您的位置: 旅游网 > 女人

数据压缩结课论文多技术报告doc

发布时间:2018-11-08 15:48:58

数据压缩结课论文多技术报告doc

多技术报告 霍夫曼(Huffman)编码摘要:随着科学技术的发展和需求,人们广发地致力于对各种文本、图片、语言、声音、活动图像和影视信号等实际信源进行了实用压缩方法和技术的研究,使信源的数据压缩技术得以蓬勃发展和成熟。信源编码主要分为无失真信源编码和限失真信源编码。香农第一告诉我们,信源的信息熵是是信源进行无失真编码的理论极限值,也就是说,总能找到某种合适的编码方法使编码后信源的信息传输率R’任意地逼近信源的信息熵而不存在任何失真。故数据压缩技术中无失真信源编码又常称为熵编码。熵编码中比较重要的一种编码方法叫霍夫曼编码。那么,什么是霍夫曼编码呢?它又有什么用呢?它的产生给我们先辈们解决了什么问题呢?以下,我为大家一一。关键词:霍夫曼(Huffman)编码 码树 无损压缩正文:霍夫曼编码的背景1951年,霍夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师Robert M. Fano给他们的学期报告的题目是,寻找最有效的二进制编码。由于无法证明哪个已有编码是最有效的,霍夫曼放弃对已有编码的研究,转向新的探索,最终发现了基于有序频率二叉树编码的想法,并很快证明了这个方法是最有效的。霍夫曼使用自底向上的方法构建二叉树,避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。1952年,David A. Huffman在麻省理工攻读博士时所发明的,并发表于《一种构建极小多余编码的方法》(A Method for the Construction of Minimum-Redundancy Codes)一文。霍夫曼压缩是个无损的压缩算法,一般用来压缩文本和程序文件。霍夫曼压缩属于可变代码长度算法一族。意思是个体符号(例如,文本文件中的字符)用一个特定长度的位序列替代。因此,在文件中出现频率高的符号,使用短的位序列,而那些很少出现的符号,则用较长的位序列。二元霍夫曼码的编码其原理步骤如下:(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个最小概率成为新信源,减少个符号。 3 才能充分利用短码。――信源缩减次数,若不满足, 增加的概率项。例:四元Huffman码, 补二项Huffman码的最佳性对于给定分布的任何信源,存在一个最佳即时码,此码满足以下性质:(1) 若 2 两个最小概率的信源符号所对应的码字具有相同的码长。 3 字,除最后一位码元不同外,前面各位码元都相同。Huffman码方法得到的码是即时码,不是唯一码,但是最佳码(即紧致码),它又有优点和不足之处。Huffman 码的优点和缺点 1 无失真编码效率高, , 常用于文件传真, . 2 解决速率匹配问题,设备较复杂, 信源与信道间需增加缓冲寄存器, , 恒速出。 3 克服误差扩散:霍夫曼码仅能应用于优质信道( 4 要求了解信源的统计分布。 5 算法复杂度随着信源符号串长度的增加而迅速增长。Huffman编码Huffman编码,但主要用途是实现数据压缩如JPEG就应用了Huffman编码。2

猜你会喜欢的
猜你会喜欢的