霍夫曼Huffman编解码.docx

霍夫曼（Huffman）编解码1，概述为了减少信源输出符号序列中的剩余度、提高符号的平均信息量，对信源 输出的符号序列所施行的变换具体说，就是针对信源输出符号序列的统计特 性来寻找某种方法，把信源输出符号序列变换为最短的码字序列，使后者的各 码元所载荷的平均信息量最大，同时又能保证无失真地恢复原来的符号序列 信源编码的作用之一是设法减少码元数目和降低码元速率，即通常所说的数 据压缩：作用之二是将信源的模拟信号转化成数字信号，以实现模拟信号的 数字化传输最原始的信源编码就是莫尔斯电码，另外还有ASCII码和电报 码都是信源编码但现代通信应用中常见的信源编码方式有：Huffman编码、 算术编码、L-Z编码，这三种都是无损编码，另外还有一些有损的编码方式 信源编码的目标就是使信源减少冗余，更加有效、经济地传输，最常见的应 用形式就是压缩其中霍夫曼（Huffman ）编码是常用的一种编码方式2，霍夫曼编码思想霍夫曼（Huffman ）编码算法是满足前缀条件的平均二进制码长最短的编码 算法其编码思想是将较长的编码码字分配给较小概率的信源输出符号，而将 较短的编码码字分配给较大概率的信源输出算法是：在信源符号集合中，首 先将两个最小概率的信源输出合并为新的输出，其概率是两个相应输出符号概 率之和。

这一过程重复下去，直到只剩下一个合并输出为止，这个最后的合并 输出符号的概率为1这样就得到了一张树图，从树根开始，将编码符号1 和0 分 配在同一节点的任意两分支上，这一分配过程重复直到树叶从树根到树叶途 经支路上的编码最后就构成了一组异前置码，就是Huffman编码输出以下图为例：码字Wi信符S.i概率p(s.)i编码过程第一次第二次第三次W=01S10.40.4W=10S0.20.222W=111S0.20.233W=1101S0.1144W=1100S0.1 —0.255010.40.40.20.0.4A（1）通过上表的对信源缩减合并过程，从而完成了对信源的霍夫曼编码3、程序设计思路分为两步，首先是码树形成过程：对信源概率进行合并形成编码码树然后是码树回溯过程：在码树上分配编码码字并最终得到Huffman编码3.1、码树形成过程将信源概率按照从小到大顺序排序并建立相应的位置索引然后按上述规则 进行信源合并，再对信源进行排序并建立新的位置索引，直到合并结束在这 一过程中每一次都把排序后的信源概率存入矩阵G中，位置索引存入矩阵Index 中这样，由排序之后的概率矩阵G以及索引矩阵Index就可以恢复原概率矩阵 P了，从而保证了回溯过程能够进行下去。

3.2、码树回溯过程在码树上分配编码码字并最终得到Huffman编码从索引矩阵M的末行开始回 溯1） 在Index的末行2元素位置填入0和12） 根据该行索引1 位置指示，将索引1 位置的编码（‘1'）填入上一行的第一、第二元素位置，并在它们之后分别添加‘0'和‘1'3） 将索引不为‘1'的位置的编码值（‘0'）填入上一行的相应位置（第3 列）（4）以Index的倒数第二行开始向上，重复步骤（1）〜（3）,直到计算至Index的 首行为止4、程序说明及结果分析4.1 程序说明程序首先从文档abc .txt中读出要编码的信息源，为了便于分析，预先在 abc・txt文本中写好了 wearethefamil y的字符信息程序计算了信息源的概率分 布，并采用上面所述的方法对信息源进行霍夫曼编解码，计算了编码后的码长 和编码效率，同时还计算了霍夫曼编码的压缩率4.2 结果分析程序运行的结果:（1）文档中含有的字符种类个数为：112）字符和相应的概率分布字符aefh■ilmrtwy概0.140.210.070.070.070.070.070.070.070.070.07率29431414141414141414143） 信息源的平均信息量:3.32494） 霍夫曼编码的平均码长:3.35715） 所对应的编码:101 01 1000 1001 1110 1111 1100 1101 0010 0011 0006） 编码效率:0.9904编码前的信息源:霍夫曼解码后的信息:119119101101979711411410110111611610410410110110210297971091091051051081081211217）霍夫曼编码的压缩率为：0.4196从结果中可以看出霍夫曼编码对概率大的符号的编码长度短，概率小的符号 编码长度长，解码后的信息与原信息源是一致的，说明编解码正确，并且霍夫 曼编码的压缩率比较好。

5.总结哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件哈夫 曼压缩属于可变代码长度算法一族意思是个体符号（例如，文本文件中的 字符）用一个特定长度的位序列替代因此，文件中出现频率高的符号，使 用短的位序列，而那些很少出现的符号，则用较长的位序列但 Huffman 编 码是不唯一的.这是因为信源符号合并中遇到最小概率相同的情况时可任意选 择来做合并；在码树分配编码码字的时候1和0的位置可以是任意的。