搜索
青岛农业大学本科生课程论文题目：哈夫曼编码及其应用姓名：学院：专业：班级：学号：指导教师：2012年06月27日青岛农业大学课程论文任务书论文题目哈夫曼编码及其应用要求完成时间2012年06月29日论文内容（需明确列出研究的问题）：研究哈夫曼编码的目的就是为了更深入的了解哈夫曼编码，更好的了解哈夫曼编码的作用，更好地使用它解决现实生活中的问题。假设已知一个信源的各符号概率，编写适当函数，对其进行哈夫曼编码，得出二进制码字，平均码长和编码效率，总结此编码方法的特点和应用。资料、数据、技术水平等方面的要求论文要符合一般学术论文的写作规范，具备学术性、科学性和一定的创造性。文字要流畅、语言要准确、论点要清楚、论据要准确、论证要完整、严密，有独立的观点和见解。内容要理论联系实际，计算数据要求准确，涉及到他人的观点、统计数据或计算公式等要标明出处，结论要写的概括简短。参考文献的书写按论文中引用的先后顺序连续编码。指导教师签名：年月日哈夫曼编码及其应用信息与计算科学专业（姓名）指导教师（老师姓名）摘要：哈夫曼在1952年提出了一种构造最佳码得方法,我们称之为哈夫曼编码(HuffmanCoding)。哈夫曼编码适用于多远独立信源,对于多元独立信源来说它是最佳码。但其存在的不足直接制约了它的广泛应用。范式哈夫曼编码及译码算法的出现,解决了其应用的不足。本文主要介绍了哈夫曼编码及范式哈夫曼编码的诸多应用。关键词：哈夫曼编码；应用；范式哈夫曼编码；多元哈夫曼编码HuffmancodinganditsapplicationStudentmajoringinInformationandComputingScienceSpecialty（英文名）Tutor（老师英文姓名）Abstract:in1952Huffmanproposesastructureoptimalcodingmethod,wecalltheHuffmancode(HuffmanCoding).Huffmancodingappliedtohowfartheindependentsourceformultipleindependentsources,itistheoptimalcode.Butitsshortcomingsdirectlyrestrictitswideapplication.CanonicalHuffmancodinganddecodingalgorithm,solvestheshortcomingsoftheapplication.ThispapermainlyintroducedtheHuffmancodingandHuffmancodingofmanyapplicationparadigm.Keywords:TheHuffmancodeApplicationCanonicalHuffmancodingMultipleHuffmancoding引言：哈夫曼编码（HuffmanCoding）是一种编码方式，哈夫曼编码是可变字长编码（VLC）的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码。1.哈夫曼编码的简单应用哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称熵编码法），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由David.A.Huffman发展起来的。例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。2.范式哈夫曼编码及其应用2.1概念介绍哈夫曼编码是一种最优的前缀编码技术，然而其存在的不足却制约了它的直接应用。首先，其解码时间为O(lavg),其中lavg为码字的平均长度；其次，更为最重要的是，解码器需要知道哈夫曼编码树的结构，因而编码器必须为解码器保存或传输哈夫曼编码树。对于小量数据的压缩而言，这是很大的开销。因而，应用哈夫曼编码的关键是如何降低哈夫曼编码树的存储空间。Faller[1973]提出的自适应哈夫曼编码技术使哈夫曼编码树的存储空间降为零，即在使用某种约定的情况下，解码器能动态地重构出和编码器同步的哈夫曼编码树，而不需要任何附加数据。这样做的代价便是时间开销的增大。另一种技术是编码器和解码器使用事先约定的编码树，这种方法只能针对特定数据使用，不具备通用性。另外一种，也是最为常用的方法，便是范式哈夫曼编码。现在流行的很多压缩方法都使用了范式哈夫曼编码技术，如GZIB、ZLIB、PNG、JPEG、MPEG等。范式哈夫曼编码最早由Schwartz[1964]提出，它是哈夫曼编码的一个子集。其中心思想是：使用某些强制的约定，仅通过很少的数据便能重构出哈夫曼编码树的结构。其中一种很重要的约定是数字序列属性(numericalsequenceproperty)，它要求相同长度的码字是连续整数的二进制描述。例如，假设码字长度为4的最小值为0010，那么其它长度为4的码字必为0011,0100,0101,...；另一个约定：为了尽可能的利用编码空间，长度为i第一个码字f(i)能从长度为i-1的最后一个码字得出,即:f(i)=2(f(i-1)+1)。假定长度为4的最后一个码字为1001，那么长度为5的第一个码字便为10100。最后一个约定：码字长度最小的第一个编码从0开始。通过上述约定，解码器能根据每个码字的长度恢复出整棵哈夫曼编码树的结构。2.2码字构造假设有如下的码长序列：符号：abcdefghijk...u码长：34444444455...5使用count[i]表示长度为i的码字的数目，first[i]表示长度为i的第一个码字的整数值。根据约定3，即first[3]=0可得到符号a的范式哈夫曼编码为000。再根据约定2，可得到first[4]=2*(first[3]+1)=2，进一步可知b的编码为0010。由约定1可构造出符号c的编码为0011，由此类推可构造出整个码字空间如下：a=000(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);其中first[3]=0,first[4]=0010b=2,first[5]=10100b=202.3解法算法范式哈夫曼编码有一个很重要的特性：长度为i的码字的前j位的数值大于长度为j的码字的数值，其中ij。如上例中的最小五位码10100，它的前四位1010大于任何的四位码。由这个特性，很容易构造出范式哈夫曼编码的解码算法：externKBitInputStreambs;intlen=1;intcode=bs.ReadBit();while(code=first[len]){code=1;code&=(bs.ReadBit());len++;}len--;intindex=index[len]+(code-first[len]);intsym=table[index];其中while循环用于确定码长，这也是解码算法中至关重要的一步，确定码长的算法效率影响着整个解码算法的效率。比如说我们要解码100110100序列，当循环至len=4的时候，code等于1001，大于len[4]，因而循环继续，继续读取下一位，code=10011,len=5，小于len[5]=10100,所以循环结束，执行下面的len--代码，得到了正确的码字长度4。算法实现需要注意几点：一定要使用code=first[len]，而不是codefirst[len]；另外，len--不能少。代码中index[len]表示长度为len的第一个码字的索引，index[3]=0,index[4]=1,index[5]=9。不难发现，index[i]=count[i-1]+count[i-2]+...+count[1]+count[0]，其中count[0]=0。2.4其他特性对于长度为i的码字而言，count[i]=(2^i)-first[i]。其中等号仅对最大长度的码字成立。如果对于码字的最大长度imax，count[imax](2^imax)-first[imax]，那么称输入的码字长度序列为不完全集。三、多元哈夫曼编码在加密技术中的应用通过分析多元哈夫曼编码的基本原理,说明了对文件进行多元哈夫曼编码的具体实现过程。在简单介绍文件加密的基础上,详细说明了用多元哈夫曼编码实现文件加密的过程。并且通过不同进制的哈夫曼编码对同一文件的加密效果,说明哈夫曼编码采用的进制越高,密文占用的存储空间越小。最后说明这种加密方式大大增强了文件的安全性。四、Huffman编码在环保实时监测系统中的研究与应用数据压缩技术是实时数据传输系统研究的核心和重点之一,它对于减少数据所占用的存储空间,提高传输信道的利用率,增强传输数据的安全性具有非常重要的作用。环保数据的在线监控要求系统要能够正确及时的接收数据,在系统的开发过程中,测试发现当要求实时接收的数据量比较大的时候,容易发生数据丢失,传输延迟,接收有误等现象。研究表明,为提高数据传输的实时响应速度,可采用数据压缩算法对污染物数据进行压缩传输,能够较好地解决传输延迟,接收有误的问题。哈夫曼编码是以D.A.Huffman在1952年发表的《最小冗余代码的构造方法》为基本理论依据的编码,是一种基于概率模型的无损压缩编码。Huffman编码作为一种通用、高效的数据编码方法在文本、图象、音频等方面有着广泛的应用。将哈夫曼编码应用于环保实时系统的数据接收中,可以利用其简洁高效的编码解码效率,增强信道的传输速率,从而减少数据的传输延迟；同时,也在一定的程度上提高了被传输数据的安全性。但是基于静态的Huffman编码算法对输入的符号流进行编码,必须进行两次扫描,这使的静态Huffman编码在实际应用中用的较少。因此,在本论文中,为了解决静态Huffman编码的缺点,本论文又研究了自适应Huffman编码,它只需要对输入的符号流进行一次扫描即可,提高了算法的效率；接着根据环保数据的传输标准CES-76标准,对传输的数据在编码前进行了预处理,进一步加大了数据的压缩比例；同时结合系统的设计需求,采用了JAVA的多线程处理机制来对上位机的发送数据进行接收,有效地减少了接收数据的丢失率；最后通过增加缺失数据处理功能对一些因网络问题丢失的数据进行弥补进一步完善了系统,并以主要代码和界面截图展示了系统。参考文献[1]Faller,N.1973.AnAdaptiveSystemforDataCompression.Recordofthe7thAsilomarConf.onCircuits,SystemsandComputers(PacificGrove,Ca.,Nov.),593-597.[2]SchwartzE.S.KallickB,.Generatingacannonicalprefixencoding,CommunicationsoftheACM7(1964),166-169.课程论文成绩评定表学生姓名专业班级论文题目哈夫曼编