哈夫曼编码及其应用论文

1、青岛农业大学本科生课程论文题 目：哈夫曼编码及其应用姓 名：学 院：专 业：班 级：学 号：指导教师：2012 年 06 月 27 日青岛农业大学课程论文任务书论文题目哈夫曼编码及其应用要求完成时间2012年 06月29日论文内容（需明确列出研究的问题）：研究哈夫曼编码的目的就是为了更深入的了解哈夫曼编码，更好的了解哈夫曼编码的作用，更 好地使用它解决现实生活中的问题。假设已知一个信源的各符号概 率，编写适当函数，对其进行哈夫曼编码，得出二进制码字，平均码 长和编码效率，总结此编码方法的特点和应用。资料、数据、技术水平等方面的要求 论文要符合一般学术论文的写 作规范，具备学术性、科学性和一定的

2、创造性。文字要流畅、语言要 准确、论点要清楚、论据要准确、论证要完整、严密，有独立的观点 和见解。内容要理论联系实际，计算数据要求准确，涉及到他人的观 点、统计数据或计算公式等要标明出处，结论要写的概括简短。参考 文献的书写按论文中引用的先后顺序连续编码。指导教师签名:哈夫曼编码及其应用信息与计算科学专业（姓名）指导教师（老师姓名）摘要：哈夫曼在1952年提出了一种构造最佳码得方法，我们称之为哈夫曼编码（Huffman Coding）。哈夫曼编码适用于多远独立信源,对于多元独立信源来说它是最佳码。但其存在的 不足直接制约了它的广泛应用。范式哈夫曼编码及译码算法的出现 解决了其应用的不足。 本文

3、主要介绍了哈夫曼编码及范式哈夫曼编码的诸多应用。关键词：哈夫曼编码；应用；范式哈夫曼编码；多元哈夫曼编码Huffman coding and its applicationStudent majoring in Information and Computing Science Specialty （英文名）Tutor（老师英文姓名）Abstract: in 1952 Huffman proposes a structure optimal coding method, we call the Huffman code （ Huffman Coding ）. Huffman coding ap

4、plied to how far the independent source for multiple independent sources, it is the optimal code. But its shortcomings directly restrict its wide application. Canonical Huffman coding and decoding algorithm, solves the shortcomings of the application. This paper mainly introduced the Huffman coding

5、and Huffman coding of many application paradigm.Key words : The Huffman code Application Canonical Huffman coding Multiple Huffman coding引言：哈夫曼编码（Huffman Coding）是一种编码方式，哈夫曼编码是可变字长 编码（VLC）的一种。Huffman于1952年提出一种编码方法，该方法完全依据字 符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就 叫做Huffman编码。哈夫曼编码的简单应用哈夫曼编码是一种编码方式，以哈夫曼树一即

6、最优二叉树，带权路径长度 最小的二叉树，经常应用于数据压缩。在计算机信息处理中，“哈夫曼编码”是 一种一致性编码法（又称熵编码法），用于数据的无损耗压缩。这一术语是指 使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编 码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出 现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使 编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种 方法是由David.A.Huffman发展起来的。例如，在英文中，e的出现概率很高， 而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时

7、，e极有可能 用一个位（bit）来表示，而z则可能花去25个位（不是26）。用普通的表示方法 时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一 般编码的1/8的长度，z则使用了 3倍多。倘若我们能实现对于英文中各个字母 出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。范式哈夫曼编码及其应用2.1概念介绍哈夫曼编码是一种最优的前缀编码技术，然而其存在的不足却制约了它的直 接应用。首先，其解码时间为O（lavg）,其中lavg为码字的平均长度；其次， 更为最重要的是，解码器需要知道哈夫曼编码树的结构，因而编码器必须为解码 器保存或传输哈夫曼编码树。对于小量数据的压

8、缩而言，这是很大的开销。因而， 应用哈夫曼编码的关键是如何降低哈夫曼编码树的存储空间Faller1973 提出 的自适应哈夫曼编码技术使哈夫曼编码树的存储空间降为零，即在使用某种约定 的情况下，解码器能动态地重构出和编码器同步的哈夫曼编码树，而不需要任何 附加数据。这样做的代价便是时间开销的增大。另一种技术是编码器和解码器使 用事先约定的编码树，这种方法只能针对特定数据使用，不具备通用性。另外一 种，也是最为常用的方法，便是范式哈夫曼编码。现在流行的很多压缩方法都使 用了范式哈夫曼编码技术，如GZIB、ZLIB、PNG、JPEG、MPEG等。范式哈夫曼编码最早由Schwartz1964提出，它

9、是哈夫曼编码的一个子集。其 中心思想是：使用某些强制的约定，仅通过很少的数据便能重构出哈夫曼编码树 的结构。其中一种很重要的约定是数字序列属性(numerical sequence property)，它要求相同长度的码字是连续整数的二进制描述。例如，假设码字 长度为4的最小值为0010，那么其它长度为4的码字必为0011, 0100, 0101, .； 另一个约定：为了尽可能的利用编码空间，长度为i第一个码字f(i)能从长度 为i-1的最后一个码字得出，艮阡f(i) =2(f(i-1)+1)。假定长度为4的最后一 个码字为1001，那么长度为5的第一个码字便为10100。最后一个约定：码字长

10、 度最小的第一个编码从0开始。通过上述约定，解码器能根据每个码字的长度恢 复出整棵哈夫曼编码树的结构。2.2码字构造假设有如下的码长序列：符号：a b c d e f g h ijk . u码长：3 4 4 4 4 4 4 4 4 5 5 . 5使用counti表示长度为i的码字的数目，firsti表示长度为i的第一 个码字的整数值。根据约定3,即first3 = 0可得到符号a的范式哈夫曼编 码为000。再根据约定2,可得到first4 = 2*(first3 + 1) = 2,进一步可 知b的编码为0010。由约定1可构造出符号c的编码为0011，由此类推可构造 出整个码字空间如下：a=0

11、00(0);f=0110(6);k=10101(21);b=0010(2);g=0111(7);.c=0011(3);h=1000(8);u=11111(31);d=0100(4);i=1001(9);e=0101(5);j=10100(20);其中 first3 = 0, first4 = 0010b = 2, first5 = 10100b = 202.3解法算法范式哈夫曼编码有一个很重要的特性：长度为i的码字的前j位的数值大于 长度为j的码字的数值，其中i j。如上例中的最小五位码10100，它的前四 位1010大于任何的四位码。由这个特性，很容易构造出范式哈夫曼编码的解码 算法：ext

12、ern KBitInputStream bs;int len = 1;int code = bs.ReadBit();while(code = firstlen)(code = firstlen，而不是 code firstlen；另外，len-不能少。代码中indexlen表示长度为len的第一个码字的索引，index3 = 0, index4 = 1, index5 = 9。不难发现，indexi= countiT+counti2+.+count1+count0，其中 count0 = 0。2.4其他特性对于长度为i的码字而言，counti = (2i)-firsti。其中等号仅对最 大长

13、度的码字成立。如果对于码字的最大长度imax，countimax (2imax)-firstimax，那么 称输入的码字长度序列为不完全集。三、多元哈夫曼编码在加密技术中的应用通过分析多元哈夫曼编码的基本原理，说明了对文件进行多元哈夫曼编码的 具体实现过程。在简单介绍文件加密的基础上，详细说明了用多元哈夫曼编码实 现文件加密的过程。并且通过不同进制的哈夫曼编码对同一文件的加密效果，说 明哈夫曼编码采用的进制越高，密文占用的存储空间越小。最后说明这种加密方 式大大增强了文件的安全性。四、Huffman编码在环保实时监测系统中的研究与应用数据压缩技术是实时数据传输系统研究的核心和重点之一，它对于减

14、少数据 所占用的存储空间，提高传输信道的利用率，增强传输数据的安全性具有非常重 要的作用。环保数据的在线监控要求系统要能够正确及时的接收数据，在系统的 开发过程中，测试发现当要求实时接收的数据量比较大的时候，容易发生数据丢 失，传输延迟，接收有误等现象。研究表明，为提高数据传输的实时响应速度，可采 用数据压缩算法对污染物数据进行压缩传输，能够较好地解决传输延迟，接收有 误的问题。哈夫曼编码是以D.A.Huffman在1952年发表的最小冗余代码的构 造方法为基本理论依据的编码，是一种基于概率模型的无损压缩编码。Huffman 编码作为一种通用、高效的数据编码方法在文本、图象、音频等方面有着广泛

15、的 应用。将哈夫曼编码应用于环保实时系统的数据接收中，可以利用其简洁高效的 编码解码效率，增强信道的传输速率,从而减少数据的传输延迟；同时，也在一定 的程度上提高了被传输数据的安全性。但是基于静态的Huffman编码算法对输入 的符号流进行编码，必须进行两次扫描，这使的静态Huffman编码在实际应用中 用的较少。因此，在本论文中，为了解决静态Huffman编码的缺点，本论文又研究 了自适应Huffman编码，它只需要对输入的符号流进行一次扫描即可，提高了算 法的效率；接着根据环保数据的传输标准CES-76标准，对传输的数据在编码前进 行了预处理，进一步加大了数据的压缩比例；同时结合系统的设计需求，采用了 JAVA的多线程处理机制来对上位机的发送数据进行接收，有效地减少了接收数 据的丢失率；最后通过增加缺失数据处理功能对一些因网络问题丢失的数据进行 弥补进一步完善了系统，并以主要代码和界面截图展示了系统。参考文献Faller, N. 1973. An Adaptive System for Data Compression. Record of the 7th Asilomar Conf. on Circuits, Sys