§5. 哈夫曼(Huffman)编码
哈夫曼编码是用于数据文件压缩的一个十分有效的编码方法，其压缩率通常在20％
～90％之间。哈夫曼编码算法使用字符在文件中出现的频率表来建立一个0,1串，以表
示各个字符的最优表示方式。下表给出的是具有100,000个字符文件中出现的6个不同
的字符的出现频率统计。
表 5.1 字符出现频率表
不同的字符 | a | b | c | d | e | f |
频率（千次） | 45 | 13 | 12 | 16 | 9 | 5 |
定长码 | 000 | 001 | 010 | 011 | 100 | 101 |
变长码 | 0 | 101 | 100 | 111 | 1101 | 1100 |
如果采用定长码，则每个字符至少需用三位，该文件总共需要300,000位；如果采用
上面所列变长码，则该文件需用
（45×1＋13×3＋12×3＋16×3＋9×4＋5×4）×1000＝224,000位，
总码长减少了25%。
一般的编码都是沿一个方向连续地写下0,1子串，比如从左到右、从上到下。解码
时也是以同样的方向逐字地搜索。为了使解码唯一，必须使用一个规则。前缀码即是一
种规则，它要求表示任何一个字符的0,1字串都不能是表示另一个字符的0,1字串的前
部。比如，若用01表示字符a，则表示其它字符的字串不能是具有形式：01…。可以
用一棵二叉树来表示前缀编码的数据结构。用树叶代表给定的字符，并将给定字符的前
缀码看作是从树根到代表该字符的树叶的一条道路。代码中每一位的0或1分
标签：编码,前缀,哈夫曼,字符,000,字串,Huffman From： https://blog.51cto.com/u_15815923/5743800