青岛农业大学
本科生课程论文
                   
题    目：      哈夫曼编码及其应用         
姓    名：                               
学    院：                             
专    业：                             
班    级：                             
学    号：                             
指导教师：                           
2012  年  06  月  27  日
青岛农业大学课程论文任务书
论文题目                哈夫曼编码及其应用                                     
要求完成时间            2012年  06 月 29 日                                       
论文内容（需明确列出研究的问题）：    研究哈夫曼编码的目的就是为了更深入的了解哈夫曼编码，更好的了解哈夫曼编码的作用，更好地使用它解决现实生活中的问题。假设已知一个信源的各符号概率，编写适当函数，对其进行哈夫曼编码，得出二进制码字，平均码长和编码效率，总结此编码方法的特点和应用。                         
                                                                 
                                                                 
                                                                 
                                                                 
哈夫曼编码树的带权路径长度                                                               
资料、数据、技术水平等方面的要求  论文要符合一般学术论文的写作规范，具备学术性、科学性和一定的创造性。文字要流畅、语言要准确、论点要清楚、论据要准确、论证要完整、严密，有独立的观点和见解。内容要理论联系实际，计算数据要求准确，涉及到他人的观点、统计数据或计算公式等要标明出处，结论要写的概括简短。参考文献的书写按论文中引用的先后顺序连续编码。                         
                                                                 
                                                         
                                                           
                                                           
指导教师签名：                            年      月    日
哈夫曼编码及其应用
信息与计算科学专业    （姓名）
指导教师  （老师姓名）
摘要：哈夫曼在1952年提出了一种构造最佳码得方法,我们称之为哈夫曼编码(Huffman Coding)。哈夫曼编码适用于多远独立信源,对于多元独立信源来说它是最佳码。但其存在的不足直接制约了它的广泛应用。范式哈夫曼编码及译码算法的出现, 解决了其应用的不足。本文主要介绍了哈夫曼编码及范式哈夫曼编码的诸多应用。
关键词：哈夫曼编码；应用；范式哈夫曼编码；多元哈夫曼编码
Huffman coding and its application
Student 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 applied 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 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编码。
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等。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。