数据压缩中未探索的领域

[译者注:本文原作者提出的三个数据压缩方面有些让人脑洞大开的感觉,如果对数据压缩原理很有兴趣的同学,建议看看这篇文章。]

Rich Geldreich 是我一个很厉害的同事,最近发表了一篇很有意思的文章,阐述了他对未来无损压缩技术的看法和见解。然后,我自己有些按捺不住了,也想谈谈我的看法~~ (嘿嘿,这正是互联网的魅力,不是么?)

在我看来,目前数据压缩领域比较热点研究点有两大块:

第一大块是找编解码性能和数据压缩比的平衡点(比如LZHAM、Brotli、LZFSE这些压缩算法)。从实用角度看,这个出发点毫无疑问是没问题的。而且我认为这正是数据压缩系统的价值所在,所以,往这个方向努力的确是正确的。

第二大块是尝试将神经网络理论用在数据压缩领域中。当然,像ZPAQ[译者注:一种非常适合用来做增量压缩备份的压缩工具,官网]和其他的基于Context Mixing的编码算法并不适合开发人员做一些日常的压缩操作(主要是因为需要较大的内存和较长的执行时间),但在压缩比方面,这些压缩算法却代表着最前沿的技术。他们的原理就是只要提供足够多统计模型,Context Mixing算法就可以取得相当不错的压缩比。

(这是图的下标题)看到top15的大文本数据压缩工具都是基于Context Mixing算法的,而基于BWT的只能排进前20,是不是感到有些惊艳啊? [译者注:BWT基本原理是将字符串变成字符矩阵,然后对字符矩阵进行进行排序和变换,也是数据压缩领域的一个热点]

总而言之,目前在数据压缩领域的所有大动作都是针对我们已知的东西。基本上都是结合数据转换、基于统计特征的编码,以及 context mixing 算法去获得更好的结果

但是这些都没有戳中我的要点。

首先要承认所有这些工作都很棒,但是现在貌似有慢慢迷失数据压缩算法根本目标的趋势。有人说只要做到了某个程度就意味着压缩的问题被解决了,对于这种说法我是不买账的。最近已经关注了很多很多这方面的研究点(可能太多了),越看越感觉我们离“问题被解决”的程度还差很远很远:数据压缩领域还有很多大坑需要我们去填。

也许我马上列出的部分点有些太过于理论以至于根本不现实,甚或是看上去有些疯狂。但他们确实是我们现在的信息理论和数据压缩领域需要被关注的。

1 排列带来的难题

现代数据压缩理论是围绕统计特征来设计的,真的追溯起来估计有200年的历史了。这么多年下来,我们都没有另辟蹊径,提出一个新概念的。更糟糕的是,我们的思维都被固化在这上面了。

想想看,根据现代数据压缩理论,一般认为一旦统计信息被提取出来,我们根本没办法进行进一步压缩了。基本上就意味着,一旦我们完成了统计特征提取,这条路就走到头了。这种观点恰恰正是我们最大的死穴。

看看这个经典的排列 [5, 7, 1, 4, 6, 3, 2, 0] 。根据信息论,这个排列是不可压缩的:因为每个符号都出现了,而且没有重复出现的。从统计特征的角度看,我们只能做到这一步了。

一个排列,以及它的一种循环表示方法

像这样的排列,基于统计的编码算法(霍夫曼编码, arithmetic【译者注:这里不是算术的意思,是一种压缩编码算法】 , ANS) 都无能为力了。亦或者是更高层的数据转换算法也不行,比如LZ,BWT和RLE。 Delta压缩可能会表现好一些,但是实际应用中效果并不明显。针对二进制的Context Mixing可能表现会更好一些,前提是能将更长的bit序列映射到特定模式。

但基本上,我们现在所有数据压缩的理论模型遇到这样的排列时,都没能有更大作为。这方面的困难性导致几乎没人在研究它。

我可以很肯定的说,没人真的在乎这个课题,我的意思是想要在这样的排列面前取得突破性进展的概率非常非常低,所以大部分研究者都不会考虑这个问题。但在我看来,真的很奇怪,像排列这么简单的一个概念居然会对我们现有的数据压缩领域会有这么大的困难。

2 为什么没有更多类似于BWT的算法?

不知道为什么,我们现有的压缩体系大多数都被限定在了线性数据上。准确说来,所有压缩算法是在考虑以某种形式将信息的上下文组织起来,然后用这种组织方式来实现压缩,没有人真正考虑将数据流中的数据打乱的。

导致这一现象的原因是对顺序的编码是很困难的,需要额外的数据来支撑。意思就是如果我可以将要压缩的数据先排好序,那么所有算法都取得更好的压缩率。但是怎么将排序好的数据给恢复回去需要大量的数据来做辅助。而这些辅助数据就是上一小节中提到的经典排列(我们已经知道它有多难压缩了)。

BWT是目前最适用于人类基因组信息的压缩算法

我就是很奇怪为什么没有更多类似于BWT的算法。在字母排列领域,只有BWT独家一份。当然,也有少许算法对它做了一些修改,但是没有像LZ算法那样有90个变体。有没有其他对排序转换的算法呢?

坦白来说,这方面的多样性缺失是有它的道理的,连BWT的作者自己都说不清他们是如何找到这个算法的,所以我们也不能期望随便冒出来个工程师在未做大量尝试的情况下就能提出个类似的算法。

但是我的重点是,像这种类型的算法,不该只有BWT独家一份。就像有那么一句话说的:“无独有偶”,只是我们还没有发现罢了。

3 柯氏复杂性

[译者注:柯氏复杂性是一种衡量想要表达一个序列的复杂度的指标,这句话有点拗口,有兴趣的同学自行百度一下,想要更加深入了解的可以看看文章开头我给出的那篇文章]

熵不是一种很好的衡量手段,看看[0,1,2,3]和[0,3,1,2]这两个序列,他们的熵值一样,但是很明显我们可以看到其中有一个可以有更短的表示形式。

柯氏复杂性是个很有意思的衡量指标,简单来说,它是用来衡量你的数据有多大,可以用多大的程序来生成你需要的数据。这对于数据压缩领域来说是个新方向:怎么把这个思想用到数据流中,进而用到数据压缩算法中?

上图完全是由Fractal算法生成的,生成这个图片的程序非常非常小,比最好的

这是一个完全未被探索过的空间,只要我们能将数据块分割中多个部分,每个部分都可以用一个很小的程序来生成,那么所有程序的大小将比原来数据的体积小很多。但我估计这个想法有些过于科幻,就我所知的现有计算机能力而言,我不确定是不是能完成这样的任务。不过,不管怎样,这个想法还是挺激动人心的。

我们的路还很长

这三个问题告诉我们,数据压缩领域还没有达到“问题被解决”的程度,我们只是关注我们能做哪些事情,而不是这件事情本身有多少种可能性。事实上是还有很多需要探索的地方。信息理论知识理论而已,离真理还差很远。

而且,就像别人说的那样,理论就是用来被突破的。

打赏支持我翻译更多好文章,谢谢!

打赏译者

打赏支持我翻译更多好文章,谢谢!

任选一种支付方式

1 1 收藏 评论

关于作者:赵荣

the quieter you become, the more you are able to hear 个人主页 · 我的文章 · 11

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部