認識壓縮算法
我們想必都有過壓縮和 解壓縮文件的經歷，當文件太大時，我們會使用文件壓縮來降低文件的佔用空間。比如微信上傳文件的限制是100 MB，我這裡有個文件夾無法上傳，但是我解壓完成後的文件一定會小於 100 MB，那麼我的文件就可以上傳了。
此外，我們把相機拍完的照片保存到計算機上的時候，也會使用壓縮算法進行文件壓縮，文件壓縮的格式一般是JPEG。
那麼什麼是壓縮算法呢？壓縮算法又是怎麼定義的呢？在認識算法之前我們需要先了解一下文件是如何存儲的
文件存儲
文件是將數據存儲在磁碟等存儲媒介的一種形式。程序文件中最基本的存儲數據單位是字節。文件的大小不管是 xxxKB、xxxMB等來表示，就是因為文件是以字節 B = Byte 為單位來存儲的。
文件就是字節數據的集合。用 1 字節（8 位）表示的字節數據有 256 種，用二進位表示的話就是 0000 0000 - 1111 1111 。如果文件中存儲的數據是文字，那麼該文件就是文本文件。如果是圖形，那麼該文件就是圖像文件。在任何情況下，文件中的字節數都是連續存儲的。
壓縮算法的定義
上面介紹了文件的集合體其實就是一堆字節數據的集合，那麼我們就可以來給壓縮算法下一個定義。
壓縮算法（compaction algorithm）指的就是數據壓縮的算法，主要包括壓縮和還原（解壓縮）的兩個步驟。
其實就是在不改變原有文件屬性的前提下，降低文件字節空間和佔用空間的一種算法。
根據壓縮算法的定義，我們可將其分成不同的類型：
有損和無損
無損壓縮：能夠無失真地從壓縮後的數據重構，準確地還原原始數據。可用於對數據的準確性要求嚴格的場合，如可執行文件和普通文件的壓縮、磁碟的壓縮，也可用於多媒體數據的壓縮。該方法的壓縮比較小。如差分編碼、RLE、Huffman編碼、LZW編碼、算術編碼。
有損壓縮：有失真，不能完全準確地恢復原始數據，重構的數據只是原始數據的一個近似。可用於對數據的準確性要求不高的場合，如多媒體數據的壓縮。該方法的壓縮比較大。例如預測編碼、音感編碼、分形壓縮、小波壓縮、JPEG/MPEG。
對稱性
如果編解碼算法的複雜性和所需時間差不多，則為對稱的編碼方法，多數壓縮算法都是對稱的。但也有不對稱的，一般是編碼難而解碼容易，如 Huffman 編碼和分形編碼。但用於密碼學的編碼方法則相反，是編碼容易，而解碼則非常難。
幀間與幀內
在視頻編碼中會同時用到幀內與幀間的編碼方法，幀內編碼是指在一幀圖像內獨立完成的編碼方法，同靜態圖像的編碼，如 JPEG；而幀間編碼則需要參照前後幀才能進行編解碼，並在編碼過程中考慮對幀之間的時間冗餘的壓縮，如 MPEG。
實時性
在有些多媒體的應用場合，需要實時處理或傳輸數據（如現場的數字錄音和錄影、播放MP3/RM/VCD/DVD、視頻/音頻點播、網絡現場直播、可視電話、視頻會議），編解碼一般要求延時 ≤50 ms。這就需要簡單/快速/高效的算法和高速/複雜的CPU/DSP晶片。
分級處理
有些壓縮算法可以同時處理不同解析度、不同傳輸速率、不同質量水平的多媒體數據，如JPEG2000、MPEG-2/4。
這些概念有些抽象，主要是為了讓大家了解一下壓縮算法的分類，下面我們就對具體的幾種常用的壓縮算法來分析一下它的特點和優劣
幾種常用壓縮算法的理解
RLE 算法的機制
接下來就讓我們正式看一下文件的壓縮機制。首先讓我們來嘗試對 AAAAAABBCDDEEEEEF 這 17 個半角字符的文件（文本文件）進行壓縮。雖然這些文字沒有什麼實際意義，但是很適合用來描述 RLE 的壓縮機制。
由於半角字符（其實就是英文字符）是作為 1 個字節保存在文件中的，所以上述的文件的大小就是 17 字節。如圖
（這裡有個問題需要讀者思考一下：為什麼 17 個字符的大小是 17 字節，而佔用空間卻很大呢？這個問題此篇文章暫不討論）
那麼，如何才能壓縮該文件呢？大家不妨也考慮一下，只要是能夠使文件小於 17 字節，我們可以使用任何壓縮算法。
最顯而易見的一種壓縮方式我覺得你已經想到了，就是把相同的字符去重化，也就是 字符 * 重複次數 的方式進行壓縮。所以上面文件壓縮後就會變成下面這樣
從圖中我們可以看出，AAAAAABBCDDEEEEEF的17個字符成功被壓縮成了 A6B2C1D2E5F1 的12個字符，也就是 12 / 17 = 70%，壓縮比為 70%，壓縮成功了。
像這樣，把文件內容用 數據 * 重複次數 的形式來表示的壓縮方法成為 RLE(Run Length Encoding, 行程長度編碼) 算法。RLE 算法是一種很好的壓縮方法，經常用於壓縮傳真的圖像等。因為圖像文件的本質也是字節數據的集合體，所以可以用 RLE 算法進行壓縮
RLE 算法的缺點
RLE 的壓縮機制比較簡單，所以 RLE 算法的程序也比較容易編寫，所以使用 RLE 的這種方式更能讓你體會到壓縮思想，但是 RLE 只針對特定序列的數據管用，下面是 RLE 算法壓縮匯總
通過上表可以看出，使用 RLE 對文本文件進行壓縮後的數據不但沒有減小反而增大了！幾乎是壓縮前的兩倍！因為文本字符種連續的字符並不多見。
就像上面我們探討的這樣，RLE 算法只針對連續的字節序列壓縮效果比較好，假如有一連串不相同的字符該怎麼壓縮呢？比如說ABCDEFGHIJKLMNOPQRSTUVWXYZ，26個英文字母所佔空間應該是 26 個字節，我們用 RLE 壓縮算法壓縮後的結果為 A1B1C1D1E1F1G1H1I1J1K1L1M1N1O1P1Q1R1S1T1U1V1W1X1Y1Z1 ，所佔用 52 個字節，壓縮完成後的容量沒有減少反而增大了！這顯然不是我們想要的結果，所以這種情況下就不能再使用 RLE 進行壓縮。
哈夫曼算法和莫爾斯編碼
下面我們來介紹另外一種壓縮算法，即哈夫曼算法。在了解哈夫曼算法之前，你必須捨棄半角英文數字的1個字符是1個字節(8位)的數據。下面我們就來認識一下哈夫曼算法的基本思想。
文本文件是由不同類型的字符組合而成的，而且不同字符出現的次數也是不一樣的。例如，在某個文本文件中，A 出現了 100次左右，Q僅僅用到了 3 次，類似這樣的情況很常見。哈夫曼算法的關鍵就在於 多次出現的數據用小於 8 位的字節數表示，不常用的數據則可以使用超過 8 位的字節數表示。A 和 Q 都用 8 位來表示時，原文件的大小就是 100次 8 位 + 3次 8 位 = 824位，假設 A 用 2 位，Q 用 10 位來表示就是 2 100 + 3 10 = 230 位。
不過要注意一點，最終磁碟的存儲都是以8位為一個字節來保存文件的。
哈夫曼算法比較複雜，在深入了解之前我們先吃點甜品，了解一下 莫爾斯編碼，你一定看過美劇或者戰爭片的電影，在戰爭中的通信經常採用莫爾斯編碼來傳遞信息，例如下面
接下來我們來講解一下莫爾斯編碼，下面是莫爾斯編碼的示例，大家把 1 看作是短點(嘀)，把 11 看作是長點(嗒)即可。
莫爾斯編碼一般把文本中出現最高頻率的字符用短編碼 來表示。如表所示，假如表示短點的位是 1，表示長點的位是 11 的話，那麼 E（嘀）這一數據的字符就可以用 1 來表示，C（滴答滴答）就可以用 9 位的 110101101來表示。在實際的莫爾斯編碼中，如果短點的長度是 1 ，長點的長度就是 3，短點和長點的間隔就是1。這裡的長度指的就是聲音的長度。比如我們想用上面的 AAAAAABBCDDEEEEEF 例子來用莫爾斯編碼重寫，在莫爾斯曼編碼中，各個字符之間需要加入表示時間間隔的符號。這裡我們用 00 加以區分。
所以，AAAAAABBCDDEEEEEF 這個文本就變為了 A 6 次 + B 2次 + C 1次 + D 2次 + E 5次 + F 1次 + 字符間隔 16 = 4 位 6次 + 8 位 2次 + 9 位 1 次 + 6位 2次 + 1位 5次 + 8 位 1次 + 2位 16次 = 106位 = 14位元組。
所以使用莫爾斯電碼的壓縮比為 14 / 17 = 82%。效率並不太突出。
用二叉樹實現哈夫曼算法
剛才已經提到，莫爾斯編碼是根據日常文本中各字符的出現頻率來決定表示各字符的編碼數據長度的。不過，在該編碼體系中，對 AAAAAABBCDDEEEEEF 這種文本來說並不是效率最高的。
下面我們來看一下哈夫曼算法。哈夫曼算法是指，為各壓縮對象文件分別構造最佳的編碼體系，並以該編碼體系為基礎來進行壓縮。因此，用什麼樣的編碼（哈夫曼編碼）對數據進行分割，就要由各個文件而定。用哈夫曼算法壓縮過的文件中，存儲著哈夫曼編碼信息和壓縮過的數據。
接下來，我們在對 AAAAAABBCDDEEEEEF 中的 A - F 這些字符，按照出現頻率高的字符用儘量少的位數編碼來表示這一原則進行整理。按照出現頻率從高到低的順序整理後，結果如下，同時也列出了編碼方案。
在上表的編碼方案中，隨著出現頻率的降低，字符編碼信息的數據位數也在逐漸增加，從最開始的 1位、2位依次增加到3位。不過這個編碼體系是存在問題的，你不知道100這個3位的編碼，它的意思是用 1、0、0這三個編碼來表示 E、A、A 呢？還是用10、0來表示 B、A 呢？還是用100來表示 C 呢。
而在哈夫曼算法中，通過藉助哈夫曼樹的構造編碼體系，即使在不使用字符區分符號的情況下，也可以構建能夠明確進行區分的編碼體系。不過哈夫曼樹的算法要比較複雜，下面是一個哈夫曼樹的構造過程。
自然界樹的從根開始生葉的，而哈夫曼樹則是葉生枝
哈夫曼樹能夠提升壓縮比率
使用哈夫曼樹之後，出現頻率越高的數據所佔用的位數越少，這也是哈夫曼樹的核心思想。通過上圖的步驟二可以看出，枝條連接數據時，我們是從出現頻率較低的數據開始的。這就意味著出現頻率低的數據到達根部的枝條也越多。而枝條越多則意味著編碼的位數隨之增加。
接下來我們來看一下哈夫曼樹的壓縮比率，用上圖得到的數據表示 AAAAAABBCDDEEEEEF 為 000000000000 100100 110 101101 0101010101 111，40位 = 5 字節。壓縮前的數據是 17 字節，壓縮後的數據竟然達到了驚人的5 字節，也就是壓縮比率 = 5 / 17 = 29% 如此高的壓縮率，簡直是太驚豔了。
大家可以參考一下，無論哪種類型的數據，都可以用哈夫曼樹作為壓縮算法
可逆壓縮和非可逆壓縮
最後，我們來看一下圖像文件的數據形式。圖像文件的使用目的通常是把圖像數據輸出到顯示器、印表機等設備上。常用的圖像格式有 : BMP、JPEG、TIFF、GIF 格式等。
BMP ： 是使用 Windows 自帶的畫筆來做成的一種圖像形式JPEG：是數位相機等常用的一種圖像數據形式TIFF: 是一種通過在文件中包含"標籤"就能夠快速顯示出數據性質的圖像形式GIF： 是由美國開發的一種數據形式，要求色數不超過 256個圖像文件可以使用前面介紹的 RLE 算法和哈夫曼算法，因為圖像文件在多數情況下並不要求數據需要還原到和壓縮之前一摸一樣的狀態，允許丟失一部分數據。我們把能還原到壓縮前狀態的壓縮稱為 可逆壓縮，無法還原到壓縮前狀態的壓縮稱為非可逆壓縮 。
一般來說，JPEG格式的文件是非可逆壓縮，因此還原後有部分圖像信息比較模糊。GIF 是可逆壓縮
轉自：https://segmentfault.com/a/1190000020921942