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