5.5.1.2 哈夫曼编码

教材导航 · 第5章

原书定位

印刷页P184起,对应PDF第196页。下文为目视整理的知识提要;完整内容见原书对照。

前缀编码要求任一码字都不是另一码字的前缀,可在编码树中用叶结点代表字符,实现逐位唯一译码。把字符频数作为叶权构造哈夫曼树,再用分支上的 0、1 标记形成码字,可得到最短总长度的二进制前缀编码。

编码总位数为 WPL,平均码长为 WPL/∑wiWPL/\sum w_i;定长编码需 ⌈log⁡2n⌉\lceil\log_2 n\rceil 位表示 nn 种字符。编码本身不一定唯一;只需前缀性质时也不必一定是最优哈夫曼编码。

图5.26 前缀编码

图5.26 前缀编码,原书P185。

图5.27 哈夫曼编码示例

图5.27 哈夫曼编码示例,原书P185。

对应练习

5.5 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P184,PDF第196页

原书对照,原书P185,PDF第197页

原书对照,原书P186,PDF第198页