人工壓縮器

陳凱

某一天，意大利藝術家Nazarino Crea腦中忽然靈光一閃，按照現(xiàn)如今以瘦為美的標準，他用畫筆給名畫里的胖美人們來了一次速效減肥，這個舉動引來一片喧嘩。本期要講的，同樣也是為名畫瘦身，不過，瘦下來的是文件容量，而不是圖片里的身材和臉型——無損壓縮，具體來說，是以字典法編碼為基礎的無損壓縮，為充分揭示其原理，下面實驗中使用的并不是壓縮軟件，而是充滿智慧的頭腦。

首先，找一幅尺寸小一些的《蒙娜麗莎》圖，將其保存為單色位圖（如圖1），用圖像編輯軟件（如XnView）將其轉換為XPM格式的圖像文件，如果用寫字板打開這個圖像文件，就可以很明顯看出編碼文件中的二維點陣（如圖2）。

接著，觀察并記錄這個圖像文件的大小，著手對該文件進行無損壓縮。所謂的字典法，通俗來說，就是將長的符號串，映射成某個短的符號串。

在《蒙娜麗莎》單色位圖中，反引號“`”代表黑色，小數(shù)點“.”代表白色，設計字典的方式有很多。例如，把兩個反引號變成一個“！”，把兩個小數(shù)點變成一個“@”，之所以選擇“！”和“@”符號，是因為原文件中并沒有出現(xiàn)過這兩個符號，這樣才不會在之后的解壓縮過程中產(chǎn)生混淆。

為了減少人工壓縮器的勞動量，可以借助寫字板中的“全部替換”功能批量替換字符，替換后就可以看到嚴重變形的二維點陣。文件大小變成原來的一半多一些，壓縮效果顯著。如果有時間的話，還可以設定更多的映射規(guī)則。由于可以直接看到壓縮過程，所以實驗過程本身就很具有觀賞性（如圖3）。由于是用“人工壓縮器”壓縮的，所以還需要將字典的映射規(guī)則也寫到圖像文件中去，以便解壓縮時參考，這當然會額外增加一些文件容量。

然而，這個被人工壓縮的文件是無法用圖像瀏覽器直接打開觀看的，必須要用“人工解壓器”將文件解壓縮，才能正常瀏覽。方法也很簡單，將先前的替換過程反過來就可以了。如果解壓縮后，圖像瀏覽器能正常打開圖像文件，并且圖像的模樣與原來一模一樣，就證明無損壓縮和解壓縮都獲得了成功。

然而，真正在對數(shù)據(jù)進行壓縮時，遇到的問題遠沒有上面所說的那么簡單，假設某個文件完全由“0”和“1”兩個符號構成，若規(guī)定在壓縮時不能引入其他符號，那怎么對這個文件進行壓縮呢？考慮到實際上計算機中存儲的都是二進制文件，這個問題就顯得更有意義。顯然，不能簡單地在壓縮時將“00”替換成“0”，在解壓縮時將“0”換回“00”，因為如果遇見“000”這樣的符號串，經(jīng)過這番折騰后，字符串就變成了“0000”，這樣的話，文件就無法恢復到原來的樣子了。

仍然以《蒙娜麗莎》為例子，因為下面的實驗完全要靠人工實現(xiàn)，為了簡便起見，這里只抽出《蒙娜麗莎》圖像文件點陣中的某一行來說明問題：“`````````````````................``````..```.....````````````````````````````............................”。

這個符號串中只有兩個符號，反引號和小數(shù)點符號。為了壓縮數(shù)據(jù)，可以將符號按同等數(shù)量編成小組，例如，每四個符號一組，于是就得到了以下五組不同的符號串：

“````”“`...”“ ....”“.```”“```.”。

接著，就可以給這五組符號串編號，不過因為只能使用反引號和小數(shù)點符號，所以編出的號碼也是只能由這兩個符號構成：“````→ ```”“`... → ``.”“.... → `.`”

“.``` → `..”“```. → .``”。

可以看出，之所以能夠將四個符號壓縮成三個符號，是因為在實際數(shù)據(jù)中，反引號和小數(shù)點符號的排列組合所出現(xiàn)的種類的數(shù)量，要遠遠少于理論上全部排列組合種類的數(shù)量。

按以上規(guī)則替換后，原始的符號串就變成了“``````````````.`.``.``.``...```..`.``..````````````````````.`.``.``.``.``.``.`.”。

長度明顯縮短了，只占原來的四分之三，對這串數(shù)據(jù)作解壓縮，只需要反過來使用規(guī)則，把三個符號還原成四個符號就可以了。

然而，還可以將符號串變得更短，這時候需要一種特殊的字典，因為“````”“`...”“....”“.```”“```.”這四組符號串，出現(xiàn)的頻率是不同的，所以對出現(xiàn)頻率高的符號串，可以映射成短一些的符號串，而對于出現(xiàn)頻率低的符號串，則映射成長一些的符號串。例如，“`````”“.... → .`”“`... → ..`”“.``` →...`”“```. → ....”。

替換之后，初始的符號串就變成了“````..`.`.`.`...`.......`.`...```````..`.`.`.`.`.`.`.”。

符號串又顯著縮短了，大概只有原來的一半長，人們可能會懷疑，這樣的符號串能否恢復成原來的樣子呢？實際上，字典的設計并不是隨心所欲的，試一下就知道了，如果從左往右按順序匹配最短的符號串，恢復數(shù)據(jù)就不會有任何問題，這種編碼的方法實際上正是哈夫曼編碼，有興趣的朋友也可以自己查閱相關資料，設定出自己的映射規(guī)則。

然而，作為設定規(guī)則的字典，本身就占用了存儲空間，于是，令人驚嘆的LZ編碼方案橫空出世，該方案能夠用等待被壓縮的數(shù)據(jù)本身作為字典，此中機巧，實在讓人佩服得五體投地，限于篇幅，這里就不專門展開論述了。