范氏霍夫曼編碼 | 2021全台活動資訊網

範式霍夫曼編碼（CanonicalHuffmanCode）是一種特殊的霍夫曼編碼，最早由Schwartz（1964）所提出。資料的編解碼運作方式中，以霍夫曼編碼來舉例，編 ...

範式霍夫曼編碼（Canonical Huffman Code）是一種特殊的霍夫曼編碼，最早由Schwartz（1964）所提出。

資料的編解碼運作方式中，以霍夫曼編碼來舉例，編解碼器的其中一方必須要知道霍夫曼樹的結構資訊，以便還原。所以其中一方必須儲存或傳輸霍夫曼樹。傳統的霍夫曼編碼使用樹狀模型編碼，給出現機率或頻率較高的符號（Symbol）較短的編碼，以提高壓縮率。但是這個方式造成兩個極大的缺點，第一，每一個樹的節點都要儲存有關它的父節點與子節點等等相關資訊，如果符號集合的數量包含許多不同機率的符號，記憶體的負荷量會明顯增大許多。第二，霍夫曼樹的追蹤需要耗費極大的運算量。所以基於以上兩個論點，傳統的霍夫曼編碼是一種極為消耗儲存空間且沒有效率的方式。

而範式霍夫曼編碼修正了這些缺點，藉由一些原則以達成利用較少的數據便能還原霍夫曼編碼的功能。範式霍夫曼編碼要求相同長度編碼必須是連續的，例如：長度為4的編碼0001，其他相同長度的編碼必須為0010、0011、0100...等等。為了盡可能降低儲存空間，編碼長度為 j {displaystyle j} 的第一個符號可以從編碼長度為 j − 1 {displaystyle j-1} 的最後一個符號所得知，即 c j = 2 ( c j − 1 + 1 ) {displaystyle c_{j}=2(c_{j-1}+1)} ，例如：從長度為3的最後一個編碼100，可推知長度為4的第一個編碼為1010。最後，最小編碼長度的第一個編碼...