陳凱

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

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

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

在《蒙娜麗莎》單色位圖中，反引號(hào)“`”代表黑色，小數(shù)點(diǎn)“.”代表白色，設(shè)計(jì)字典的方式有很多。例如，把兩個(gè)反引號(hào)變成一個(gè)“！”，把兩個(gè)小數(shù)點(diǎn)變成一個(gè)“@”，之所以選擇“！”和“@”符號(hào)，是因?yàn)樵募胁]有出現(xiàn)過這兩個(gè)符號(hào)，這樣才不會(huì)在之后的解壓縮過程中產(chǎn)生混淆。

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

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

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

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

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

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

接著，就可以給這五組符號(hào)串編號(hào)，不過因?yàn)橹荒苁褂梅匆?hào)和小數(shù)點(diǎn)符號(hào)，所以編出的號(hào)碼也是只能由這兩個(gè)符號(hào)構(gòu)成：“````→ ```”“`... → ``.”“.... → `.`”

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

可以看出，之所以能夠?qū)⑺膫€(gè)符號(hào)壓縮成三個(gè)符號(hào)，是因?yàn)樵趯?shí)際數(shù)據(jù)中，反引號(hào)和小數(shù)點(diǎn)符號(hào)的排列組合所出現(xiàn)的種類的數(shù)量，要遠(yuǎn)遠(yuǎn)少于理論上全部排列組合種類的數(shù)量。

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

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

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

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

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

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