哈夫曼编码
编码方案
． 编码和解码 数据压缩过程称为编码 即将文件中的每个字符均转换为一个惟一的二进制位串 数据解压过程称为解码 即将二进制位串转换为对应的字符
． 等长编码方案和变长编码方案 给定的字符集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
． 前缀码方案 对字符集进行编码时 要求字符集中任一字符的编码都不是其它字符的编码的前缀 这种编码称为前缀(编)码 注意 等长编码是前缀码
．最优前缀码 平均码长或文件总长最小的前缀编码称为最优的前缀码 最优的前缀码对文件的压缩效果亦最佳
其中 pi为第i个字符得概率 li为码长 【例】若将表 所示的文件作为统计的样本 则a至f六个字符的概率分别为 对变长编码求得的平均码长为 优于定长编码(平均码长为 )
根据最优二叉树构造哈夫曼编码
利用哈夫曼树很容易求出给定字符集及其概率(或频度)分布的最优前缀码 哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术 该技术一般可将数据文件压缩掉 ％至 ％ 其压缩效率取决于被压缩文件的特征
． 具体做法 （ ）用字符ci作为叶子 pi或fi做为叶子ci的权 构造一棵哈夫曼树 并将树中左分支和右分支分别标记为 和 （ ）将从根到叶子的路径上的标号依次相连 作为该叶子所表示字符的编码 该编码即为最优前缀码（也称哈夫曼编码）
． 哈夫曼编码为最优前缀码 由哈夫曼树求得编码为最优前缀码的原因 ① 每个叶子字符ci的码长恰为从根到该叶子的路径长度li 平均码长(或文件总长)又是二叉树的带权路径长度WPL 而哈夫曼树是WPL最小的二叉树 因此编码的平均码长(或文件总长)亦最小 ② 树中没有一片叶子是另一叶子的祖先 每片叶子对应的编码就不可能是其它叶子编码的前缀 即上述编码是二进制的前缀码
． 求哈夫曼编码的算法 （ ）思想方法 给定字符集的哈夫曼树生成后 求哈夫曼编码的具体实现过程是 依次以叶子T[i]( ≤i≤n )为出发点 向上回溯至根为止 上溯时走左分支则生成代码 走右分支则生成代码 注意 ① 由于生成的编码与要求的编码反序 将生成的代码先从后往前依次存放在一个临时向量中 并设一个指针start指示编码在该向量中的起始位置（start初始时指示向量的结束位置） ② 当某字符编码完成时 从临时向量的start处将编码复制到该字符相应的位串bits中即可 ③ 因为字符集大小为n 故变长编码的长度不会超过n 加上一个结束符 \ bits的大小应为n+
（ ）字符集编码的存储结构及其算法描述 typedef struct { char ch //存储字符 char bits[n+ ] //存放编码位串 }CodeNode typedef CodeNode HuffmanCode[n] void CharSetHuffmanEncoding(HuffmanTree T HuffmanCode H) {//根据哈夫曼树T求哈夫曼编码表H int c p i;//c和p分别指示T中孩子和双亲的位置 char cd[n+ ] //临时存放编码 int start //指示编码在cd中的起始位置 cd[n]= \ //编码结束符 for(i= i<n i++){ //依次求叶子T[i]的编码 H[i] ch=getchar() //读入叶子T[i]对应的字符 start=n //编码起始位置的初值 c=i //从叶子T[i]开始上溯 while((p=T[c] parent)>= ){//直至上溯到T[c]是树根为止 //若T[c]是T[p]的左孩子 则生成代码 否则生成代码 cd[ start]=(T[p) child==C)? c=p //继续上溯 } strcpy(H[i] bits &cd[start]) //复制编码位串 }//endfor }//CharSetHuffmanEncoding 文件的编码和解码 有了字符集的哈夫曼编码表之后 对数据文件的编码过程是 依次读人文件中的字符c 在哈夫曼编码表H中找到此字符 若H[i] ch=c 则将字符c转换为H[i] bits中存放的编码串 对压缩后的数据文件进行解码则必须借助于哈夫曼树T 其过程是 依次读人文件的二进制码 从哈夫曼树的根结点(即T[m ])出发 若当前读人 则走向左孩子 否则走向右孩子 一旦到达某一叶子T[i]时便译出相应的字符H[i] ch 然后重新从根出发继续译码 直至文件结束 文件的编码和解码算法【参见练习】
lishixinzhi/Article/program/sjjg/201311/22941
