莫爾斯碼的啟示#

• 1837 年莫爾斯發明了莫爾斯碼，用長短不同的兩種信號對英語字母和常見符號進行編碼
• 核心原則：用較短的編碼表示常見的字母，用較長的編碼表示不常見的字母
• 莫爾斯碼的平均編碼長度為 2.56，比等長編碼高效得多，大約可以節省 30% 的發報時間

變長編碼的普遍原則#

• 無論是莫爾斯碼還是各國長途電話區位碼的設計，都遵循同一個原則：
  • 把較短的編碼分配給常見的信息
  • 把較長的編碼分配給不常出現的信息
• 這樣做比對所有信息採用同樣碼長在總體上更合算

等長編碼 vs. 變長編碼的例子#

假定有 32 條信息，每條信息出現的概率分布為 1/2, 1/4, 1/8, 1/16, …, 1/2^31, 1/2^31：

• 方法 1（等長編碼）：每條信息用五位二進制數表示，碼長為 5
• 方法 2（變長編碼）：第一條信息用 0 編碼，第二條用 10，第三條用 110……最後兩條用 111…110 和 111…111
  • 雖然某些信息的碼長超過 5，但平均碼長只有 2
  • 變長編碼節省了 60% 的碼長，而這個編碼的長度也是香農所給出的極限

可譯碼的條件#

• 在上述變長編碼中，除了最後一個，所有的編碼都是以 0 結束的
• 每當看到 0 時，計算機就知道當前的碼傳輸完畢了，下面要開始新的了
• 如果將 1、11、101、111 這樣的二進制串也設計為編碼，接收到 111 時就無法確定是一個符號還是多個符號的組合

哈夫曼編碼算法#

1952 年，麻省理工學院的學生大衛·哈夫曼（David Huffman）發明了一種算法，對於已知概率分布的信息，它可以找到一種平均編碼長度最短的編碼方式。

算法步驟#

1. 排序：先將所有信息按照概率從小到大排序
2. 合併：將概率最小的兩個信息合併，概率相加後插回排好序的序列中
3. 重複：不斷重複步驟 2，每次合併概率最小的兩組信息，直到所有信息合併到一起
4. 編碼：所有信息形成一棵二叉樹，把左子樹用 0 作為編碼，右子樹用 1 作為編碼，從樹根到葉節點順序排列就得到了所有信息的編碼

具體例子#

八種不等概率的信息 A ～ H，概率分別為 0.1、0.05、0.3、0.2、0.15、0.15、0.03、0.02：

• 平均碼長為 2.65，比等長編碼要短
• 根據香農的信息論，上述概率分布的信息熵是 2.61，哈夫曼編碼已經非常接近這個極限

信息冗餘度與壓縮效率#

• 信息的編碼長度和它的信息熵之間的差異被稱為信息的冗餘度
• 冗餘度越高，說明信息編碼的效率越低；反之則越高
• 對信息進行哈夫曼編碼後，冗餘度近乎為零，因此它是計算機中最常見的一種壓縮算法

應用場景#

• 漢字文本壓縮：按漢字出現的頻率統計，然後用哈夫曼編碼進行壓縮，通常能壓掉一半左右的冗餘
• 按詞組壓縮：如果按照詞的頻率統計再壓縮，可以壓縮掉 70% 以上的冗餘
• 句子層面的壓縮效果有限：一篇文章中通常不會有大量重複的句子，因此每個句子實際上都是等概率的

編碼的藝術在於「將最好的資源用在最重要的地方」。今天大部分標準的編碼算法都有開源代碼可以直接使用；能夠看懂代碼是一級工程師的基本要求，能理解算法原理是四級工程師的要求，能根據情況修改標準編碼以提高性能是三級工程師的水平。

要點#

• 有效編碼的關鍵在於將較短的碼字給予出現概率高的信息，將較長的碼字給予不常出現的信息
• 無論如何編碼，編碼的平均碼長不會短於相應信號源的信息熵