数据压缩霍夫曼编码算术编码精品文稿.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《数据压缩霍夫曼编码算术编码精品文稿.ppt》由会员分享,可在线阅读,更多相关《数据压缩霍夫曼编码算术编码精品文稿.ppt(27页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数据压缩霍夫曼编码算术编码第1页,本讲稿共27页主要内容图像压缩编码简介Huffman编码算术编码简介算术编码原理算术编码的发展及应用第2页,本讲稿共27页一 图像压缩编码简介第3页,本讲稿共27页 霍夫曼编码霍夫曼编码(Huffman coding)根据给定数据集中霍夫曼(D.A.Huffman)在1952年提出和描述的“从下到上从下到上”的熵编码方法各元素所出现的频率来压缩数据的一种统计压缩编码方法。这些元素(如字母)出现的次次数越多数越多,其编码的位数就越少位数就越少广泛用在JPEG,MPEG,H.26X等各种信息编码标准中第4页,本讲稿共27页熵(entropy)按照香农(Shanno
2、n)的理论,在有限的互斥和联合穷举事件的集合中,熵为事件的信息量的平均值,也称事件的平均信息量事件的平均信息量(mean information content)(依概率平均依概率平均)用数学表示为熵是数据压缩的极限第5页,本讲稿共27页霍夫曼编码(1)计算该字符串的霍夫曼码步骤:按照符号出现概率大小的顺序对符号进行排序排序步骤:把概率最小概率最小的两个符号组成两个符号组成一个节点P1步骤:重复重复步骤,得到节点P2,P3,P4,PN,形成一棵树,其中的PN称为根节点步骤:从根节点PN开始到每个符号的树叶,从上到下 标上0(上枝)和1(下枝),至于哪个为1哪个为0则 无关紧要,但通常把概率大的
3、标成1,概率小的 标成0.(标记标记)步骤:从根节点PN开始顺着树枝到每个叶子分别写出 每个符号的代码.(反向编码反向编码)第6页,本讲稿共27页霍夫曼编码霍夫曼编码举例1现有一个由5个不同符号组成的30个符号的字符串:BABACACADADABBCBABEBEDDABEEEBB计算(1)该字符串的霍夫曼码(2)该字符串的熵(3)该字符串的平均码长(4)编码前后的压缩比第7页,本讲稿共27页霍夫曼编码符号出现的次数 log2(1/pi)分配的代码 需要的位数B101.585?A81.907?C33.322?D42.907?E52.585?合计30符号出现的概率符号出现的概率第8页,本讲稿共27
4、页霍夫曼编码符号B(10)A(8)E(5)D(4)C(3)P1(7)P2(12)P3(18)P4(30)01101010代码代码B(11)A(10)E(00)D(011)C(010)第9页,本讲稿共27页霍夫曼编码符号出现的次数log2(1/pi)分配的代码需要的位数B101.5851120A81.9071016C33.3220109D42.90701112E52.5850010合计306730个字符组成的字符串需要个字符组成的字符串需要67位位5个符号的代码第10页,本讲稿共27页霍夫曼编码(2)计算该字符串的熵计算该字符串的熵 其中,是事件 的集合,并满足H(S)=(8/30)log2(3
5、0/8)+(10/30)log2(30/10)+(3/30)log2(30/3)+(4/30)log2(30/4)+(5/30)log2(30/5)=(44.313624.5592)/9.0308 2.1874 (Sh)理论上可获得的压缩比为:理论上可获得的压缩比为:3:2.1874=1.37第11页,本讲稿共27页霍夫曼编码(3)计算该字符串的平均码长平均码长:(28210333425)/30 2.233 位/符号 压缩比压缩比:90/67=1.34:1 平均码长:平均码长:67/30=2.233位位(4)计算编码前后的压缩比计算编码前后的压缩比n编码前:5个符号需3位,30个字符,需要90
6、位n编码后:共67位第12页,本讲稿共27页算术编码简介算术编码(Arithmetic Coding):和霍夫曼编码不同,算术编码跳出。分组编码的范畴,从全序列出发,采用递推形式的连续编码不是将单个信源符号映射成一个码字,而是将整个输入符号序列映射为实数轴上0,1)区间内的一个小区间,其长度等于该序列的概率,再在该小区间选择一个代表性的二进制小数,作为实际的编码输出。第13页,本讲稿共27页算术编码算术编码(arithmetic coding)给已知统计信息的符号分配代码的数据无损数据无损压缩技术基本思想是用0和1之间的一个数值范围数值范围表示输入流中的一个字符(串),字符(串),而不是给输入
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据压缩 霍夫曼 编码 算术 精品 文稿
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内