数据压缩结课论文.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编码是一种比较具体的和有效的无失真信源编码方法，它便于计算机软件和硬件的实现。Huf