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

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

霍夫曼編碼過程

霍夫曼編碼使用一種特別的方法為信號源中的每個符號設定二進制碼。出現(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 比特表示一個字符縮短了很多。