根据哈夫曼树求哈夫曼编码 树 - 哈夫曼树及其应用 - 哈夫曼编码 （一）

树 - 哈夫曼树及其应用 - 哈夫曼编码 （一）  

　　编码方案

　　 编码和解码

　　数据压缩过程称为编码 即将文件中的每个字符均转换为一个惟一的二进制位串

　　数据解压过程称为解码 即将二进制位串转换为对应的字符

　　 等长编码方案和变长编码方案

　　给定的字符集C 可能存在多种编码方案

　　( ) 等长编码方案

　　等长编码方案将给定字符集C中每个字符的码长定为[lg|C|] |C|表示字符集的大小

　　【例】设待压缩的数据文件共有 个字符 这些字符均取自字符集C={a b c d e f} 等长编码需要三位二进制数字来表

　　示六个字符 因此 整个文件的编码长度为 位

　　( )变长编码方案

　　变长编码方案将频度高的字符编码设置短 将频度低的字符编码设置较长

　　【例】设待压缩的数据文件共有 个字符 这些字符均取自字符集C={a b c d e f} 其中每个字符在文件中出现的次数

　　(简称频度)见表

　　表 字符编码问题

　　字符 a b c d e f

　　频度(单位 千次)

　　定长编码

　　变长编码

　　根据计算公式

　　( * + * + * + * + * + )* =

　　整个文件被编码为 位 比定长编码方式节约了约 %的存储空间

　　注意

　　变长编码可能使解码产生二义性 产生该问题的原因是某些字符的编码可能与其他字符的编码开始部分(称为前缀)相同

　　【例】设E T W分别编码为 则解码时无法确定信息串 是ET还是W

　　 前缀码方案

　　对字符集进行编码时 要求字符集中任一字符的编码都不是其它字符的编码的前缀 这种编码称为前缀(编)码

　　注意

　　等长编码是前缀码

　　 最优前缀码

　　平均码长或文件总长最小的前缀编码称为最优的前缀码 最优的前缀码对文件的压缩效果亦最佳

　　其中

　　p i 为第i个字符得概率

　　l i 为码长

　　【例】若将表 所示的文件作为统计的样本 则a至f六个字符的概率分别为 对变长编码

　　求得的平均码长为 优于定长编码(平均码长为 )