如何把非均匀分布的信息实际用于压缩？
信息论 香农(Claude Shannon)
《A Mathematical Theory of Communication》 1948
05.07.2020
Multimedia Search Engine
13
压缩
信息论
消息(message)：收到的一个信息
压缩
为什么数据可以被压缩？
冗余的本质
数据交换的本质
从发送者向接收者传递信息
…… ……
05.07.2020
Multimedia Search Engine
5
压缩
为什么数据可以被压缩？
冗余的本质
数据交换的本质
从发送者向接收者传递信息 但是，如果接收者有一些先验知识……
……
…
05.07.2020
需要传递 预测器
反向预测器
的信息
实际传递的信息
获得的信息
预测模型
05.07.2020
Multimedia Search Engine
8
压缩
预测器
如何预测？
1 101001110……
0 如果正反出现的概率各50%？ 无法预测
05.07.2020
Multimedia Search Engine
9
压缩
上 0.63% 到 0.53% 人 0.53% 为 0.51% 会 0.48% 要 0.41% 一个 0.41% 说 0.40%
m 3.22% 22.82% j 0.15% 1.17%
后 0.40%
05.07.2020
Multimedia Search EngineFra bibliotek12压缩
预测器
输入数据的概率分布不是完全均匀的
2
压缩
为什么数据可以被压缩？
信息的表达形式有冗余
Die Freiheit, die Liebe,
生命诚可贵
Tun beide mir not:
爱情价更高
Mit Lust fü r die Liebe Geh' ich in den Tod,
若为自由故 两者皆可抛
Doch opfr' ich auch sie
05.07.2020
Multimedia Search Engine
17
压缩
IK sKpslogp1s 熵
信息论
信息的度量
报文中消息的平均信息量
报文中各个消息的出现概率是不同的！ 按概率加权 {0, 1}，分布{0.9, 0.1}
I(0)=0.15 bit, I(1)=3.32 bit (0.15*0.9+3.32*0.1)=0.467 bit 每收到一个这样的消息，获知0.467比特信息 可以压缩！
多媒体搜索引擎
多媒体文档及其内容理解(2)
多媒体信息的存储
压缩与编码
多媒体信息都很大
1百万字的小说：2MB 10分钟CD质量音频：100MB 10分钟普通电视质量视频：8.5GB
直接存储难以承受
如何节约存储空间？ 压缩
05.07.2020
Multimedia Search Engine
中 0.71%
r 7.51% 50.24% b 2.12% 15.70% t 7.46% 48.05% y 2.00% 15.15% o 7.12% 44.44% f 1.47% 10.22% n 6.41% 42.77% v 1.07% 8.24% s 5.55% 36.91% w 0.94% 7.15% l 5.52% 37.03% k 0.84% 6.37% c 4.74% 32.44% x 0.35% 2.72% u 3.66% 26.42% z 0.24% 1.66% p 3.27% 23.05% q 0.23% 1.85%
05.07.2020
Multimedia Search Engine
11
压缩
预测器
输入数据的概率分布不是完全均匀的
e 11.42% 64.52% d 3.13% 22.52%
是 1.72%
a 8.56% 54.08% h 2.76% 20.04%
有 0.84%
i 7.94% 50.39% g 2.30% 16.47%
预测器
如何预测？
1 101001110……
0 如果正面出现的概率90%？
预测正面出现：命中率90%
只需传递反面出现的情况
05.07.2020
Multimedia Search Engine
10
压缩
预测器
输入数据的概率分布不是完全均匀的
福尔摩斯：跳舞的小人
“你们也知道，在英文字母 中Ｅ最常见，它出现的次 数多到即使在一个短的句 子中也是最常见的。第一 张纸条上的十五个符号， 其中有四个完全一样，因 此把它估计为Ｅ是合乎道 理的……”
16
压缩
信息论
信息的度量
报文中消息的平均信息量
{0, 1}，均匀分布 I(0)=1 bit, I(1)=1 bit 平均信息量 1 bit
{0, 1}，分布{0.9, 0.1} I(0)=0.15 bit, I(1)=3.32 bit 平均信息量？ (0.15+3.32)/2=1.735 bit ??
Wenn die Freiheit bedroht!
05.07.2020
Multimedia Search Engine
3
压缩
为什么数据可以被压缩？
信息的表达形式有冗余
用典
“效田光故事” “二桃杀三士” “墨守成规”
05.07.2020
Multimedia Search Engine
4
Multimedia Search Engine
6
压缩
为什么数据可以被压缩？
冗余的本质
先验知识：可以更好地表示数据的模型
预测器
收到的信息
实际获得的信息
先验知识
05.07.2020
Multimedia Search Engine
7
压缩
为什么数据可以被压缩？
冗余的本质
先验知识：可以更好地表示数据的模型
1, 0 A, B, C, D, …… 天, 地, 玄, 黄…… 消息集
报文(sequence of messages):一串消息
05.07.2020
Multimedia Search Engine
14
压缩
信息论
香农：通信的模型
传递的“东西”：信息
如何度量？
05.07.2020
Multimedia Search Engine
15
压缩
信息论
信息的度量
单个消息的信息量
Islog
1
ps
自信息
消息s出现的概率
符号集大小？
如果正反概率相等： I(正)=log(1/0.5)=log(2) 如果底为2，则： I(正)=1 比特(bit)
对数底？ 与信息量的单位有关
05.07.2020
Multimedia Search Engine