查看“︁范氏霍夫曼編碼”︁的源代码

{{Unreferenced|time=2024-04-17T17:42:41+00:00}}
{{NoteTA
|G1=IT
|T=zh-hans:范氏霍夫曼編碼;zh-hant:範式霍夫曼編碼;
}}
'''範式霍夫曼編碼'''（{{lang-en|Canonical Huffman Code}}）是一種特殊的[[霍夫曼編碼]]，最早由Schwartz（1964）所提出。

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

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

== 演算法 ==
假設我們有一組[[霍夫曼編碼]]與其相對應的符號：<br>
 F：000<br>
 O：001<br>
 R：100<br>
 G：101<br>
 E：01<br>
 T：11<br>
<br>
首先我們先對符號進行排序，排序方式由
:'''1. 編碼長度短至長排列'''和
:'''2. 字母在英文單字中的次序'''<br>
 E：01<br>
 T：11<br>
 F：000<br>
 G：101<br>
 O：001<br>
 R：100<br> 
<br>
接著，照下列方式依序給予新的編碼：<br>
:1. 第一個符號的編碼方式是依照符號的編碼長度給予相同長度的'0'值<br>
:2. 對接下來的符號的編碼+1，保證接下來的編碼大小都大於之前<br>
:3. 如果編碼較長，位元左移一位並補0<br>
 E：01  →  00                 按照''1.'' <br>
 T：11  →  01                 依照''2.'' <br>
 F：000 → 100                 依照''2.''&''3.''<br>
 G：101 → 101                 依照''2.''<br>
 O：001 → 110                 依照''2.''<br>
 R：100 → 111                 依照''2.''<br>
<br>
依照上述演算法將霍夫曼碼變成範式霍夫曼碼。<br><br>
而解碼的方式可由：<br>
:1. 范式霍夫曼碼的順序（後面編碼大小必定大於前面）<br>
:2. 編碼長度為 <math>j</math> 的第一個符號可以從編碼長度為 <math>j-1</math> 的最後一個符號所得知，即 <math>c_{j} = 2(c_{j-1} +1 ) </math> 

{{压缩方法}}

[[Category:无损压缩算法]]