范氏霍夫曼編碼

范型霍夫曼编码（英语：Canonical Huffman Code）是一种特殊的霍夫曼编码，最早由Schwartz（1964）所提出。

资料的编解码运作方式中，以霍夫曼编码来举例，编解码器的其中一方必须要知道霍夫曼树的结构信息，以便还原。所以其中一方必须存储或传输霍夫曼树。传统的霍夫曼编码使用树状模型编码，给出现几率或频率较高的符号（Symbol）较短的编码，以提高压缩率。但是这个方式造成两个极大的缺点，第一，每一个树的节点都要存储有关它的父节点与子节点等等相关信息，如果符号集合的数量包含许多不同几率的符号，存储器的负荷量会明显增大许多。第二，霍夫曼树的追踪需要耗费极大的运算量。所以基于以上两个论点，传统的霍夫曼编码是一种极为消耗存储空间且没有效率的方式。

而范型霍夫曼编码修正了这些缺点，借由一些原则以达成利用较少的数据便能还原霍夫曼编码的功能。范型霍夫曼编码要求相同长度编码必须是连续的，例如：长度为4的编码0001，其他相同长度的编码必须为0010、0011、0100...等等。为了尽可能降低存储空间，编码长度为$j$的第一个符号可以从编码长度为$j-1$的最后一个符号所得知，即$c_{j}=2(c_{j-1}+1)$，例如：从长度为3的最后一个编码100，可推知长度为4的第一个编码为1010。最后，最小编码长度的第一个编码必须从0开始。范型霍夫曼编码通过这些原则，便可以从每个编码还原整个霍夫曼编码树。

算法

假设我们有一组霍夫曼编码与其相对应的符号：

F：000

O：001

R：100

G：101

E：01

T：11

首先我们先对符号进行排序，排序方式由

1. 编码长度短至长排列和

2. 字母在英文单字中的次序

E：01

T：11

F：000

G：101

O：001

R：100
 

接着，照下列方式依序给予新的编码：

1. 第一个符号的编码方式是依照符号的编码长度给予相同长度的'0'值

2. 对接下来的符号的编码+1，保证接下来的编码大小都大于之前

3. 如果编码较长，比特左移一位并补0

E：01  →  00                 按照1. 

T：11  →  01                 依照2. 

F：000 → 100                 依照2.&3.

G：101 → 101                 依照2.

O：001 → 110                 依照2.

R：100 → 111                 依照2.

依照上述算法将霍夫曼码变成范型霍夫曼码。

而解码的方式可由：

1. 范式霍夫曼码的顺序（后面编码大小必定大于前面）

2. 编码长度为 $j$ 的第一个符号可以从编码长度为 $j-1$ 的最后一个符号所得知，即 $c_{j}=2(c_{j-1}+1)$