Episode 1 (Variable Length Codes) - 1502120373
PreviousIntroducing Compressor Head - 1502120372NextEpisode 2 (The LZ77 Compression Family) - 1502120374
Last updated
Was this helpful?
Last updated
Was this helpful?
视频发布时间
2014年5月20日
视频介绍
Variable Length Codes have been at the heart of data compression algorithms since the early 1950s. Understanding compression algorithms means understanding how humans view and use data. Colt McAnlis walks through the creation of Information Theory.
视频推介语
暂无，待补充。
翻译
润稿
终审
原始链接
中文字幕
翻译流水号
加入字幕组
周亿
--
--
1502120373
数码时代欢乐多
很多年前我们就明显
已经进入了信息大爆炸时代
你看 在网上我们有很多的数据
图书 音乐 甚至是你喜欢的
电视节目 无论你在哪或者
你使用什么设备
都能够找到
现在 想想这个
我们讨论的是像Google或者是
百特这样的大公司YB级的信息量
每时每刻都在
全球互联网上传播
70年代后期以来 信息理论家和
计算机科学家已经利用压缩算法
有效减少了这类信息大小
保证互联网的畅通
这也是为何我们越来越多的听到
程序或者网站的数据大小
和转换率之间的关系
举个例子 用户不会访问一个
三秒不能加载的网站
也不会下载占用
额外空间的应用
精明的程序员需要控制好这些
这就意味着 要避免
仅仅使用压缩算法
而应该深入研究
了解你的数据 从全新的
有趣的角度使用压缩算法来取悦用户
但是年轻程序猿 不要怂
我在这就是来帮助你实现这一步的
我是Colt McAnlis 我将为大家讲解压缩算法
在1836年 美国发明家
Samuel F. Morse创造了一种
通过电线传送电子脉冲的方法
在电线的末端上
吸附着一个电磁铁
他和其他的物理学家发现
如果他们能够
使用电信号
去控制电磁铁
就能实现每个电脉冲到来时响铃一次
这样 电报系统应运而生
你看 这么做的目的就是为了通过
一种强大媒介实现
超远距离的自然语言发送
当然 他们需要找到一个方法
使得他们能够
从英文字母ABC
转换成点脉冲信号
·-··-
也就是这样产生了摩斯代码
他们分配这种代码的方式
实际上是根据字符
在英文中出现的频率
举个例子比如说e 英文单词中出现次数
最多的字母实际上被分配的是最短的编码
你得知道这样做是因为
必须有人坐在电报前
不停地敲 才能通过电线发送信号
他们都希望发送
一段电报的工作量最小
当然 其他的字符编码也都是
由它的出现频率决定的
编码越复杂的字符 出现的可能性就越低
而现代计算机
我们使用的是一种不同的编码
也就是所谓的binary code
binary code的长度是固定的
也就是说 我们有一组
二进制数
然后我们分配给每一个字符
一个固定长度的二进制数
比如 ASCII码的每个字符都是
使用的8位二进制数
当我们收到一串这样的二进制数时
我们就知道每次读8位
来确定具体是哪个字符
如果我们打算像摩斯一样
按照频率来重新分配一次 不好意思
事实上我们可以做得更好一些
我们把字符频率
考虑在内 并且使用
可变长度编码
我们将会
发现一些很有趣的事
比如在一段文章中c出现的可能性是80%
得到最短的编码
一个单独的0
这就是说我们不对每个字符
都分配一个8位二进制数作为编码
而是对每个字符分配的可变长度编码
在这个例子中这样做我们比之前优化了81%
这就是可变长度编码的定义
这也是我们今天将要进一步讨论的内容
现在看来你不能
只讨论压缩
而不去讨论信息论本身
而如果说起信息论
就不得不提一个人
Cloud不仅仅是在party上很赞
很擅长倒立
而且创建了现代信息论
Cloud的影响在于
他发现了信息内容和数据流
中的字符出现频率之间存在着相关性
现在他能够使用
这个对数函数
来得到数位结果
因此他能够有效地
发现包含在二进制数据中的信息内容
这一非常大胆的举动
实际上定义了信息论的工作方式
但是就我们而言 我们更感兴趣的是
他对于熵的定义
你看 把数据流中的
所有概率内容和信息内容加在一块
你就得到了熵的算法
大致来说
我们真正发现的是
熵实际是每个符号
所分配的二进制数的
最小平均值的估计值
没懂 不用怕 我们来快速的举一个例子
看看在实际中如何使用
看看再实际中如何使用
假设我们的数据流中仅有两个符号
他们出现的概率分别是P1和P2
你看尽管这两个符号的概率
尽管是0.5和0.5 但实际上的熵值确实1
基本上表明这个数据流每个符号
需要一个一位二进制数来表示 对吧
所以这两个字符 我们分别用0和1表示
非常好
现在我们调整概率
使得某一个字符的
出现概率比其他字符更大
我们发现概率
P1增大而P2减小
我们可以看到熵值因此变成了0.88
大致意思是 平均而言
数据流中每个符号需要0.88比特数来表示
这样很好 不是么
也就是使用变长码
一些编码长 一些编码短
再看这
如果我们把概率修改成0.99和0.01
那么熵值无限接近于0
也就是说我们将看到
很多的P0 而P1的编码很长
让我们更多的讨论一下这个
让我们做一个简单的假设
假设我们有四个字符 好么
每个字符出现的概率都是0.25
在这个条件下 熵值是2
所以我们至少需要用两位比特数
来表示数据流中的每个字符
也就是像这样
00 01 10和11
这差不多就是最基本的binary code工作方式
如果你知道每一位的二进制码
那么解码也是相当的简单
现在来更深一点的讨论熵
如果我们改变一些符号的出现概率
那么我们就会得到不同的熵
假设我们有一组数据 这组数据
由四种符号组成 出现的概率分别是
0.49 0.25 0.25和0.01
如果你用之前的熵值公式计算一下
那么你得到的值约为0.157
强调一下 这是一个平均值 对吧
也就是说 我们能够开始编制
变长码来实现压缩
因为我们只有在概率不同时
才能实现压缩
所以在这个例子中 A是出现次数最多的
应该得到最短的一位编码
一个一个的分配编码 那么最终我们就实现了压缩
记住熵实际上表示的是
数据流中平均每个字符需要的二进制数位
的最小值的最优估计
当然 这也就把我们引入了下一个知识点
如果你使用的
变长码进行压缩
那么你需要保证你分配的
最短编码给出现最频繁的字符
如果你没有遵守这个原则
那么你就不能实现压缩
这样不好不好
所以我们来看一下
如何将变长码实际应用于
你软件的数据编码和解码
假设我们有一个符号流ABC
当然 我们也有一个字符表
字符表将把你的字符ABC
和你分配的变长码对应起来
所以A的编码是0 B的是10 C的是11
编码其实是非常简单的
我们需要做的仅仅是从数据流中读取符号
找到符号所对应的二进制编码
然后将二进制编码输入到二进制流中
让我们看看具体是怎么操作的
我们从数据流中读取A
当然 A对应编码0
所以我们将0写入二进制流
接着我们读取B
我们通过简单的查找字符表
发现B的编码是10
我们接着输出1再输出0
最后一个C 编码是11
也是非常容易实现
就像我说的 编码过程
不是很难
我们把字符变成对应的二进制编码 这样就行了
但是解码却有一点点棘手
因为在解密的过程中
我们会从二进制流中读取数据
然后再来看我们读取的
二进制编码表示的是哪一个字符
这也是问题所在
因为我们的编码实际上是变长码
我们不知道一次读取多少位
让我们举个例子看看
我们有一个二进制流01011
我们从中读取一位
然后在字符表中查找
我们发现这第一个字符表示的是A 是吗
A的编码是0 我们从二进制流中读取的是0
所以我们可以把A输出
然后接着读取二进制流中的下一位
是一个1
问题出现了
我们不知道这表示的是B还是C
因为B和C的编码都是1开始的
也就是说我们需要再接着从
二进制流中读取一位
才能确定到底表示的是哪个字符
所以我们读取了10
我们可以看到10表示的是字母B
也就是我们从10解码出了一个B
然后我们像这样再来一次
我们接着读取一位
因为我们每次都需要从最小的公共部分开始
然后我们发现这也可能是
B或者C 我们需要再读取一位来进行配对确认
我们刚刚从二进制流读出的
其实是字母C
一切正常 我们的编码
和解码都非常的正确
但实际上是很难设计
创造出正确的变长码
事实上 在你将编码
分配给字符的时候 非常容易出错
而这将会使你的数据错得彻彻底底
假设我们已经做到了这一步
我们得到了和之前相同的二进制流
但是注意 我们给C分配了
不同的编码
现在是101而不是11
让我们开始解码 看看会发生什么
我们读取了一个0
我们知道这代表着A 一切都还很正常
很好 输出A 一切都还很正常
然而我们读取下一个 我们得到1 然后我们发现
这可能代表B也可能代表C 仍然没有出错
到这为止都很正常
然而 我们读取下一位0
我们仍然无法确定这是B还是C
我们不能得到一个确定的结果
如果看成10 应该表示B
但是这也可能表示C 因为如果我们
再读取一位 我们就能得到C的二进制编码101
我们现在所面临的问题是
我们使用的是变长码 我们不能确定1010
表示的是两个B还是表示的CA
这样就引出了
你在设计变长码时
需要遵守的一个规则
也就是所谓的前缀属性
更具体来说
一旦一个编码被分配给一个特定字符
那么没有其他的编码以这个编码作为开始前缀
所以如果我们有10作为B的编码
那么C的编码就不能用10作为开始
这会是我们在使用变长码时痛苦不堪
当然 这时你可能在想
变长码从哪来呢
它当然不是从天上掉下来
掉进你的电脑里给你编码
说到这个 我们就应该
介绍一下Peter Elias
他不只是一个著名的踢踏舞融合讲师
他还发明了beta编码
也就是我们今天现代binary code
像我们之前说的 binary code
并不是变长码
他们不满足前缀属性
但是Elias博士并不是在这就止步了
他实际上构建了一整套压缩编码
以适应各种各样的模式
刚开始创建编码时
你可以使用整数值
比如0到5 用来表示
你这一种代码里的字符
例如这种一元编码unary code
可能是我们见过的最简单的
符合前缀属性的可变长码
一元码的构造方式即是
被赋予了特定的索引 你实际上
在一个0之前追加了许多个1
举个例子 这下面这个5
你看我们用了四个1和一个0
4用了三个1和一个0
3用了两个1和一个0 依此类推
当然 因为这种特殊的构造方式
0实际上并没有表示值
Elias博士建立他的变长码时
主要是围绕特定的
分布概率建立的
一元代码的最优情况是
你的字符概率满足P的
方程P(n)=2^(-n)
如果你的字符频率
不满足这个规律
之后你所得到的二进制流
就会有一点点膨胀
也就是说得不到熵最优值得结果
但是一元编码并不是他唯一创造的东西
看这
我们还有伽马编码 可以看到
这是一种完全不同的编码方式
这主要是因为他们有着
不同的概率分布
同样还有三角编码 或者是其变体
他们本身的编码方式都是不同的
有这底部的这个怪物一样的概率
当然也有传说中的
欧米茄编码 复杂到你
难以举出一个
实际的例子
这就有点像大声喊伏地魔一样
不管怎样
回顾之前所述
我们选择使用哪种编码方式
来进行编码实际上取决于你字符集合的
概率以及你有多少种字符
针对这些条件挑选的编码方式
将会是你字符集合的最优编码方式
比如你现在有一些64-88之间的
唯一字符需要被编码
你可以发现如果概率匹配正确的话
使用欧米茄编码
能够得到最优的结果
当然如果你的欧米茄的概率值低
那么你可能需要伽马
或者是两者之间的某个值 那么你可能需要δ
这样的话我们发现了一个很有意思的问题
如果你的字符集不满足上面
任何一个这里已知的概率分布函数
应该怎么办呢
关于这个问题的解答 让我们看这
有上百个可变长编码可用
你看 我们有Schalkwijk编码
Phased-In编码 Punctured编码
Stout编码 斐波那契编码很多很多供你选择
或者你可用尝试一些不同的
直接根据你数据的概率构建
你自己的可变长码
让我们看看如何操作
在1951 当时David Huffman还是
麻省理工的学生 正在学习他的教授
给他安排的电子工程课
他需要写一堆东西
来解决一个很难的问题
或者是为他的期末考试而努力学习
为了实现自己的价值
David决定去解决问题
而不是去应付考试
他教授让他找到一种最有效的方式
去使用二进制码
表示字符 数字
和其他符号
当然 David决定咬牙做这个枯燥无比的事情
在数月的苦熬之后
他都要打算放弃了
事实上 他已经放弃了
打算扔掉所有的笔记
这时候 灵光一闪
他事后说 当纸击中
垃圾桶的一瞬间 他突然开窍
那时他发明的东西
被Donald Knuth认为是
我们所知的计算科学
和数据转换的最基本原理之一
David Huffman发现了一种方法
能够使用简单紧凑的二进制数表
二叉树呈现创造出任何概率的
可变长码
接着他就继续解决之前的问题
也就是把他的想法实现
之后 他使用了这种编码
让我们去看看
Huffman有一个极其棒
的发现就是使用表和
分配字符编码的之间关系
他发现如果
使用二叉树
他能够利用字符表中的概率信息
沿着二叉树的分支
创造出最优的二进制编码
好吧 让我们来构建一颗哈夫曼树
一般来说你知道字符集
还有每个字符的概率
第一步是排序
概率最高的
在最前
概率最低的在最后
这里我们要做的是
把数组最后两个出列
用他们构成一个新的节点
然后将新节点再入列
我们继续这样的操作
将所有的都取出
比较数组中的最后两个元素
然后用他们构建新值
再将新值放入数组
这时我们已经完全构建出了二叉树
使用这棵树构建哈夫曼编码
是非常简单的
我们只用根据需要
把0和1分配给左右分支
每个字符的可变长码
其实就是从节点
往根走所遇到的01值
比如A从节点到根
得到0
B从节点到根得到01
C从节点到根得到11
这就是使用
Huffman算法构建可变长码
的过程
这棵树也就是哈夫曼树
很容易理解 哪怕是一点点的
压缩差别也是很大的
对于一些简单的编码
比如统计编码
你可以使用变长码来压缩你的数据
当然 接下来要说的是在使用
这些变长码降低
熵值之前的
就能使用的
其他压缩算法
当然 这是另外一节的主题了
我是Colt McAnlis
谢谢收看
