范氏霍夫曼編碼

范型霍夫曼编码(英语:Canonical Huffman Code)是一种特殊的霍夫曼编码,最早由Schwartz(1964)所提出。

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

而范型霍夫曼编码修正了这些缺点,借由一些原则以达成利用较少的数据便能还原霍夫曼编码的功能。范型霍夫曼编码要求相同长度编码必须是连续的,例如:长度为4的编码0001,其他相同长度的编码必须为0010、0011、0100...等等。为了尽可能降低存储空间,编码长度为的第一个符号可以从编码长度为的最后一个符号所得知,即,例如:从长度为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. 编码长度为   的第一个符号可以从编码长度为   的最后一个符号所得知,即