10、2.2 统计编码,统计编码 给已知统计信息的符号分配代码的数据无损压缩方法 编码方法 香农-范诺编码 霍夫曼编码 算术编码 编码特性 香农-范诺编码和霍夫曼编码的原理相同 ， 都是根据符号集中各个符号出现的频繁程度来编码 ， 出现次数越多的符号 ， 给它分配的代码位数越少 算术编码使用0和1之间的实数的间隔长度代表概率大小 ， 概率越大间隔越长 ， 编码效率可接近于熵,2021年3月23日,第2章 数据无损压缩,13 of 42,2.2.1 统计编码香农-范诺编码,香农-范诺编码(ShannonFano coding) 在香农的源编码理论中 ， 熵的大小表示非冗余的不可压缩的信息量 在计算熵时 ， 如果对数的底数用2 ， 熵 。

11、的单位就用“香农(Sh)” ， 也称“位(bit)”。
“位”是1948年Shannon首次使用的术语 。
例如,最早阐述和实现“从上到下”的熵编码方法的人是Shannon(1948年)和Fano(1949年) ， 因此称为香农-范诺(Shannon- Fano)编码法,2021年3月23日,第2章 数据无损压缩,14 of 42,2.2.1 香农-范诺编码,香农-范诺编码举例 有一幅40个像素组成的灰度图像 ， 灰度共有5级 ， 分别用符号A ， B ， C ， D和E表示 。
40个像素中出现灰度A的像素数有15个 ， 出现灰度B的像素数有7个 ， 出现灰度C的像素数有7个 ， 其余情况见表2-1 (1) 计算该图像可能获得的压缩比的理 。

12、论值 (2) 对5个符号进行编码 (3) 计算该图像可能获得的压缩比的实际值 表2-1 符号在图像中出现的数目,2021年3月23日,第2章 数据无损压缩,15 of 42,2.2.1 香农-范诺编码(续1,1) 压缩比的理论值 按照常规的编码方法 ， 表示5个符号最少需要3位 ， 如用000表示A ， 001表示B ， 100表示E ， 其余3个代码 (101 ， 110 ， 111)不用 。
这就意味每个像素用3位 ， 编码这幅图像总共需要120位 。
按照香农理论 ， 这幅图像的熵为,这个数值表明 ， 每个符号不需要用3位构成的代码表示 ， 而用2.196位就可以 ， 因此40个像素只需用87.84位就可以 ， 因此在理论上 ， 这幅图像的的压缩比为 。

13、120:87.841.37:1 ， 实际上就是3:2.1961.37,2021年3月23日,第2章 数据无损压缩,16 of 42,2.2.1 香农-范诺编码(续2,2) 符号编码 对每个符号进行编码时采用“从上到下”的方法 。
首先按照符号出现的频度或概率排序 ， 如A ， B ， C ， D和E ， 见表2-2 。
然后使用递归方法分成两个部分 ， 每一部分具有近似相同的次数 ， 如图2-1所示,2021年3月23日,第2章 数据无损压缩,17 of 42,2.2.1 香农-范诺编码(续3,3）压缩比的实际值 按照这种方法进行编码需要的总位数为30+14+14+18+1591 ， 实际的压缩比为120:911.32 : 1,图2-1 。

14、 香农-范诺算法编码举例,2021年3月23日,第2章 数据无损压缩,18 of 42,2.2.2 统计编码霍夫曼编码,霍夫曼编码(Huffman coding) 霍夫曼(D.A. Huffman)在1952年提出和描述的“从下到上”的熵编码方法 根据给定数据集中各元素所出现的频率来压缩数据的一种统计压缩编码方法 。
这些元素(如字母)出现的次数越多 ， 其编码的位数就越少 广泛用在JPEG, MPEG, H.26X等各种信息编码标准中,2021年3月23日,第2章 数据无损压缩,19 of 42,2.2.2 霍夫曼编码 Case Study 1,霍夫曼编码举例1 现有一个由5个不同符号组成的30个符 。

15、号的字符串：BABACACADADABBCBABEBEDDABEEEBB 计算 (1) 该字符串的霍夫曼码 (2) 该字符串的熵 (3) 该字符串的平均码长 (4) 编码前后的压缩比,2021年3月23日,第2章 数据无损压缩,20 of 42,2.2.2 霍夫曼编码 Case Study 1 (续1,符号出现的概率,2021年3月23日,第2章 数据无损压缩,21 of 42,2.2.2 霍夫曼编码 Case Study 1 (续2,1) 计算该字符串的霍夫曼码 步骤：按照符号出现概率大小的顺序对符号进行排序 步骤：把概率最小的两个符号组成一个节点P1 步骤：重复步骤 ， 得到节点P2 ， P3 ， P 。

16、4 ，PN ， 形成一棵树 ， 其中的PN称为根节点 步骤：从根节点PN开始到每个符号的树叶 ， 从上到下 标上0(上枝)和1(下枝) ， 至于哪个为1哪个为0则 无关紧要 ， 但通常把概率大的标成1 ， 概率小的 标成0 步骤：从根节点PN开始顺着树枝到每个叶子分别写出 每个符号的代码,2021年3月23日,第2章 数据无损压缩,22 of 42,2.2.2 霍夫曼编码 Case Study 1 (续3,符号 B (10) A (8) E (5) D (4) C (3,P1 (7,P2 (12,P3 (18,P4 (30,0,1,1,0,1,0,1,0,代码 B(11) A(10) E(00) D(011) C(0 。

17、10,2021年3月23日,第2章 数据无损压缩,23 of 42,2.2.2 霍夫曼编码 Case Study 1 (续4,30个字符组成的字符串需要67位,5个符号的代码,2021年3月23日,第2章 数据无损压缩,24 of 42,2.2.2 霍夫曼编码 Case Study 1 (续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) = 30lg30 (8lg8 10lg10。

来源：(未知)

【学习资料】网址：/a/2021/0323/0021755558.html

标题：PowerPoint|PowerPoint Presentation - 博客园( 二 )