哈佛推出完美流算法，达30年来最优性能

译者 | 王纯超，编辑 | vincent，AI前线出品｜ ID：ai-front

AI 前线导读：“当水在击打你的脸时，你很难测量从消防水管中流出的水。在某种意义上，这正是分析流数据的挑战，这些数据以滔滔之势向我们涌来，不曾停歇。如果你在 Twitter 上看到推文，你可能想暂停一下，弄清趋势。但是，这办不到，所以，你需要找到一种方法来动态统计标签“。

执行这种在线计算的计算机程序称为流式算法程序。因为数据连续不断地流入，而数据量又非常之大，所以策略上，程序只记录数据的精髓，同时忽略其余信息。30 多年来，计算机科学家一直致力于构建更好的流算法。去年秋天，一支研究团队发明了一个完美的算法”。

哈佛大学计算机科学家 Jelani Nelson 表示：“我们开发出了一种新算法，同时也是各方面性能最好的算法”。他与丹麦奥胡斯大学的 Kasper Green Larsen、东北大学的 Hui Nguyen 以及哥本哈根大学的 Mikkel Thorup 是该算法的合著者。

这个一流的流算法的工作原理是，记住看到的一切，找出出现最多的内容。它表明，流数据分析似乎固有的折衷实际上是不必要的，也指出了通往战略遗忘新时代的道路。

趋势识别

任何监控持续更新的数据库的场景，流算法都是有用的。可能是，AT＆T 监控数据包，或者 Google 绘制无休止的搜索查询流图。在这些场景下，处理数据的实时问题而无需重新检查甚至记住所有数据的所有信息的方法很有用，甚至是必需的。

这里有一个简单的例子。想象一下，你有一连串的数字，你想知道迄今为止看到的所有数字的总和。在这种情况下，很明显，不用记住每一个数字，只需要记住一个值：运行过程中的总和。

但是，当你想要询问的数据问题变得更加复杂时，挑战变得越来越大。想像一下，不是计算总和，你想回答以下问题：哪些数字最常出现？可以使用什么样的捷径时刻保持一个答案，已经不太明显。

这个谜题被称为“频繁元素（frequent items）”或“高命中目标（heavy hitters）”问题。解决它的第一个算法是在 20 世纪 80 年代初由康奈尔大学的 David Gries 和得克萨斯大学奥斯汀分校的 Jayadev Misra 开发的。他们的项目在许多方面是有效的，但它不能处理所谓的“变更检测（change detection）”。它可以告诉你最常搜索的词条，但不能指出哪些词条的趋势上升。就 Google 而言，它可以识别出“维基百科”是一个最流行的搜索词条，但它却无法找出伴随着诸如飓风伊尔玛等重大事件而出现的搜索峰值。

“这是一个编码问题——你把信息编码成紧凑的概要信息，而试图提取出信息来恢复最初放入的数据”，华威大学计算机科学家 Graham Cormode 说道。

在接下来的 30 多年中，Cormode 和其他计算机科学家改进了 Gries 和 Misra 的算法。例如，一些新算法能够检测趋势词条，而另一些则能够对词条频繁出现的含义进行更细致的定义。所有这些算法都做出了权衡，比如牺牲速度来提高准确性或者加大内存消耗来增强可靠性。

这些做法主要依靠索引。想象一下，假如你要识别频繁的搜索词条。一种方法是为每一个英文单词分配一个数字，然后将该数字与另一个记录该词条被搜索次数的数字进行配对。也许“aardvark”索引为 17，并以（17，9）在数据库中出现，这意味着编号为 17 的词条已经被搜索了九次。这种方法使最频繁的词条唾手可得，因为在任何时候，你都确切地知道每个词条被搜索了多少次。

但它还是有不足——即算法要花费很多时间来梳理英语中的数十万个单词。

但是如果字典中只有 100 个单词呢？那么“翻遍字典中的每一个词就不会花那么长时间”，Nelson 说。

然而，字典中的单词数就是那么多。除非像新算法的作者所发现的那样，你可以把大字典分解成更小的字典，并找到一个聪明的方法把它们还原。

小数据

少量数据比大量数据易于跟踪。

例如，想象一下，正在监视一个介于零和 50,000,000 之间的数字流（类似于通过 IP 地址记录互联网用户的任务）。你可以使用 50,000,000 词的索引来跟踪这些数字，但是这样大小的索引作用不大。更好的方法是，将每个八位数字看作是连接在一起的四个两位数字。

假设你看到数字 12,345,678。一种节约内存的方法是把它分成四个两位数的块：12,34,56,78。然后你可以把每个块发送到计算词条频率的子算法：12 发送到算法一，34 发送到算法二，56 发送到算法三，而 78 发送到算法四。

每个子算法都维护自己的索引，由于每个算法都不会看到大于两位数的数字，所以每个索引只涉及 0 到 99。

这种拆分的一个重要特征是，如果大数字（12,345,678）在整个数据流中频繁出现，那么它的两位数组成部分也是如此。当你要求每个子算法来识别它看到的最多的数字时，算法一会吐出 12，算法二会吐出 34，依此类推。只需要在四个更短的列表中查找频繁词条，你就能够找到一个巨大列表中最常见的成员。

Nelson 说：“与其花费 5000 万单位的时间在整个空间循环，你只需要四个算法花费 100 个单位的时间。”

这种分治策略的主要问题是，虽然很容易将大数分成小数，但反过来却更棘手——要找出正确的小数来重组成大数是很困难的。

例如，想象一下，你的数据流频繁出现两个有共同数字的数字：12,345,678 和 12,999,999。两者都以 12 开头。你的算法将每个数字分成四个较小的数字，然后将每个数字发送到一个子算法。随后，你问每个子算法，“哪些数字出现最频繁？”算法一会说，“12 出现最多。”识别哪些八位数出现最频繁的算法无法分辨，所有的 12 都属于同一个八位数字，还是和这个例子一样，属于两个不同的数字。

Nelson 说：“我们面临的挑战是要弄清楚哪些两位数连接在一起。”

新算法的作者通过将每个两位数块与一个小标签打包在一起解决了这个难题，这个小标签不占用太多的内存，但是仍然可以让算法以正确的方式将两位数碎片重新组合在一起。

要简单地理解这种标记方式的工作原理，以 12,345,678 为例，将其分成两位数的块。但是这一次，在将每个块发送到其各自的子算法之前，使用一对唯一的标识号打包该块，以便能将这些块重新组合在一起。标记的第一位是块的名称，第二位是链接。这样，12,345,678 就变成了：

这里数字 12 名字为“0”，链接到名字为“1”的数字。数字 34 名字为“1”，链接到名字为“2”的数字。依此类推。

现在当子算法返回出现最频繁的两位数字块时，12 寻在名字为“1”的数字，找到了 34，然后 34 寻在名字为“2”的数字，找到了 56，56 寻在名字为“3”的数字，找到了 78。

这样，可以将两位数的块看作链条上的扣，这些扣通过这些额外的标记数字连接起来。

当然，链条的问题是，它们的强度取决于最脆弱的扣。而且链条基本上必然会断。

构件

没有任何算法每次运行都能完美运行——即使是最好的算法也会偶尔失灵。在我们使用的例子中，失灵可能意味着第二个两位数的块 34 被分配了一个不正确的标记，因此，当它寻找它应该被连接的块时，它没有找到 56 需要的信息。一旦链条中的一个扣失败，一切努力就是徒劳。

为了避免这个问题，研究人员使用了所谓的“膨胀图”（expander graph）。在膨胀图中，每个两位数的块形成一个点。点（按照上面描述的标记过程）通过连线相互连接形成一个簇（cluster）。膨胀图的一个重要特征是，不是只将每个点与其相邻的块连接起来，还要将每个两位块与多个其他块连接起来。例如，以 12,345,678 为例，12 与 34 相连，也与 56 相连，所以即使 12 和 34 之间的连接失效了，仍然可以知道 12 和 56 属于相同的数字。

膨胀图并不总是完美的。有时两个应该连接的块却没有连接起来。或者它将两个不属于一个数字的块连接在了一起。为了应对这种可能，研究人员开发了算法的最后一步：“簇维护”（cluster-preserving）子算法，可以调查膨胀图，准确地确定哪些点应该聚集在一起，哪些不应该，即使有些 连线丢失，或添加了错误的连线。

Thorup 说：“这保证了我能恢复看起来像原始簇的东西。”

虽然 Twitter 不会马上使用膨胀图，但背后的技术适用于远比处理推文广泛的计算机科学问题。该算法还证明了，解决频繁词条问题以前看起来是必需的牺牲是不必要的。以前的算法总是放弃一些东西——准确但是耗内存，或者很快但是不能确定哪些词条的趋势上升。这项新的算法表明，给予正确的方式来编码大量的信息，你可以尽享世界所有之美好：你可以存储频繁的词条，也可以找回它们。

查看英文原文：

https://www.quantamagazine.org/best-ever-algorithm-found-for-huge-streams-of-data-20171024