数据压缩结课论文

《数据压缩结课论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、霍夫曼(Huffman)编码目录摘要·································································2关键词·······························································2正文·······························································2霍夫曼编码的背景·················································2二元霍夫曼码的编码················

2、································3r元霍夫曼（Huffman）码编········································6Huffman码的最佳性·················································7Huffman7码的优点和缺点···········································8霍夫曼（Huffman）编码摘要：随着科学技术的发展和需求，人们广发地致力于对各种文本、图片、语言、声音、活动图像和影视信号等实际信源进行了实用压缩方法和技术的研究，使信源的数据

3、压缩技术得以蓬勃发展和走向成熟。信源编码主要分为无失真信源编码和限失真信源编码。香农第一定理告诉我们，信源的信息熵是是信源进行无失真编码的理论极限值，也就是说，总能找到某种合适的编码方法使编码后信源的信息传输率R’7任意地逼近信源的信息熵而不存在任何失真。故数据压缩技术中无失真信源编码又常称为熵编码。熵编码中比较重要的一种编码方法叫霍夫曼编码。那么，什么是霍夫曼编码呢？它又有什么用呢？它的产生给我们先辈们解决了什么问题呢？以下，我为大家一一讲解。关键词：霍夫曼（Huffman）编码码树无损压缩正文：霍夫曼编码的背景1951年，霍夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导

4、师RobertM.Fano给他们的学期报告的题目是，寻找最有效的二进制编码。由于他们无法证明哪个已有编码是最有效的，霍夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。霍夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。1952年，DavidA.Huffman在麻省理工攻读博士时所发明的，并发表于《一种构建极小多余编码的方法》（AMethodfortheConstructionofMinimum-RedundancyCodes）一文。它是是可变字长编码(VLC)的一种，该方法完

5、全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。霍夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。霍夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。7二元霍夫曼码的编码其原理步骤如下：（1）将q个信源符号按概率分布P()的大小，以递减次序排列起来，设（2）用0和1码符号分别分配给概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新符号，并用这两个最小概率之和作为新符号的概率，从而得

6、到只包含q-1个符号的新信源，并称为S信源的缩减信源.（3）把缩减信源的符号扔以递减次序排列，再将其最后两个最小概率的信源符号合并成一个新符号，并用0和1码符号表示，这样又形成了q-2个符号的缩减信源。（4）依次继续下去，直至缩减信源最后只剩两个符号为止。将这最后两个新符号用0和1码符号表示。最后这两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径由后向前返回，就得出各信源符号所对应的码符号序列，即得对应的码字。下面举个例子说明这种编码方法。例：离散无记忆信源,的概率分别为0.4，,0.2，0.2,0.1,0.1。其霍夫曼码如下表：7霍夫曼码的码树：r元霍夫曼（Huffman）码

7、编码注意三点：(1)将最小概率的r个符号分配码元。(2)每次合并r个最小概率成为新信源，减少r-1个符号。(3)满足式才能充分利用短码。——信源缩减次数，若不满足,增加的概率项。例：四元Huffman码，补二项7Huffman码的最佳性对于给定分布的任何信源，存在一个最佳即时码，此码满足以下性质：（1）若(2)两个最小概率的信源符号所对应的码字具有相同的码长。(3)两个最小概率的信源符号对应的码字