算法科普：有趣的霍夫曼編碼

霍夫曼編碼 ( Huffman coding ) 是一種可變長的前綴碼?；舴蚵幋a使用的算法是 David A. Huffman 還是在MIT 的學生時提出的，并且在 1952 年發(fā)表了名為《 A Method for the Construction of Minimum-Redundancy Codes 》的文章。

編碼這種編碼的過程叫做霍夫曼編碼，它是一種普遍的熵編碼技術(shù)，包括用于無損數(shù)據(jù)壓縮領(lǐng)域。

霍夫曼編碼過程

霍夫曼編碼使用一種特別的方法為信號源中的每個符號設(shè)定二進制碼。出現(xiàn)頻率更大的符號將獲得更短的比特，出現(xiàn)頻率更小的符號將被分配更長的比特，以此來提高數(shù)據(jù)壓縮率，提高傳輸效率。

以字符串 ” ABAABACD “ 為例進行說明。

接下來，按照字符出現(xiàn)的比例從高往低對字符進行排序。

圖 1

然后，按出現(xiàn)比例低的順序查找兩個字母。在這種情況下，它是 “ C ” 12.5% 和 “ D ” 12.5% 。

通過一條線連接兩個字母拼構(gòu)成一個樹狀結(jié)果。將兩個字母合并為 “ C 或 D”，并將出現(xiàn)比率相加起來。

動畫 2

按照同樣的操作，將合并后的 “ C 或 D ” 視為一個字符，重復相同的操作。

在 “ A " "B" " C 或 D " 三個中，按照出現(xiàn)比例低的順序查找兩個字母。

圖 3

圖 4

這樣，所有的字母都變成了 " A 或 B 或 C 或 D" ，出現(xiàn)的比率為 100% 。

圖 4 就是霍夫曼編碼的樹結(jié)構(gòu)。

接下來再次顯示各個字母出現(xiàn)的比率，同時使用 0 和 1 進行編碼，代碼 0 和 1 分別分配給上下延伸的分支。

圖 5

分配完畢后，從樹的根部遍歷每個字符并確定相應的代碼。

在 " A " 的情況下，被分配的代碼為" 0 "

在 " B " 的情況下，被分配的代碼為 " 10 "

在 " C " 的情況下，被分配的代碼為 " 110 "

在 " D " 的情況下，被分配的代碼為 " 111 "

動畫 6

就這樣，通過這樣的編碼規(guī)則， " ABAABACD " 的二進制編碼就變成了 " 01000100110111 "，只需要 14 個比特就能表示，比單純的使用 2 比特表示一個字符縮短了很多。