眾所周知，通過網(wǎng)絡(luò)上傳或者下載數(shù)據(jù)的每一個(gè)字節(jié)都是要花流量的，即需要花錢的。盡管現(xiàn)存的壓縮算法已經(jīng)有幾十上百種，但其中最流行的壓縮算法可能還是 zip。gzip 壓縮算法雖然和 zip 有著相似的名字，但卻是另一種不同的算法。gzip 算法應(yīng)用也相當(dāng)廣泛，它被 HTTP 三種標(biāo)準(zhǔn)壓縮規(guī)范之一（譯者注：屬于端到端壓縮技術(shù)，參見 HTTP 協(xié)議中的數(shù)據(jù)壓縮 ）所采用。雖然各種壓縮算法適用于不同場景，但是它們的底層都是基于 DEFLATE 。 DEFLATE是同時(shí)使用了 LZ77 算法與 哈夫曼編碼 （Huffman Coding）的一種無損數(shù)據(jù)壓縮算法。
LZ77
DEFLATE基于 LZ77 算法——這是一種用于文本壓縮的無損壓縮技術(shù)。
壓縮
LZ77算法通過使用編碼器或者解碼器中已經(jīng)出現(xiàn)過的相應(yīng)匹配數(shù)據(jù)信息替換當(dāng)前數(shù)據(jù)從而實(shí)現(xiàn)壓縮功能。
此算法并非同時(shí)在整個(gè)文本中查找重復(fù)的字母，一般會(huì)先設(shè)定一個(gè)固定大小的搜索緩沖區(qū)，例如 20（在真實(shí)場景中，這個(gè)緩沖區(qū)的大小一般是幾十 kB ）。接著在逐一對文本中字母進(jìn)行編碼時(shí)，首先會(huì)判斷當(dāng)前字母是否有出現(xiàn)在前面緩沖區(qū)的 20 個(gè)字母中。如果能找到匹配的字母，就記錄下當(dāng)前字母與找到的字母的偏移量 d ，這樣就完成了一個(gè)字母編碼的第一階段。接來下，用當(dāng)前在編碼字母鄰近的下一個(gè)字母與緩沖區(qū)中匹配上字母鄰近的下一字母進(jìn)行匹配，如果匹配上就繼續(xù)進(jìn)行下一個(gè)字母的匹配，如此循環(huán)往復(fù)直到緩沖區(qū) 20 個(gè)字母匹配完或者鄰近的字母未匹配上，就結(jié)束匹配過程。結(jié)束上述過程后，將當(dāng)前位置匹配上的連續(xù)字母替換成與緩沖區(qū)字母的偏移量以及這段連續(xù)字母的個(gè)數(shù) l 。這樣，字母編碼的第二階段就完成了。
讓我們用這個(gè)例子來看看它是如何工作的:
ERTOORTORR
首先能想到的最簡單做法就是直接替換第二次出現(xiàn)的 O 為指向第一次出現(xiàn)的 O 的一個(gè)標(biāo)記，或者替換第二次出現(xiàn)的 RTO 為指向第一次出現(xiàn)的 RTO 。
下面更具體地描述一下這個(gè)過程，假定我們設(shè)置的緩沖區(qū)大小是 4，把這 4 個(gè)長度的緩沖區(qū)看成是一個(gè)滑動(dòng)窗口沿著正文文本向右滑動(dòng)：
1) [....E]RTOORTORR
2) [...ER]TOORTORR
3) [..ERT]OORTORR
4) [.ERTO]ORTORR
5) [ERTOO]RTORR -> ERTO(1, 1)RTOORR
6) E[RTOOR]TORR -> ERTO(1, 1)(4, 3)RR
7) ERTO[ORTOR]R -> ERTO(1, 1)(4, 3)(3, 1)R
8) ERTOO[RTORR] -> ERTO(1, 1)(4, 3)(3, 1)(1, 1)
滑動(dòng)窗口隨著隨著編碼的迭代一步步向右移動(dòng)，前面 4 步中滑動(dòng)窗口內(nèi)的字母都沒有發(fā)現(xiàn)重復(fù)。到了第 5 步，滑動(dòng)窗口內(nèi)字母 O 已經(jīng)出現(xiàn)重復(fù)了，然后查看字母 O 右側(cè)的 R 發(fā)現(xiàn)在滑動(dòng)窗口中匹配字母 O 右側(cè)相鄰的字母并非 R ，便不再繼續(xù)向右進(jìn)行匹配，將第 2 個(gè) O 替換成 (1, 1) （表示：滑動(dòng)窗口中匹配的字母離當(dāng)前字母偏移距離為 1，匹配上的連續(xù)字母長度為 1）。在第 6 步中，滑動(dòng)窗口中字母 R 與其左邊第 4 個(gè)字母匹配上了，繼續(xù)檢查下一個(gè)字母 T 的匹配情況，然后發(fā)現(xiàn)滑動(dòng)窗口中 RT 也匹配上了。然后繼續(xù)下一個(gè)字母 O ，在滑動(dòng)窗口中匹配 RTO 也匹配上了，并且到此為止，因?yàn)橄乱粋€(gè)字母匹配上了。滑動(dòng)窗口中匹配上的字母與當(dāng)前字母的偏移距離為 4，同時(shí)有連續(xù) 3 個(gè)字母匹配上了，所以這里將匹配上的 3 個(gè)字母替換成 (4, 3) 。接著在第 7 步中，字母 R 與偏移距離 3 出的字母匹配上，但是接下來的 RR 并未匹配上，在第 8 步中發(fā)現(xiàn)最近的匹配上的 R 的偏移距離為 1。最終整段文本經(jīng)過編碼的結(jié)果如下：
ERTO(1, 1)(4, 3)(3, 1)(1, 1)
解壓
壓縮過的文本其實(shí)是由一系列的這種 (d, 1) 標(biāo)記對和字母組成，標(biāo)記對無法直接找到相匹配的字母。在解壓過程中，字母保持不變，這種標(biāo)記對轉(zhuǎn)換為其指向位置的字母。下面看一個(gè)解壓的例子：
abc(3, 2)(1, 1)
字母 abc 保持不變，標(biāo)記對 (3, 2) 表示從當(dāng)前位置向左移動(dòng) 3 個(gè)單位，然后取出 2 個(gè)字母，因此其轉(zhuǎn)換為 ab 。現(xiàn)在原始文本變成了這樣 abcab(1, 1) ，最后的一個(gè)標(biāo)記對表示從當(dāng)前位置向左移動(dòng) 1 個(gè)單位，然后取出 1 個(gè)字母，因此轉(zhuǎn)換為 b 。最終解壓完成的文本為 abcabb 。
哈夫曼編碼
在用 LZ77 消除了文本中重復(fù)的字母后，再使用 哈夫曼編碼 進(jìn)行第二次壓縮。這種方法用較短的編碼代替較常用的字母，用較長的編碼代替較少用的字母，從而減少了文本的總長度。
讓我們用一個(gè)簡單的示例文本來看看它是如何工作的。
壓縮
EFTUPOEERRREOOPRRUTUTTEEE
這個(gè)例子中，我們希望能無損地壓縮這段文本。通常一個(gè)字母占用 8 字節(jié)，所以這段文本總長度有 200 字節(jié)。在這段本文中，我們發(fā)現(xiàn)其中字母 F 只出現(xiàn)了 1 次，而字母 E 出現(xiàn)了 7 次。哈夫曼編碼正是利用了這一特性，通過減少出現(xiàn)頻率高的字母本身的字節(jié)長度，來減少整個(gè)文本所占的總長度。
要采用哈夫曼編碼壓縮文章，首先需要統(tǒng)計(jì)各個(gè)文本中各個(gè)字母的出現(xiàn)頻率，上述例子中的字母頻率如下：
頻率:
E: 7, R: 5, T: 4, U: 3, O: 3, P: 2, F: 1
我們需要使用文本中的字母作為葉子節(jié)點(diǎn)來構(gòu)建一顆二叉樹，通過這顆二叉樹來編碼文本中的每一個(gè)字母。從出現(xiàn)頻率最小的字母： P 和 F 開始，讓其作為底層的葉子節(jié)點(diǎn)，將其頻率相加的值作為父節(jié)點(diǎn)，這樣便得到了如下的二叉樹：
(3)
/
P(2) F(1)
重復(fù)上面的步驟，依次使用頻率最小的字母： U 和 O 以及 R 和 T ，最后剩下頻率最高的字母 E 先單獨(dú)放著。
(6) (9) E(7)
/ /
U(3) O(3) R(5) T(4)
接下來使用上面得到的 4 個(gè)二叉樹作為子節(jié)點(diǎn)來創(chuàng)建一顆更大的二叉樹，將上面的二叉樹的根節(jié)點(diǎn)的頻率值遞增排序，優(yōu)先使用根節(jié)點(diǎn)頻率值小的二叉樹作為新的二叉樹子節(jié)點(diǎn)。這里使用 U 和 O 、 R 和 T 這兩組二叉樹組成了如下的一顆二叉樹：
(9)
/
/
(6) (3)
/ /
U O P F
這時(shí)候還有 3 顆二叉樹，根節(jié)點(diǎn)分別為：9、9、7（第一個(gè) 9 是上一步創(chuàng)建的二叉樹），同樣的，將根節(jié)點(diǎn)頻率值最小的兩個(gè)作為子節(jié)點(diǎn)創(chuàng)建新的二叉樹如下：
(16)
/
(9) E
/
/
(6) (3)
/ /
U O P F
復(fù)制代碼
現(xiàn)在剩下一顆將根節(jié)點(diǎn)值為 16 的大二叉樹和根節(jié)點(diǎn)值為 9 葉子節(jié)點(diǎn)為 R 、 T 的二叉樹，將其作為子節(jié)點(diǎn)創(chuàng)建一顆新的二叉樹如下：
(25)
/
/
(16) (9)
/ /
(9) E R T
/
/
(6) (3)
/ /
U O P F
現(xiàn)在我們要做的就是根據(jù)這棵二叉樹來對文本進(jìn)行編碼。依次從跟節(jié)點(diǎn)訪問各個(gè)字母，遇到左分支當(dāng)成 0，遇到右分支當(dāng)成 1，按照字母沿著二叉樹訪問路徑的順序所將這些 0、1 連接起來。比如，從根節(jié)點(diǎn)到字母 E 先后需要經(jīng)過 1 次左分支和 1 次右分支，所以字母 E 的編碼為 10 。字母 U 需要經(jīng)過 4 次左分支，其編碼為 1111 ； F 需要經(jīng)過 2 次左分支和 2 次右分支，其編碼為 1100 。可以發(fā)現(xiàn)，在這里例子中出現(xiàn)頻率非常高的字母 E 編碼后位數(shù)比出現(xiàn)頻率較少的字母 F 編碼后位數(shù)要少。經(jīng)過這樣的編碼處理，最終壓縮過的文本如下：
10110000111111011110101001010110111011101101010111110011110000101010
這段壓縮后的文本長度只有 68 位，遠(yuǎn)比原始的 200 位長度小。
解壓
假如收到這樣一段壓縮過的文本，我們希望能夠解壓它讓其變得可以理解。我們都知道一段未壓縮過的文本中的一個(gè)字符占用 8 位，上面說過經(jīng)過哈夫曼編碼壓縮后一個(gè)字符的位數(shù)并不是固定 8 位的，所以并不清楚一段數(shù)據(jù)（比如： 011 ）是表示 1 個(gè)字符、2 個(gè)字符或者 3 個(gè)字符，因此這段壓縮過的文本將如何解壓呢？
這一步不存在任何奇跡，要準(zhǔn)確解壓還需要上面編碼中構(gòu)建的二叉樹。得到這個(gè)用于編碼的二叉樹有兩種方案，第一種是其和壓縮后的文本放一起作為原始文本的壓縮結(jié)果，這可能會(huì)導(dǎo)致壓縮后的文本比原始文本還要大；第二種方案是使用預(yù)先定義好的二叉樹。我們知道各個(gè)字母在英語中的使用頻率，完全可以根據(jù)這個(gè)頻率來構(gòu)建上述的二叉樹。使用這種預(yù)先定義的公共字母頻率二叉樹壓縮部分文本的結(jié)果可能比根據(jù)文本內(nèi)容字母頻率二叉樹壓縮的效果差一些，但是這樣不再需要將字母頻率二叉樹保存到壓縮后的文件中。總而言之，這兩種方案各有優(yōu)缺點(diǎn)。
雖然本文沒有深入的分析各種壓縮算法原理的細(xì)節(jié)和對應(yīng)的實(shí)現(xiàn)，但是經(jīng)過上述講解你應(yīng)該已經(jīng)對文本如何被壓縮成 zip 和 gzip 等格式有了大概的認(rèn)識(shí)。希望本文能滿足你對壓縮算法神秘面紗的好奇心:)
