|
根据最优二叉树构造哈夫曼编码 利用哈夫曼树很容易求出给定字符集及其概率(或频度)分布的最优前缀码哈夫曼编码正是一种应用广泛且非常有效的数据压缩 技术该技术一般可将数据文件压缩掉%至%其压缩效率取决于被压缩文件的特征 具体做法 ()用字符c i 作为叶子p i 或f i 做为叶子c i 的权构造一棵哈夫曼树并将树中左分支和右分支分别标记为和; ()将从根到叶子的路径上的标号依次相连作为该叶子所表示字符的编码该编码即为最优前缀码(也称哈夫曼编码) 哈夫曼编码为最优前缀码 由哈夫曼树求得编码为最优前缀码的原因 ① 每个叶子字符c i 的码长恰为从根到该叶子的路径长度l i 平均码长(或文件总长)又是二叉树的带权路径长度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 H[i].ch=getchar();//读入叶子T[i]对应的字符 start=n; //编码起始位置的初值 c=i; //从叶子T[i]开始上溯 while((p=T[c].parent)>=0){//直至上溯到T[c]是树根为止 //若T[c]是T[p]的左孩子，则生成代码0;否则生成代码1 cd[--start]=(T[p).1child==C)?'0'：'1'; c=p; //继续上溯 } strcpy(H[i].bits，&cd[start]); //复制编码位串 }//endfor }//CharSetHuffmanEncoding 文件的编码和解码 有了字符集的哈夫曼编码表之后，对数据文件的编码过程是：依次读人文件中的字符c，在哈夫曼编码表H中找到此字符，若 H[i].ch=c，则将字符c转换为H[i].bits中存放的编码串。tW.WIngwIT.COM 对压缩后的数据文件进行解码则必须借助于哈夫曼树T，其过程是：依次读人文件的二进制码，从哈夫曼树的根结点(即T[m- 1])出发，若当前读人0，则走向左孩子，否则走向右孩子。一旦到达某一叶子T[i]时便译出相应的字符H[i].ch。然后重新从根出发 继续译码，直至文件结束。 文件的编码和解码算法【参见练习】。 |
