Episode 3 (Markov Chain Compression) - 1502120375
Last updated
Was this helpful?
Last updated
Was this helpful?
视频发布时间
2014年5月20日
视频介绍
Markov Chains Compression sits at the cutting edge of compression algorithms. These algorithms take an Artificial Intelligence approach to compression by allowing the encoder and decoder to 'predict' what data is coming next. In this episode Colt McAnlis talks about how these magical algorithms compress data, and why some think that they are the future of compression.
视频推介语
暂无，待补充。
翻译
润稿
终审
原始链接
中文字幕
翻译流水号
加入字幕组
周亿
——
——
1502120375
嗨 时髦的硅谷大叔
你在研究什么
呃 我在一个新的手机应用的想法
牛 赞一个
这么说你已经找到投资公司
很不错嘛
是奇思妙想设计网站公司
BING 猜对了
我迫不及待想看看你的协作智能算法
怎样帮助用户找到 啊 不是
你不是做这个的啊
呃 那个 我敢说你的压缩算法
很赞
我是说 压缩向第三世界国家传输的数据
信息的大小
不 也不是这个第三
好吧 那你会压缩的哪一块
你知道 今天是个重要的日子
不会 什么都不会
好吧 听着
别灰心
这还不算太糟
我是说你还可以做些弥补
你所需要做的就是
在马尔科夫链上下工夫
而且你分分钟就实现了压缩了
你懂的 马尔科夫链
从数学角度
在一个空间把一种状态转换到另一个状态
通常被认为占用很少内存
这种状态取决于目前的情况
而不是事件发生的顺序
使得应用能够遵循现实世界
统计模型的过程
不行
还是不会
你知道么
也许我们应该从头开始
但是不要害怕 年轻的硅谷嬉皮士
我就是来帮忙的
我是Colt McAnlis 这里是压缩头
瞬间移动 开始
现在我空余时间最喜欢做的事之一
就是提炼美国的伟大传统
并将它们绘制成图表
就拿棒球来说吧
虽然它看似一系列随机的动作
一对赢一队输
这事实上是个很简单的图表
我们来看一看 当一个击球手来到场地
他在这个地方击球
这时候只有两种情况
第一种 他可以用棒挥击 推击
或其他方式把球打出
或者是上垒
这个游戏最有趣的部分是
一旦你跑起来
无论你有没有上垒 那么你都得回去
然后另一个队员上场
最牛的是这些道理都是
显而易见的 不是么
在他们之间只有三种情况和两种转换
但如果我们想要通过这个图表把一些运动
传达给另一个人会怎么样呢
举个例子 击球手们上场 下场
然后上垒了
再来一次 然后又有一个下场
我们一直都在做的也是最简单的事情
就是假设每种情况是有限的符号
我们可以用两个字节来为每个符号编码
也就是说 我们有1 2 3 4 5 6
每一个符号占两个字节
即若我们想把这个发给某人
那么它的整个流量是大概12个字节
但是如果我们仔细观察
也许会有更好的方法来解决
如果我们不把每种状态指定为
可变字节长度
而是在每种状态转换之间指定字节编码
比如说 我们把0 1 0 0
放在这四个地方
这样 我们就能编码不同状态
之间的互相转换
只要编码器和解码器了解这些状态以及
我们在各个状态之间是怎样运行的就行了
如果这个假设成立的话
也就是说我们在对这种状态
进行编码
我们可以在5个字节内完成整个
流程的编码 这是不是很棒呀
但是我认为我们可以做的更好
你在看看我们这儿的这张图表
我们知道棒球的有些规则
是含蓄隐藏式的
我们不需要去编码
例如 一个击球手不管是上场还是下场
无论如何另一个击球手
也是要上场的
所以我们不需要这个流程中为他们编码
因此我们可以擦掉这个和这个
也就是说我们真正需要编码的唯一信息是
一个棒球队员上场
他是出场还是上垒
这个信息使得我们能够编码所有的符号数据
仅仅需要三个字节
所以从12个字节压缩到3个字节是至关重要的
我们这里所说的去编码状态间的转换
而不是编码每个具体的状态
并且某些状态是隐藏在
编码器和解码器的里的
也就是马尔科夫链的基本工作原理
但是这只是一个简单的例子
实际上要比这复杂的多
在1913 A A Markov通过数学和诗歌
发现了概率的一个新分支
Markov 花费了数小时
选择普希金文章中的
元音和辅音 模式
并于1913年1月23日发布了模型的详细说明
给定一个字母
那么它的下一个字母的概率
是一个有限的可循环的概率
你看大多数的时候 Markov是一个
非常爱管闲事的人 经常参与政治争斗
公众抗议
他在他的任何领域都喜欢和人竞争
事实上他花了很多的时间
在监狱大抡拳头
无论怎么说这个算法的发明者
现代硅谷的开创者
都不能诋毁他的功绩
你看 Markov的概率事件理念
严重的违背了当时的统计界
特别是抛掷硬币
投掷筛子
核心的是 马尔科夫链
帮助我们解决了关系概率的很多问题
比如 今天是下雨
那么两天之后下雨
下雨的概率是多少
在1913年 预测数学被当做
鸡肋
你能想象么
而今天马尔科夫链却是硅谷一些最大最复杂的大数据
算法的重要组成部分
这些从癌症研究到天气预报
再到模拟消费者行为
随处可甚至是能找出
圣何塞最美味的披萨
而最好的是 我们能够使用同样的算法
来组成这些大的算法或者是用来压缩
让我们来看一看
使用Markov 的理论 我们能够通过专注于
一个字母之后出现任何字母的这种转换关系
编码的一个字符串
这儿我们为了简便
我将把每组符号转换从新画成
一颗树的形状 每组中的第二个字母
作为树干第一个字母
作为子节点
为了给这个主题一个更好的术语解释
我们把每一组上下两个字母指定为从0开始的顺序
第一个字母用0表示
那么接下来的字母就用1表示
你们中专注画图的那些人
会问T与N同是指向0 为什么不都作为
第一组的子节点呢
对于用符号0 来表示每一组
确实0是接下来的字母
但事实上这么做事错的
我来告诉你们为什么
为了明白为什么 我们用简单的三个步骤
来给这一行字母从新编码 又叫二阶文
使用你的想法 来展示一阶文
现在 虽然这棵树看起来很有视觉震撼效果
非常讨人喜欢但它表示字符串构建却
表示的相当不准确
比如 这个图
允许你从T到一阶的0
然后从0到二阶的T 这样组成TOT
但实际上输入数据中却不存在
这当然就是错误的做法
正确的做法是把文章的转换
不共享
现在让我们向前延伸一下
看看在更长一些的字符串中如何使用一阶文
也就是每两个字符一对
你可以看到一个更真实的例子
改变了我们的分支 给了我们一个
不同的更错综复杂的
关系排列树 比如T, O和E
之后有多个
后续字母
如果我们要对这个例子编码
我们需要对这些
上下关系进行编码分配
问题是我们给一个关系
分配多少位呢
我们可以使用这些关系中所需要最大 的那个
在这个例子中 0阶中的0
有三个转换 但就是说
我们可以用2位来描述所有关系
当然 这样做有一些浪费
比如 我们只有一个转换关系的
不需要两位来描述
另外 每个节点我们还需要一些数来让
编译器知道有多少为需要读取
如果每个节点有16种关系而不是
两种会怎么样呢
正确是使用变长码来描述
这些关系
这样 用来描述关系的密码长度
就是可变的
具体的是由实际需要决定的
记住 可变长码要给可能性
最大 的分配短的编码
为了使压缩程度最大化
我们在分配密码时
必须把概率考虑在内 不过还好
在我们构建链的时候还是很容易实现的
这样做使得我们能够使用可变长码来正确进行编码
这样一个容易出错的地方
就是每个字符转换
从0阶到1阶的每个子分支
都有它自己的概率表
同样的 也有它自己的变长码
需要说明的是 你不是在根据
整个图建立变长码
不 不是
那样是错的
这 这些年出现了
巨大的马尔科夫链
比如 由Google开创者Larry Page和
Sergey Brin设计的Page Rank算法
就是基于马尔科夫链 其状态是
世界范围的网站页面 也许有400亿那么多
这些状态之间的转换
实际上就是页面之间的 链接
这个算法的目标就是弄清楚一个读者从一个链接
随机到达其他页面
每一个页面的具体概率是多少
为了使马尔科夫实际应用于压缩
我们需要更多地从科技眼光看问题
对于马尔科夫链来说
熵值和实际的实现方法
是完完全全不一样的
可惜的是
我不会这么说
让我们实际动手
看看具体是怎么回事
马尔科夫的效率很高 但是对于压缩
它 有一个巨大的缺陷
假设你想要对这个编码方式设计解码器
对于每个文本转换或者是父亲到儿子
的转换 你需要储存一个频率表
也就是字符和他对应的频率
这个数据也需要
在压缩数据中 这样解码器
才能正确解码
但是即便是对于这个简单的例子
这个过程的开销也是很大的
必须存储所有的频率数据
这样解码器才能够解码
对于这个流我们需要53字节
而原字符串才22字节
所以明显这么做一点用都没有
甚至变得更糟糕了 我们的数据更大了
或者是我们需要保存的文本更多了
重点是我们不能简单的把编码器的
百分比拿到解码器来解码数据流
我们需要把这 整个过程作为解码器
这样解码器解码数据将会产生
和编码器数据一样的
统计特性
假设我们要解码这个流
动态生成概率
同时马尔科夫链进行编码
我们从一个空的马尔科夫数据集开始的
我们从流中读取第一个字母 A
我们需要对它编码
不过我们不能编码 因为目前我们没有可用数据
因此 我们需要创建我们的树
树创建好了以后
我们需要用变长码对 A 进行编码
但是我们还是不能
因为我们一步需要分配给他概率
因为这是我们见到的第一个字母
我们给他100%
一旦我们有了概率 我们能够建出哈夫曼树
这样我们就能给字符 A 分配编码
因为我们的树里没有其他的东西
所以编码是0
我们开始读取第二个字母 B
我们依旧是第一次见到
我们需要把它作为一个符号按照它的概率
加入我们的树中
这时我们同样要更新我们文本中的
其他字符的概率
这是我们第二次看见 B
更新它在表中的概率
并且和A交换编码 这也是我们想要的
动态的更新概率
根据概率产生变长码
最棒的是我们不用转换流概率
只用编码就好了
然而我们尝试解码这个
我们就遇到了一个大问题
我们没有任何关于这些文字的信息
或者是用来构成二进制流的概率表
也就是说我们不能解码这个流
这不是你哥正确的编码
为了弥补这个 我们不得不
从新审视编码器 找到一个
正确的方法来输出文本 这样解码器就能够
实用他们来重构原始数据
我们第一次将 A 加入树的时候
我们需要想办法将 A 输出到编码流
这样我们的解码器就能够得到它
为了实现这个 我们增加一个新的流叫做文字流
每个字符仅仅8位用来记录
我们还没有见过的字母
我们现在需要告诉输出流
它需要从文本流读取符号
而不是一个可变长码
要做的这一点 我们引人了一个转义码的概念
转义码是一种特殊的字符
我们能够使用它使得解码器
知道什么时候读取一个文字
从我们的文本流
现在一个转义码并不像
A , B , C 一样是一个字符
但它的的确确存在我们的概率表中
所以它在编码是得到一个可变长码
不是从一颗空白树开始
每个新的文本节点初始化时
都被分配一个转义码并且是100%的概率
我们从字符流中读取 A
我们将它添加到文本中 更新我们的编码
输出转义码到二进制流
然后将A加入文本流
读取B再进行同样的过程
我们之前没有见过
我们输出了装义码的编码和文本值
接下来就是
见证奇迹的时刻了 孩子们
我们读取下一个B 它不是新的
我们之前已经见过了
需要特别注意的是
我们编码一个已经存在的字符时
要在更新统计和编码表
之前输出可变长码
一旦我们根据第二个 B 更新了表中的概率
比重改变 编码分配也改变了
这样编码器就看不到这样的变化
而这就坏事了
解码也是一样的
除非我们遇到一个装义码 它告诉我们
去从文本流中读取一个符号并且输出
首先 我们做的时从二进制流
读取变长码
如果你对这一部分不熟悉 回去看第一篇去
因为我们只有装义码
所以我们仅仅需要从流中读取一位
然后我们是在使用转义码
这就是在告诉我们应该从文本流中读取8位
然后放到输出流
然后更新我们的概率表
我们从二进制流中读取下一个0
也是变长码
我们知道要读取下一个文本
输出 然后更新
这时候 我们有了足够的信息
我们剩下两位从二进制流中读取的就和 B 匹配上了
我们将其输出
我们从输入流读取一个 A
发现它在表中
我们输出我们的编码到输出流
然后更新概率
但是因为我们在维护文本
我们需要在树中创建一个新分支
在这个天真的解决方案中
每阶的符号都有一个指向下一个文本的孩子
但是为了能够正确运作
我们不得不给后续的文本转义码
好消息是最基础的基本就是这样
然而 坏消息是
我们实际还是需要维护一个混合文本链
来得到正确合法的压缩
为了维护那个
我们再来看看编码器 然后
改一些工作方式
我们看见这一阶中
我们没有见过的字符
我们要使我们的链回到0阶
每次我们读取的一个0阶中
已存在的字符
我们都接着读取后续文本的
下一个字符
所以如果开始的字符 A, C
我们将A, C放入
文本以供编码
需要说明的是 我们将任何阶的新字符
都看做是一个全新的字符
如果我们编码是遇到一串A, B, C
而且是第一次遇到 那么我们发现
C是在B之后的
所以我们就把他当做0阶的来处理
输出到文本流
分配转义码
一旦完成了这一整套的编码
我们得到了最终的二进制流和文本流
这样就能传递给网上任何一个需要它的人
不需要去维护一个
单一的概率表
在这个解决方案中
原始串是88字节 而编码后的串是46字节
接近50% 非常的好
很明显 马尔科夫链
进行高效编码你需要去把握一个
独一无二的平衡
压缩需要的链的长度
和你进行压缩的系统
本身可用内存
早早的就耗尽内存
可不是什么好事
一个真正的编码器要解决这个平衡
是通过分开系统分内存的文件
然后把额外的文本写入磁盘
来找到最佳的解决方案
希望你现在在想
我们如何增加了
新的符号是适当调整
转义码时的概率
在我们这个小例子中
我们只是从中简单的减去第一个点
但在现实中并非如此简单
不幸的是这是另一个完全不同的系列
我们不会再这讲解
也就是说 自行Google吧
现在很多人认为马尔科夫链
将来会不可避免的用
用人工智能运行
在所有的数据压缩领域
显而易见
你看 维持一个多阶的马尔科夫链
就像在调试人工智能的
神经网络算法
当然 我们知道那么最成功的
马尔科夫链都是应用在
大数据上面的
现在也有轻量级的马尔科夫链
已经被应用在现代的压缩机
像7-zip LPack ZPack
很容易看出 未来人工智能
和云计算以一些奇怪的方式结合
将会产生一场数据压缩的变革
不过我们在40年内很难见到
而且这又是另外一说了
我是 Colt McAnlis 这里是压缩头
