|
编码方案 ． 编码和解码 数据压缩过程称为编码即将文件中的每个字符均转换为一个惟一的二进制位串 数据解压过程称为解码即将二进制位串转换为对应的字符 ． 等长编码方案和变长编码方案 给定的字符集C可能存在多种编码方案 （） 等长编码方案 等长编码方案将给定字符集C中每个字符的码长定为[lg|C|]|C|表示字符集的大小 【例】设待压缩的数据文件共有个字符这些字符均取自字符集C={abcdef}等长编码需要三位二进制数字来表示六个字符因此整个文件的编码长度为位 （）变长编码方案 变长编码方案将频度高的字符编码设置短将频度低的字符编码设置较长 【例】设待压缩的数据文件共有个字符这些字符均取自字符集C={abcdef}其中每个字符在文件中出现的次数(简称频度)见表 表 字符编码问题 字符 a b c d e f 频度（单位千次） 定长编码 变长编码 根据计算公式 (*+*+*+*+*+)*= 整个文件被编码为位比定长编码方式节约了约％的存储空间 注意 变长编码可能使解码产生二义性产生该问题的原因是某些字符的编码可能与其他字符的编码开始部分(称为前缀)相同 【例】设ETW分别编码为则解码时无法确定信息串是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 THuffmanCode H) {//根据哈夫曼树T求哈夫曼编码表H int cpi;//c和p分别指示T中孩子和双亲的位置 char cd[n+] //临时存放编码 int start //指示编码在cd中的起始位置 cd[n]=\ //编码结束符 for(i=i<ni++){ //依次求叶子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然后重新从根出发继续译码直至文件结束 文件的编码和解码算法【参见练习】 |
