@ 2014.07.27 , 13:12
28

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

[-]

相信不少人已经看过了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.0
赞一个 (5)

TOTAL COMMENTS: 28+1

  1. 2491666

    8834uha8mNEI3wNDj42bOGzgoaKiOuNiDioVtzJq7LwtfkrLjLR8GNszotPpqG8M7PrHYTL6Dq28kgX4HBxP/ccKtLr6LQMQ4Zj7eyNls5vKOiJkXkz7EA
    我更加好骑的是这个算法

    [381] XX [17] 回复 [0]
  2. 小九
    @3 years ago
    2491668

    作为文科生,觉得男主很萌就可以了~

    [10] XX [5] 回复 [0]
  3. 疯蓝
    @3 years ago
    2491669

    总有一个印度人

  4. 东东抢
    @3 years ago
    2491673

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

    似乎电池,艾滋病的研究,等等诸多科技都躺枪了

    [49] XX [0] 回复 [0]
  5. 蹲得脚发麻
    @3 years ago
    2491678

    有时候我会自卑地觉得自己还是个未开化的猿人——尤其是在煎蛋看到这些geek文时感觉尤其强烈

    [61] XX [4] 回复 [0]
  6. 2491679

    编剧倒是肯下血本啊

  7. dickMonday
    @3 years ago
    2491687

    是不是只有我一个人看过这部剧啊……如果没看过推荐你们看啊,超棒的

    [15] XX [2] 回复 [0]
  8. 2491688

    科技的发展总是将技术集中到少数人手中的 所以。。。人类的未来也是不确定的

  9. PassBy
    @3 years ago
    2491696

    @Stark: 看上去跟文章里介绍的算法原理一样。

  10. felyfely
    @3 years ago
    2491699

    压缩极限和绝对零度一样是不能突破的,他们的原始算法号称直接达到了压缩极限已经是很不可思议了,后来改进算法直接突破压缩极限直接可以把信息论的教材烧掉了。

    [37] XX [4] 回复 [0]
  11. 羽蛇神的回归
    @3 years ago
    2491703

    我们要提出一种今天看来不可能的方法,但是又不能一眼看上去就觉得不可能

    想到了那个传说中的π

    [12] XX [0] 回复 [0]
  12. 同尘
    @3 years ago
    2491710

    嗯 我看懂了 所以说那个算法是怎么来的?

  13. 2491713

    @felyfely:
    其实没有什么所谓的压缩极限
    就例如一个圆这么简单的图形
    就压缩了一个无限的恒定数π的数据
    在某些方面上来说这也是一个压缩方法
    压缩真正困难的不是压缩率
    而是有什么方法如何在一定短时间内把一个数据尽可能的压缩和解压缩
    不谈时间效率和普及性的压缩就是在耍流氓
    其实你想要的话
    你完全可以花一万年去分析
    把一个特定的超大的数据仅仅压缩成为一个几bit的公式
    但是这个压缩率几乎无限100%的方法又有什么意义呢?

    [15] XX [29] 回复 [0]
  14. Armstrong
    @3 years ago
    2491725

    @Stark: 还有有损和无损吧?

  15. 2491728

    不就是中出算法吗~~~~

  16. 2491735

    最近学习了压缩感知…感觉很有趣…可能成为未来压缩算法的方向

  17. Anubis
    @3 years ago
    2491737

    @dickMonday: 看得我尿都要笑出来了

  18. Anubis
    @3 years ago
    2491738

    @Stark: 说是有篇文献说这个算法其实有可能会压缩出来比源文件还要大,当然我对这个领域几乎都不了解所以没去证实,但是我粗略的想一下觉得还是有点可能的

  19. 2491743

    是我好久没看美喜剧了吗,觉得笑点槽点都很low

  20. 羽蛇神的回归
    @3 years ago
    2491782

    @zyfo2: 科技的发展总是将技术集中到少数人手中的,这句话是什么意思,如果想学的话谁都可以学啊,你对技术的看法不明确,应该说科技发展使得各行各业的技术量剧增,一个人不可能将所有技术全部学会,因此才会出现少部分人掌握少部分技术的现象,也就是说大多数人只掌握知识的一部分

  21. wxd356
    @3 years ago
    2491800

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

  22. raespsp
    @3 years ago
    2491853

    @Stark: 这个就是开启主角的灵感的金钥匙啊。看剧不认真/有意卖萌秀图。

  23. raespsp
    @3 years ago
    2491854

    HBO现在的两部喜剧,VEEP和这个,都棒极了。强烈推荐。

  24. 百得
    @3 years ago
    2491867

    压缩算法有许多种思路,但是它们基本上是公开的算法了,近二十年来没有什么重大的突破,普通的突破都没有。有的,只是各有侧重的变种而已。

  25. 小助手
    @3 years ago
    2491870

    这种认真的态度才是美剧好看的地方,可惜奉上面的命令,要全部禁掉,只能看看抗日神剧了

  26. browncoat
    @3 years ago
    2491902

    @Stark 撸管算法……

  27. devillzx
    @3 years ago
    2492339

    我非常想把在煎蛋里看到的很多有趣的东西分享给更多人看,比如朋友圈,空间

  28. wsxy162
    @1 year ago
    3189684

    @Stark:
    一看就知道是没学习过信息论的。

发表评论


24H最赞