@ 2014.07.27 , 13:12

《硅谷》中那个很牛的算法是怎么来的?

[-]

相信不少人已经看过了HBO的《硅谷》,现在就要迎来第二季。故事讲述的是年轻的计算机天才Richard在硅谷创业公司的大潮中打拼的故事。他组建了魔笛手公司,向风投公司介绍了自己的软件。其实在《硅谷》这部喜剧里,魔笛手这款软件吸引了不少人。

《硅谷》的几位创剧人必须把剧中的这个牛逼软件设计的尽量合理。其实,一开始他们就已经定好了——一套通用压缩算法。这中算法可以应用在不同领域的不同产品中,是风投家门称为“深度科技”的核心科技。(其实最早这部剧的名字被定为《深度科技》)同时,创剧人需要一套外行观众不用费劲就能理解牛逼在哪的技术——那么压缩这个概念就很好,虽然做起来很麻烦,至少这个概念却很容易理解。

为了更真实地反映硅谷创业公司所经历的一切,几位创剧人还雇佣了一名有硅谷创业公司经验的技术顾问Jonathan Dotan。遗憾的是,Jonathan Dotan本人并不是压缩方面的专家,但是创剧人又希望剧中出现的技术尽可能真实。所以Dotan从Google拉来一名压缩方面的专家,还专门研究了斯坦福大学教授Tsachy Weissman所授的课程。

Dotan发了一封电子邮件给Weissman,希望和他聊一聊这部电视剧。向来不太爱理主动找上门的邮件的Weissman鬼使神差地点了进去,立刻被这个想法迷住了。很快他就想出了许多关于基因数据压缩算法、有损数据压缩、压缩去噪的点子,但是最后他还是回到了压缩界中最神秘的概念——一种比现有压缩算法效率更高,压缩比更高的神奇无损压缩算法,这种压缩算法可以应用在任何类型的数据上,并且支持搜索——这种压缩算法就和圣杯一样神秘,大家都知道它,但就是没人见过真货。

于是平时工作繁忙的Weissman邀请了自己的一名博士生Vinith Misra,两人共同为这个虚构算法添砖加瓦。

“我们要提出一种今天看来不可能的方法,但是又不能一眼看上去就觉得不可能,”Misra说,“也就是说,必须是一种专家看了也要思考一下才知道有问题的方法。”

Misra说为了创造出一套无损压缩算法,他先从有损数据压缩算法开始研究,原因只是因为这些算法会牵涉到数据转换,在白板上表达出来的话,视觉上更有吸引力。所以,他提出可以先用有损压缩法压缩源文件,然后计算解压缩出来的近似文件和源文件的差别,将损失的文件部分再次压缩,结合两者,就得到了无损压缩软件

Misra说虽然这样做比较可行,但是和标准无损压缩算法相比,效率还是不够高,因为错误编译并不比数据编译简单。所以粗看之下,这个想法还算有趣,至少经得起粗略分析。

但Misra没有满足于此,HBO《硅谷》的创剧人表示这套算法要在表现出算法领域的突破性提升,才能迎来这一季的大结局——魔笛手公司最大的竞争对手互利公司逆向工程还原了原始算法,并信誓旦旦扬言要击垮魔笛手。

不过创剧人对算法的突破性做了约束。结果新算法莫名其妙地要和middle out算法扯上关系,还要开一个玩笑。Misra后来提交了一份12页的数学分析,介绍了如何展开这个玩笑。

香农算法用树形结构编译模型数据,顺序是从根到叶。今天MP3和JPEG文件中用到的霍夫曼算法是通过从叶到根的顺序,所以表现更佳。LZW算法是从一端到另一端的数据流模式。Misra的算法,是从数据的中间部分向外压缩,同时逆向查找数据中的隐藏结构并压缩。

虽然这套算法在今天并不存在,但是Weissman说总有人会提出新的压缩方法,通过建立新的数据模型,会完全搅乱现在的压缩标准。

Misra和Weissman两人为HBO充实算法的工作还没有结束。剧中的工程师们会在以后面临新出现的竞争,所以为了击败竞争对手,他们还需要对算法进行进一步升级。

[-]

本文译自 IEEE,由译者 王大发财 基于创作共用协议(BY-NC)发布。


给这篇稿打赏,让译者更有动力 !
支付宝打赏 [x]
您的大名: 打赏金额:

3.5
赞一个 (6)

24H最赞