数据压缩霍夫曼编码算术编码.pptxVIP

算术编码ArithmeticCoding

主要内容图像压缩编码简介Huffman编码算术编码简介算术编码原理算术编码的发展及应用

一图像压缩编码简介

231根据给定数据集中霍夫曼(D.A.Huffman)在1952年提出和描述的“从下到上”的熵编码方法各元素所出现的频率来压缩数据的一种统计压缩编码方法。这些元素(如字母)出现的次数越多，其编码的位数就越少广泛用在JPEG,MPEG,H.26X等各种信息编码标准中霍夫曼编码(Huffmancoding)霍夫曼编码

熵(entropy)熵是数据压缩的极限按照香农(Shannon)的理论，在有限的互斥和联合穷举事件的集合中，熵为事件的信息量的平均值，也称事件的平均信息量(meaninformationcontent)(依概率平均)用数学表示为

霍夫曼编码(1)计算该字符串的霍夫曼码步骤①：按照符号出现概率大小的顺序对符号进行排序步骤②：把概率最小的两个符号组成一个节点P1步骤③：重复步骤②，得到节点P2，P3，P4，……，

PN，形成一棵树，其中的PN称为根节点步骤④：从根节点PN开始到每个符号的树叶，从上到下

标上0(上枝)和1(下枝)，至于哪个为1哪个为0则

无关紧要，但通常把概率大的标成1，概率小的

标成0.(标记)步骤⑤：从根节点PN开始顺着树枝到每个叶子分别写出

每个符号的代码.(反向编码)

现有一个由5个不同符号组成的30个符号的字符串：BABACACADADABBCBABEBEDDABEEEBB计算该字符串的霍夫曼码该字符串的熵该字符串的平均码长编码前后的压缩比霍夫曼编码举例1霍夫曼编码

霍夫曼编码符号出现的次数log2(1/pi）分配的代码需要的位数B101.585?A81.907?C33.322?D42.907?E52.585?合计30符号出现的概率

霍夫曼编码符号B(10)A(8)E(5)D(4)C(3)P1(7)P2(12)P3(18)P4(30码B(11)A(10)E(00)D(011)C(010)

霍夫曼编码符号出现的次数log2(1/pi）分配的代码需要的位数B101.5851120A81.9071016C33.3220109D4252.5850010合计306730个字符组成的字符串需要67位5个符号的代码

霍夫曼编码(2)计算该字符串的熵

其中，是事件的集合，

并满足H(S)=(8/30)×log2(30/8)+(10/30)×log2(30/10)+

(3/30)×log2(30/3)+(4/30)×log2(30/4)+

(5/30)×log2(30/5)

=(44.3136－24.5592)/9.0308＝2.1874(Sh)理论上可获得的压缩比为：3:2.1874=1.37

平均码长：

＝(2×8＋2×10＋3×3＋3×4＋2×5)/30

＝2.233位/符号计算该字符串的平均码长编码前：5个符号需3位，30个字符，需要90位编码后：共67位压缩比:90/67=1.34:1平均码长：67/30=2.233位(4)计算编码前后的压缩比霍夫曼编码

和霍夫曼编码不同，算术编码跳出。分组编码的范畴,从全序列出发,采用递推形式的连续编码不是将单个信源符号映射成一个码字,而是将整个输入符号序列映射为实数轴上[0,1)区间内的一个小区间,其长度等于该序列的概率,再在该小区间选择一个代表性的二进制小数,作为实际的编码输出。算术编码(ArithmeticCoding)：算术编码简介

给已知统计信息的符号分配代码的数据无损压缩技术基本思想是用0和1之间的一个数值范围表示输入流中的一个字符（串），而不是给输入流中的每个字符分别指定一个码字实质上是为整个输入字符流分配一个“码字”，因此它的编码效率可接近于熵算术编码(arithmeticcoding)算术编码

算术编码算术编码(1)基本思想：基于递归概率区间划分的二进制编码．具体过程：①把信源符号序列{Xi|i=1,2,…,n}发生的概率用实数区间[0，1]上的间隔（Xi的取值范围）来表示②按符号概率大小来分配符号间隔，使[0，1]随迭代计算次数的增加而逐次变窄；③所求最后范围便是替代{Xi}符号串