huffman編碼是即時碼嗎

第 84 篇原創

前言

霍夫曼編碼 （ Huffman coding ） 是一種可變長的字首碼。霍夫曼編碼使用的演算法是 David A。 Huffman 還是在MIT 的學生時提出的，並且在 1952 年發表了名為《 A Method for the Construction of Minimum-Redundancy Codes 》的文章。

編碼這種編碼的過程叫做

霍夫曼編碼

，它是一種普遍的熵編碼技術，包括用於無損資料壓縮領域。

霍夫曼編碼過程

霍夫曼編碼使用一種特別的方法為訊號源中的每個符號設定二進位制碼。出現頻率更大的符號將獲得更短的位元，出現頻率更小的符號將被分配更長的位元，以此來提高資料壓縮率，提高傳輸效率。

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

接下來，按照字元出現的比例從高往低對字元進行排序。

圖 1

然後，按出現比例低的順序查詢兩個字母。在這種情況下，它是 “ C ” 12。5% 和 “ D ” 12。5% 。

透過一條線連線兩個字母拼構成一個樹狀結果。將兩個字母合併為 “ C 或 D”，並將出現比率相加起來。

動畫 2

按照同樣的操作，將合併後的 “ C 或 D ” 視為一個字元，重複相同的操作。

在 “ A “ ”B“ ” C 或 D “ 三個中，按照出現比例低的順序查詢兩個字母。

圖 3

圖 4

這樣，所有的字母都變成了 ” A 或 B 或 C 或 D“ ，出現的比率為 100% 。

圖 4 就是霍夫曼編碼的樹結構。

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

圖 5

分配完畢後，從樹的根部遍歷每個字元並確定相應的程式碼。

在 ” A “ 的情況下，被分配的程式碼為 ” 0 “

在 ” B “ 的情況下，被分配的程式碼為 ” 10 “

在 ” C “ 的情況下，被分配的程式碼為 ” 110 “

在 ” D “ 的情況下，被分配的程式碼為 ” 111 “

動畫 6

就這樣，透過這樣的編碼規則， ” ABAABACD “ 的二進位制編碼就變成了 ” 01000100110111 “，只需要 14 個位元就能表示，比單純的使用 2 位元表示一個字元縮短了很多。

今日問題：

你還了解哪些編碼方式？