I(0)=0.15 bit, I(1)=3.32 bit (0.15*0.9+3.32*0.1)=0.467 bit 每收到一个这样的消息，获知0.467比特信息 可以压缩！
压缩
信息论
{0, 1}，分布{0.9, 0.1} 如何压缩？
如果最小输出信息单位是1比特 如果输入信息必须以单比特处理 每个输入比特至少需要一个输出比特
压缩
霍夫曼码(Huffman Coding)
Байду номын сангаас 前缀码
非前缀码会导致译码困难
多媒体搜索引擎
多媒体文档及其内容理解(2)
多媒体信息的存储
压缩与编码
多媒体信息都很大
1百万字的小说：2MB 10分钟CD质量音频：100MB 10分钟普通电视质量视频：8.5GB
直接存储难以承受
如何节约存储空间？ 压缩
压缩
为什么数据可以被压缩？
信息的表达形式有冗余
Die Freiheit, die Liebe, Tun beide mir not: Mit Lust fü r die Liebe Geh' ich in den Tod, Doch opfr' ich auch sie Wenn die Freiheit bedroht!
{0, 1}，分布{0.9, 0.1} I(0)=0.15 bit, I(1)=3.32 bit 平均信息量？ (0.15+3.32)/2=1.735 bit ??
压缩
IK sKpslogp1s 熵
信息论
信息的度量
报文中消息的平均信息量
报文中各个消息的出现概率是不同的！ 按概率加权 {0, 1}，分布{0.9, 0.1}
1.29/2=0.645 < 1 熵为0.467
编码
压缩
霍夫曼码(Huffman Coding)
按输入消息的概率分布，编制最佳的码书
码书(code book)：输入消息和输出码字的对应 关系
码字(code)：一个比特串
可以被正确译码
废话…… 前缀码
一个码书中，任何码字都不是别的码字的前缀
无法压缩 必须至少去除一个限制
压缩
信息论
{0, 1}，分布{0.9, 0.1} 如果输入信息可以联合处理多个bit
报文可以很长 {00, 01, 10, 11}{0.81, 0.09, 0.09, 0.01}
000, 0110, 10110, 11111 最短码长：1，最长码长：3 平均码长：0.81*1+0.09*2+0.09*3+0.01*3=1.29
生命诚可贵 爱情价更高 若为自由故 两者皆可抛
压缩
为什么数据可以被压缩？
信息的表达形式有冗余
用典
“效田光故事” “二桃杀三士” “墨守成规”
压缩
为什么数据可以被压缩？
冗余的本质
数据交换的本质
从发送者向接收者传递信息
…… ……
压缩
为什么数据可以被压缩？
冗余的本质
数据交换的本质
获得的信息
预测模型
压缩
预测器
如何预测？
1 101001110……
0 如果正反出现的概率各50%？ 无法预测
压缩
预测器
如何预测？
1 101001110……
0 如果正面出现的概率90%？ 预测正面出现：命中率90% 只需传递反面出现的情况
压缩
预测器
输入数据的概率分布不是完全均匀的
福尔摩斯：跳舞的小人
“你们也知道，在英文字母 中Ｅ最常见，它出现的次 数多到即使在一个短的句 子中也是最常见的。第一 张纸条上的十五个符号， 其中有四个完全一样，因 此把它估计为Ｅ是合乎道 理的……”
压缩
预测器
输入数据的概率分布不是完全均匀的
e 11.42% 64.52% d 3.13% 22.52%
是 1.72%
Islog
1
ps
自信息
消息s出现的概率
符号集大小？
如果正反概率相等： I(正)=log(1/0.5)=log(2) 如果底为2，则： I(正)=1 比特(bit)
对数底？ 与信息量的单位有关
压缩
信息论
信息的度量
报文中消息的平均信息量
{0, 1}，均匀分布 I(0)=1 bit, I(1)=1 bit 平均信息量 1 bit
中 0.71% 上 0.63% 到 0.53% 人 0.53% 为 0.51% 会 0.48% 要 0.41% 一个 0.41% 说 0.40% 后 0.40%
压缩
预测器
输入数据的概率分布不是完全均匀的
如何把非均匀分布的信息实际用于压缩？
信息论 香农(Claude Shannon)
《A Mathematical Theory of Communication》 1948
压缩
信息论
消息(message)：收到的一个信息
1, 0 A, B, C, D, …… 天, 地, 玄, 黄…… 消息集
报文(sequence of messages):一串消息
压缩
信息论
香农：通信的模型
传递的“东西”：信息
如何度量？
压缩
信息论
信息的度量
单个消息的信息量
从发送者向接收者传递信息 但是，如果接收者有一些先验知识……
……
…
压缩
为什么数据可以被压缩？
冗余的本质
先验知识：可以更好地表示数据的模型
预测器
收到的信息
实际获得的信息
先验知识
压缩
为什么数据可以被压缩？
冗余的本质
先验知识：可以更好地表示数据的模型
需要传递 预测器
反向预测器
的信息
实际传递的信息
a 8.56% 54.08% h 2.76% 20.04%
有 0.84%
i 7.94% 50.39% g 2.30% 16.47% 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% m 3.22% 22.82% j 0.15% 1.17%