Managing Gigabytes--文本壓縮

開門見山，文本壓縮可以歸納為兩大類, 符号方法和字典方法， 下面分别介紹下：

1）符号方法，symbolwise method

普通編碼方式是每個字元都采用相同位數編碼， 比如asc碼， 每個字元都是8位編碼。

那麼現在要壓縮，就是要用更少的位數來表示字元。顯而易見， 我們隻須用較小的位數來表示高機率字元， 用較長的位數來表示低機率字元，這樣平均下來就可以實作壓縮。

那麼這裡面就有兩個點：

a）怎麼來确定每個待編碼字元的機率，這就是機率模型問題。

所謂機率模型就是為編碼器提供的機率分布函數，我們必須保證編碼器，和解碼器使用相同的模型， 不然解出來的就不對了。

那麼對于一個符号的編碼位數是有個下限的， 和這個符合的資訊量i(s)相關。

i(s)= -logpr[s] (pr[s]就是s符合出現的機率)

是以對于”擲硬币面向上“這個事實，至少要用-log(1/2)=1位來編碼。

那麼對于字母表中每個符合的平均資訊量稱為”機率分布的熵（entropy）“， h = sum(pr[s]*i[s])

假定符合以假設的機率值獨立出現，h為壓縮下限。即這是個理論極值，實際上不可能達到。

這也就是claude shannon著名的編碼原理。

回到模型，可分為每個字元都當獨立的符号來處理的0階模型和僅考慮有限個前驅符号的m階有限上下文模型。 

也可分為靜态模型， 半靜态模型， 和自适應模型。

靜态模型就是不考慮正在編碼的文本，隻使用固定的模型，這個模型就适用于文本模式相對固定的任務。

半靜态模型就先為要壓縮的檔案生成模型， 發送給解壓方， 這個方法需要周遊兩遍被壓縮的文檔， 是以這個solution明顯不太好。

是以比較流行的是自适應模型，adaptive modeling，即以平緩的機率模型開始， 随着遇到的符号變多， 不斷的調整。

自适應模型往往要解決零頻問題，這個問題解決方法很多， 最簡單的是預設每個字元在剛開始時已出現過一次。

這種模型的缺點是不能對文本進行随機通路， 必須從文本的開頭開始解碼，因為我們必須保證編碼和解碼時的context是相同的。

對于怎麼建立符号機率模型， 也是有很多研究， 比如部分比對模型（prediction by partial matching, ppm）依據以前的字元做出預測, 動态馬爾可夫模型基于有限狀态機。

這些模型就不較長的描述了， 有興趣可以參看相關文獻。

b）知道待編碼字元的機率，怎麼給它配置設定合适的編碼， 這就是編碼算法的問題。

哈夫曼編碼

介紹編碼算法當然先來看看哈夫曼編碼， 這個号稱是作者在研究所學生時為了避免參加科目考試而想出的算法，很簡單也很高效。再一次對美國的教育環境表示深深的敬意和向往。

這類算法基本想法就是給高機率字元配置設定較少位數的編碼。

這就有個問題， 如果每個字元的編碼位數不一樣， 那麼我們怎麼知道後一個字元的編碼位數，肯定不能用個len去指定。

哈夫曼的方法是解決編碼字首的歧義性（ambiguity）， 即字首編碼，就是說每個編碼的字首都是不同的

那麼怎麼去産生編碼和怎麼去解碼呢？

哈夫曼樹，通過哈夫曼樹，從下到上進行編碼， 從上到下進行解碼。具體怎麼建構哈夫曼樹， 就不具體說了， 很簡單。

再一次感歎此算法構思的巧妙和簡單。

對于靜态的機率分布， 哈夫曼算法是很好的， 但對于自适應模型，哈夫曼算法會耗費較多的記憶體或時間。

因為自适應模型在同一時間會使用許多不同的機率分布，依賴于被編碼文本的上下文的不同。那麼這樣就要同時建立多顆哈夫曼樹。

算術編碼

那麼對于自适應模型而言算術編碼更受歡迎。

算術編碼相對比較複雜，不過顯著的優勢是算術編碼可以用低于一位的編碼來表示高機率字元， 而哈夫曼編碼對于每個字元至少要用一位來編碼。

由于算術編碼包含了各種不同的機率分布， 是以比較适合自适應模型。

但對于靜态模型，還是哈夫曼編碼要快許多。

算術編碼的基本思想就是， 在編碼過程中， 随着各個字元的出現不斷縮小機率區間， 高機率字元不會大幅地縮短區間，而低機率字元會導緻産生一個小的多的‘下一個’區間。

算術編碼隻有當編碼完成時，才會一次性輸出編碼，編碼值就是在最終的機率區間内任意選取一個值，區間越小，表示這個值所用的位數越多。

不好了解，就舉個例子：

對于隻有3個字元的字元集a,b,c, 對bccb進行編碼

為解決零頻問題， 開始假設a,b,c個出現過一次

編碼前機率區間為[0,1]，此時abc的機率都是1/3，是以abc各占機率區間的1/3, 如b的機率區間為[0.33, 0,66]

開始編碼......

第一個字元b，是以機率區間縮短為[0.33, 0,66]

此時a:b:c的比例為1:2:1，是以各個字元的機率區間變為a = [0.333,0.416], b = [0.416, 0.583], c = [0.583, 0.666]

第二個字元c，是以機率區間縮短為[0.583, 0.666]

此時a:b:c的比例為1:2:2，是以各個字元的機率區間變為a = [0.583,0.600], b = [0.600, 0.633], c = [0.633, 0.666]

第三個字元c，是以機率區間縮短為[0.633, 0.666]

此時a:b:c的比例為1：2：3，。。。。。。

最終機率區間縮小至[0.639, 0.650]

是以0.64就可以作為bccb的編碼。

而解碼的過程就是照着編碼的過程重做一遍即可，

解碼前機率區間為[0,1]，此時abc的機率都是1/3，是以abc各占機率區間的1/3, 如b的機率區間為[0.33, 0,66]

是以0.64落在了b的機率區間内, 第一個字元為b

機率區間縮短為[0.33, 0,66]， 此時a:b:c的比例為1:2:1，是以各個字元的機率區間變為a = [0.333,0.416], b = [0.416, 0.583], c = [0.583, 0.666]

是以0.64落在了c的機率區間内, 第二個字元為c

。。。。。。最終完成解碼。

區間中的數需要的多少位來表示和區間長度的負對數成正比。而最終的區間長度是已編碼符合機率值的乘積（顯而易見）。

而log(ab)= log(a)+log(b), 是以最終的區間長度的對數就等于所有已編碼符号單獨機率值的對數的和。是以具有機率pr[s]的符号s對輸出編碼的貢獻是-logpr[s]， 與符号資訊量相同。

是以算術編碼的輸出位數接近最優。

2）字典方法，dictionary method

字典模式很好了解， 用字典裡面的碼字來替換原文，如果這個碼字比原文的位數少，那麼就實作了壓縮， 如果你的字典是獨有的， 不公開的， 那麼就實作了加密。

那麼為了實作壓縮， 就要基于詞或短語進行編碼， 基于字元壓縮效果肯定不好， 那麼如果這個字典是靜态的，因為各個領域的詞和短語都不一樣的， 是以不可能适用于所有文本。

也有半靜态的，就是每次對要壓縮的文本生成一個字典，這個方法肯定也不好。

是以就有自适應的字典方案（adaptive dictionary scheme）， 這個就有技術含量了怎麼産生自适應的字典了。

當然牛人是很多的，ziv和lempel發明了lz77和lz88兩種方法。

牛人想出來的方法都是很簡單，很好用的， 這個也不例外，基本原理就是文本的子串被指向其以前出現之處的指針所替換。

說白了，就是字典碼書就是文本本身， 碼字就是指針。個人感覺，在發明這個方法時， 作者可能并沒有想到什麼基于字典模式的方法，應該是後面的學者把它歸到這類了。

我們就以lz77來了解下這個方法，

lz77的輸出碼是一系列三元組，（a,b,c）, a表示往前回溯多遠， b表示短語多長， c表示要輸入的下一個字元。

為什麼要有c項，是為沒有出現過的字元準備的, 這個設計照顧了新字元引進的需要。

以abaabab為例，輸出碼為：

（0,0,a） (0,0,b) (2,1,a) (3,2,b)

這個方法需要在之前的文本中找到最大比對視窗， 這個不能線性查找， 一般采用散清單， 或二分查找樹來實作。

著名的gzip就是這個算法的一個變體，

gzip用hash table來定位之前出現的字元串， 用3個連續的字元作為hash鍵值，連結清單中記錄了這三個字元在視窗中出現的位置資訊。

出于效率的考慮，限制了連結清單的長度， 其實也沒有必要記錄過遠的位置， 記較近的幾個位置比較合理。

gzip比較有意思的是，對指針的偏移值也做了哈夫曼編碼，較常用的值用較少的編碼。同時對字元串比對長度值， 也采用哈夫曼編碼。

當之前沒有發現比對的時候， 傳遞一個原始字元（raw character），有意思的是這個原始字元和字元串比對長度值公用同一個編碼。

也就是說第二項有可能是個字元串比對長度值， 也有可能是個原始字元，反正字首編碼， 也不沖突， 用心良苦都是為了壓縮。

本文章摘自部落格園，原文釋出日期：2011-07-04