|
回答問題之前先來看看什么是壓縮。當你有天走在路上，碰見熟人對你說：“吃了？”你一定知道他是在打招呼，既不是要請客也不是讓你“沒吃趕緊回家吃去”。這一句簡單的“吃了”是禮貌和問好的體現(xiàn)，也是一種信息的壓縮�；\統(tǒng)地說，把一系列已有信息通過一定方法處理，使得其長度縮短，并且信息含量基本或者完全不變，就稱之為壓縮。 計算機上的壓縮過程 我們都知道，計算機采用的是2進制系統(tǒng)。一個連續(xù)的n位二進制數(shù)集，就可以用來表示 2 n 個字符。目前的國際標準是ASCII碼：用一個字節(jié)即8位數(shù)的2進制碼，來表示各種字符和字母。 現(xiàn)在我們只使用2位二進制碼，來簡單地演示由4個符號組成的字符串的壓縮過程。 假設我們有這么一串20個字母的數(shù)據(jù)： 
默認情況下，用2位2進制碼來表示這四個字母：
A:6次 B:10次 C:3次 D:1次 而在計算機中，數(shù)據(jù)則是以2進制碼的形式儲存在硬盤上的： 00 00 01 00 00 01 01 10 01 00 01 01 01 10 01 01 00 01 11 10 壓縮過程如下： ①注明每個字符的出現(xiàn)次數(shù)。把兩個出現(xiàn)次數(shù)最小的字符圈到一起，看作一個新字符，新字符的次數(shù)為兩個組成字符的次數(shù)之和。 ②重復上述操作，直至完成對所有字符的處理。這種操作形成的結構看起來像棵樹（下圖），被稱為——霍夫曼(Huffman)樹。 ③在每一層的分支線上，按下圖所示分別標上0和1。 從最頂端往下讀，每個字符都有唯一的分支編號連到它那里，無重復也無遺漏，這樣就得到了ABCD這四個字符的新的代碼：
10 10 0 10 10 0 0 110 0 10 0 0 0 110 0 0 10 0 111 110 整理一下得到新編碼： 原編碼：0000010000010110010001010110010100011110 新編碼：1010010100011001000011000100111110 看！數(shù)據(jù)成功被壓縮。這一段40位長度的內容被壓縮到了34位，壓縮率是85%。 回顧過程容易發(fā)現(xiàn)壓縮的秘密：出現(xiàn)頻率最多的"B"由一位二進制碼“0”來表示，而出現(xiàn)頻率較低的"C"和"D"，則由長度增加了的三位二進制碼來表示。通過合理分配不同長度的編碼，肯定可以對數(shù)據(jù)進行一定程度的壓縮。 另外可以證明，霍夫曼樹就是此類編碼替代的最優(yōu)化的方案之一。因為假如存在一個字符的出現(xiàn)頻率高于另一個字符，而它的變長碼長度卻長于另一個字符，那么必然可以通過交換兩者的位置，使得輸出結果的總長度變短。有限次操作后可以達到無法再交換的情況，也就是霍夫曼樹規(guī)則下的情況。 進一步思考幾個問題 在壓縮文件的時候，人們不禁會產生一些新想法或者遇到一些疑問：是否可以對壓縮后的數(shù)據(jù)再次壓縮？當2 n 的n變大后，遇到A：1010，B：10這樣的情況，如何解讀10101010？ 就操作上來說，當然能反復編碼，但通過對本文例子中得到的新編碼再次操作后會發(fā)現(xiàn)，結果是不會有任何變化的。壓縮的實質，在于消除特定字符分布上的不均衡，通過將短碼分配給高頻字符，而長碼對應低頻字符實現(xiàn)長度上的優(yōu)化。而數(shù)據(jù)經過一次壓縮后，字符的分布已經幾乎平均化了，很難更進一步的壓縮了。 而第二個問題描述的情況是不會出現(xiàn)的的。從構造霍夫曼樹操作上可以看到，一個字符無法在另一個字符的上層。只要操作正確，就一定可以構造出唯一的代碼表，不存在歧義。 還有一個有趣的問題是：雖然把40字節(jié)的內容壓縮到了34字節(jié)，但需要將相應的碼表一并發(fā)送給接收方（沒有對應碼表，無法解壓）。這不反而使得壓縮后的數(shù)據(jù)比壓縮前的還要長？ 事實也確實如此。本文例子中，真正的最終結果體積是大于原文的。但這不意味了算法錯誤。這是因為“n”過�。ɡ又袨�2，實際通常為8）導致的。 總長度的不夠使得節(jié)省出來的那部分容量還不足以彌補碼表本身的儲存空間。實際應用中，如果你非要去壓縮一個只有幾個字節(jié)的文件，得到的壓縮包也經常會大于文件本身。通常，壓縮軟件會在每壓縮4kb到32kb數(shù)據(jù)后，重新生成并保存一個霍夫曼樹。當分塊過大時，統(tǒng)計上的整體平均，會掩蓋小區(qū)域內的極度不平均，損失了壓縮的空間。比如存在一個這樣的文件： AAAAA……AAAAA（一萬個）BBBBB……BBBBB（一萬個）……ZZZZ（一萬個）。 如果從整體上進行霍夫曼樹操作，將不會產生任何壓縮，但是這時候我們把它分成26塊，壓縮并各自保存相應的重新編碼的霍夫曼樹，壓縮率將非常驚人，約等于12.5%。
英語中各字母出現(xiàn)頻率示意圖 |
