huffman编码

缘起

Huffman编码树要从PFC（prefix-free code 无歧义前缀编码方案） 谈起.

我们考虑只包含5个字符的字符集 {‘A’, ‘E’, ‘G’, ‘M’, ‘S’} 的编码. 如果采用下面的编码方案的话,

字符 编码
A 00
E 01
G 10
M 11
S 111

那么请问如果译码机收到 111xxxx 这种字符串, 到底是将11译为M 还是将111译为S呢? 貌似还要看后面的. 但是译码之事，生死攸关, 怎么容许算法延迟? 所以我们需要提供一种只需要译码机顺序读取密文就可以无歧义的解码的算法. 这就要求编码方案有无歧义的特点. 符合这种特点的编码方案就是 PFC.

Read More