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

该【数据压缩霍夫曼编码算术编码 】是由【1354793****】上传分享，文档一共【27】页，该文档可以免费在线阅读，需要了解更多关于【数据压缩霍夫曼编码算术编码 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。算术编码
Arithmetic Coding
单击此处添加文本具体内容，简明扼要地阐述你的观点
图像压缩编码简介
01.
算术编码原理
04.
Huffman编码
02.
算术编码的发展及应用
05.
算术编码简介
03.
主要内容
CONTENTS
一 图像压缩编码简介
根据给定数据集中霍夫曼(. Huffman)在1952年提出和描述的“从下到上”的熵编码方法
各元素所出现的频率来压缩数据的一种统计压缩编码方法。这些元素(如字母)出现的次数越多，其编码的位数就越少
广泛用在JPEG, MPEG,
02
01
03
霍夫曼编码(Huffman coding)
霍夫曼编码
熵(entropy)
熵是数据压缩的极限
按照香农(Shannon)的理论，在有限的互斥和联合穷举事件的集合中，熵为事件的信息量的平均值，也称事件的平均信息量(mean information content) (依概率平均)
01
用数学表示为
02
霍夫曼编码
(1) 计算该字符串的霍夫曼码
步骤①：按照符号出现概率大小的顺序对符号进行排序
步骤②：把概率最小的两个符号组成一个节点P1
步骤③：重复步骤②，得到节点P2，P3，P4，……，  PN，形成一棵树，其中的PN称为根节点
步骤④：从根节点PN开始到每个符号的树叶，从上到下 标上0(上枝)和1(下枝)，至于哪个为1哪个为0则 无关紧要，但通常把概率大的标成1，概率小的 标成0.(标记)
步骤⑤：从根节点PN开始顺着树枝到每个叶子分别写出 每个符号的代码.(反向编码)
现有一个由5个不同符号组成的30个符号的字符串：BABACACADADABBCBABEBEDDABEEEBB
计算
该字符串的霍夫曼码
该字符串的熵
该字符串的平均码长
编码前后的压缩比
霍夫曼编码举例1
霍夫曼编码
霍夫曼编码
符号
出现的次数
log2(1/pi）
分配的代码
需要的位数
B
10

?
A
8

?
C
3

?
D
4

?
E
5

?
合计
30
符号出现的概率
霍夫曼编码
符号
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(010)
霍夫曼编码
符号
出现的次数
log2(1/pi）
分配的代码
需要的位数
B
10

11
20
A
8

10
16
C
3

010
9
D
4

011
12
E
5

00
10
合计
30
67
30个字符组成的字符串需要67位
5个符号的代码