开创性CVM算法解开40多年计数难题！计算机科学家掷硬币算出「哈姆雷特」独特单词

计数，听起来简单，却在实际执行很有难度。

想象一下，你被送到一片原始热带雨林，进行野生动物普查。每当看到一只动物，拍一张照片。

数码相机只是记录追踪动物总数，但你对独特动物的数量感兴趣，却没有统计。

那么，若想获取这一独特动物数量，最好的方法是什么？

这时，你一定会说，从现在开始计数，最后再从照片中将每一种新物种与名单进行比较。

然而，这种常见的计数方法，有时并不适用于高达数十亿条目的信息量。

来自印度统计研究所、UNL、新加坡国立大学的计算机科学家提出了一种新算法——CVM。

它可以近似计算长列表中，不同条目的的数量，而且只需要记住少量条目就可实现。

论文地址：https://arxiv.org/pdf/2301.10191

这一算法适用于任何一次出现一个条目的清单，比如演讲中的文字、传送带上的商品，或州际公路上的汽车。

CVM算法是以三位作者首字母命名，在解决「不同元素问题」上取得的一个重大进展。

而这一问题，长期困扰计算机科学家40多年。

它要求有一种高效的方法来监控一个元素流（其总数可能超过可用内存），并估算出其中独特元素的数量。

那么，CVM算法究竟是如何解决问题的？

开创性CVM算法，秘诀在于「随机化」

假设你在听《哈姆雷特》有声读物。

这部戏剧共有30557个字，有多少是不同的？

为了找到答案，你可以边听边暂停，按字母顺序写下每个单词，然后跳过清单上已有的单词，最后，只需要数一下清单上每个单词数。

这种方法是可行的，但太考验一个人的「记忆量」了。

研究者Vinodchandran Variyam表示，「在典型的数据流情况中，可能会有数百万个项目需要追踪。你可能不想把所有的信息都存储起来。

这就是，云服务器算法可以提供更简单方法的地方」。

诀窍，就在于「随机化」。

Vinodchandran Variyam帮助发明了一种估算数据流中不同元素数量的CVM算法

「哈姆雷特」有多少个独特词？掷硬币大挑战

再回到《哈姆雷特》，假设你的「有效内存」只能容纳100个单词。

一旦音频开始播放，你记下听到的前100个单词，并跳过任何重复的单词。

当完成100个单词记录后，剩下的就是为每个单词掷硬币——

正面，保留单词。若为反面，将其删除。

在这一轮初选之后，你将留下大约50个不同的单词。

现在，你继续团队所说的第一轮游戏Round 1，继续阅读《哈姆雷特》，添加新单词。

如果你再次遇到一个已经在清单上的单词，再次掷硬币决定，一直到你的内存白板中，有100个单词。

然后，根据100次掷硬币的结果，再次随机删除大约一半的单词。Round 1到此结束。

接下来，进入第二轮Round 2。

和第一轮一样，我们要增加一个单词的难度——当你遇到一个重复的单词时，再次掷硬币。

条件是，如果是反面，就像之前一样删除它。但如果是正面，就再掷一次硬币。只有当第二次出现正面时，才保留这个单词。

一旦内存白板写满，结束这一轮，然后根据100次抛掷结果，再次删除大约一半的单词。

在第三轮Round 3中，你需要连续三次掷硬币正面，才能保留一个单词。

在第四轮中，连续四次正面保留一个单词，以此类推。

最终，在第k轮，你会听完整部《哈姆雷特》戏剧。

这个练习的重点是，确保每个单词都有相同的出现概率：1/2 (k) 。

假设，如果在《哈姆雷特》音频结束时，你的列表中有61个单词，用了六轮的时间完成。

你可以用61除以概率1/2 (6)来估计不同单词的数量——最终在这个游戏中的结果是3904个。

算法精度与内存量成正比

研究人员Chakraborty、Variyam和Meel从数学上证明了CVM算法的精确度与内存量的大小成比例。

而《哈姆雷特》恰好有3967个独特的单词。（通过普通的计数方法）

在使用100个单词内存的实验中，5轮实验结果的平均估计为3955个单词。

在1000个单词内存忆量下，平均提高到3964个。

Variyam表示，「如果（内存量）大到可以容纳所有单词，那么我们就可以达到100%的准确率」。

哈佛大学William Kuszmau表示，「这是一个很好的例子，说明即使是非常基础和被广泛研究过的问题，有时也可能存在简单但并不明显的解决方案仍待被发现」。

参考资料：

https://www.quantamagazine.org/computer-scientists-invent-an-efficient-new-way-to-count-20240516/