[浅谈哈夫曼编码]
姓    名：    杜宁
学    号：  09990572
2018年9月18日

浅谈哈夫曼编码
Introduction of Huffman Coding
哈夫曼编码(Huffman Coding)是是一种用于无损数据压缩的熵编码（权编码）算法，哈夫曼编码是可变字长编码(VLC)的一种。这种编码是David A. Huffman于1952年在麻省理工学院攻读博士时所发明一种编码方法，并发表于《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码。
1 哈夫曼编码的起源
1951年，哈夫曼和他在麻省理工学习信息论的同学需要选择是完成学期报告还是期末考试，而他们的导师Robert M. Fano给他们的学期报告的题目是，寻最有效的二进制编码。由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。
正是由于这个算法，使得哈夫曼超越了他那曾经和信息论创立者香农共同研究过类似编码的导师。哈夫曼使用自底向上的方法构建二叉树，从而避免了次优算法Shannon-Fano编码的最大弊端――自顶向下构建树。
在霍夫曼编码理论的基础上发展了一些改进的编码算法。其中一种称为自适应霍夫曼编码（Adaptive Huffman code）。这种方案能够根据符号概率的变化动态地改变码词，产生的代码比原始霍夫曼编码更有效。另一种称为扩展的霍夫曼编码（Extended Huffman code）允许编码符号组而不是单个符号。
同香农-范诺编码一样，霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。这是
因为这两种方法都自含同步码，在编码之后的码串中都不需要另外添加标记符号，即在译码时分割符号的特殊代码。当然，霍夫曼编码方法的编码效率比香农-范诺编码效率高一些。
２ 哈夫曼编码的原理
霍夫曼（Huffman）编码属于码词长度可变的编码类，是霍夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率。
由于经过哈夫曼编码法所编码出来的档案是具有唯一码性质的即时码,即各个相异字元所编码出的所元串并不相同,解码时能立即解出。因此，哈夫曼编码法的解码过程是即时且唯一的解码。由此可见，曼编码具有以下明显的特点：
1)编出来的码都是异字头码，保证了码的唯一可译性。
2)由于编码长度可变，因此译码时间较长,使得哈夫曼编码的压缩与还原相当费时。
3)编码长度不统一，硬件实现有难度。
4)由于“0”与“1”的指定是任意的,故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，影响编码效率与数据压缩性能。
由此可见,哈夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短;而对于出现频率低的,编码长度较长。
生成霍夫曼编码算法基于一种称为“编码树”（coding tree）的技术。
算法步骤如下：
1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。
2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。
3）重复第2步，直到形成一个符号为止（树），其概率最后等于1。
4）从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。
3 哈夫曼编码的压缩机理
以哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称“熵编码法”），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即哈夫曼编码树的带权路径长度8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。
4 哈夫曼编码的应用方向
借助哈夫曼编码独特的数据结构，使得该编码在计算机的很多领域都得到了应用。
在文件压缩方面，哈夫曼编码技术得到了充分应用，从图片压缩标准到矢量量化图像压缩算
法。有部分研究人员利用哈夫曼编码改进全文索引结构压缩算法，同时还有部分研究人员使用多元哈夫曼编码技术开发了一个对任意文件进行加密和解密的适用程序，以实现了对文件的安全保密。并通过分析不同进制的哈夫曼编码对同一文件的加密效果，说明哈夫曼编码采用的进制越高，密文占用的存储空间越小。
还有很多研究人员在哈夫曼编码技术基础之上，研究分析了基于动态哈夫曼编码的XML数据流压缩技术、基于哈夫曼编码的文本文件压缩技术和基于哈夫曼编码在Symbian平台下对文件压缩解压技术等。于此同时，很多研究人员还对现有的哈夫曼编码技术提出诸多改进意见。
5 总结
随着计算机硬件系统的发展，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如在银行查询存款、通过互联网查看新闻、远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。哈夫曼编码将会在各个领域发挥重要的作用，同时基于哈夫曼编码的研究也将逐步完善。

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