数据压缩结课论文.doc

霍夫曼(Huffman)编码目录摘要·································································2关键词·······························································2正文 ·······························································2霍夫曼编码的背景·················································2二元霍夫曼码的编码················································3r元霍夫曼（Huffman）码编········································6Huffman码的最佳性·················································7Huffman 码的优点和缺点···········································8霍夫曼（Huffman）编码摘要：随着科学技术的发展和需求，人们广发地致力于对各种文本、图片、语言、声音、活动图像和影视信号等实际信源进行了实用压缩方法和技术的研究，使信源的数据压缩技术得以蓬勃发展和走向成熟。

信源编码主要分为无失真信源编码和限失真信源编码香农第一定理告诉我们，信源的信息熵是是信源进行无失真编码的理论极限值，也就是说，总能找到某种合适的编码方法使编码后信源的信息传输率R’任意地逼近信源的信息熵而不存在任何失真故数据压缩技术中无失真信源编码又常称为熵编码熵编码中比较重要的一种编码方法叫霍夫曼编码那么，什么是霍夫曼编码呢？它又有什么用呢？它的产生给我们先辈们解决了什么问题呢？以下，我为大家一一讲解关键词：霍夫曼（Huffman）编码 码树 无损压缩正文：霍夫曼编码的背景1951年，霍夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试导师Robert M. Fano给他们的学期报告的题目是，寻找最有效的二进制编码由于他们无法证明哪个已有编码是最有效的，霍夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的霍夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树1952年，David A. Huffman在麻省理工攻读博士时所发明的，并发表于《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。

它是是可变字长编码(VLC)的一种，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码霍夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件霍夫曼压缩属于可变代码长度算法一族意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列二元霍夫曼码的编码其原理步骤如下：（1）将q个信源符号按概率分布P()的大小，以递减次序排列起来，设 （2）用0和1码符号分别分配给概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新符号，并用这两个最小概率之和作为新符号的概率，从而得到只包含q-1个符号的新信源，并称为S信源的缩减信源.（3）把缩减信源的符号扔以递减次序排列，再将其最后两个最小概率的信源符号合并成一个新符号，并用0和1码符号表示，这样又形成了q-2个符号的缩减信源4）依次继续下去，直至缩减信源最后只剩两个符号为止将这最后两个新符号用0和1码符号表示最后这两个符号的概率之和必为1然后从最后一级缩减信源开始，依编码路径由后向前返回，就得出各信源符号所对应的码符号序列，即得对应的码字。

下面举个例子说明这种编码方法例：离散无记忆信源, 的概率分别为0.4，,0.2，0.2,0.1,0.1其霍夫曼码如下表： 霍夫曼码的码树：r元霍夫曼（Huffman）码编码注意三点：(1) 将最小概率的r个符号分配码元2) 每次合并r个最小概率成为新信源，减少r - 1个符号3) 满足式才能充分利用短码——信源缩减次数，若不满足, 增加的概率项例：四元Huffman码， 补二项Huffman码的最佳性对于给定分布的任何信源，存在一个最佳即时码，此码满足以下性质：（1） 若(2) 两个最小概率的信源符号所对应的码字具有相同的码长3) 两个最小概率的信源符号对应的码字，除最后一位码元不同外，前面各位码元都相同Huffman码方法得到的码是即时码，不是唯一码，但是最佳码（即紧致码），它又有优点和不足之处Huffman 码的优点和缺点(1) 无失真编码效率高, , 常用于文件, 语音处理和图象处理的数据压缩.(2) 解决速率匹配问题，设备较复杂, 信源与信道间需增加缓冲寄存器, 变速入, 恒速出3) 克服误差扩散：限制霍夫曼码仅能应用于优质信道（<=10-6）以限制扩散的可能性4) 要求了解信源的统计分布。

(5) 算法复杂度随着信源符号串长度的增加而迅速增长Huffman编码是一种比较具体的和有效的无失真信源编码方法，它便于计算机软件和硬件的实现Huffman编码应用广泛,但主要用途是实现数据压缩，如JPEG、文件、语声处理、和图像处理等等就应用了Huffman编码参考资料：1、 电子工业出版社的《信息论与编码》；2、 电子工业出版社的《数据压缩》7。