想象一下，你被派往一片原始雨林进行野生动物普查。每当你看到一只动物，就拍一张照片。你的数码相机会记录总拍摄次数，但你只关心独一无二的动物数量——那些你还没统计过的。如何最有效地得到这个数字呢？伊利诺伊理工学院的计算机科学家兰斯·福托诺说：“显而易见的解决方案是记住至今所见的所有动物，然后逐个对比新出现的动物。”但他补充道，还有更聪明的方法，因为如果有数千条记录，显而易见的方式并不简单。
情况变得更糟。如果你是Facebook，想要统计每天登录的唯一用户数量，即使他们可能来自多个设备并在不同时间登录，问题就更复杂了。现在，你需要将每个新的登录与可能达到数十亿的列表进行比较。
在最近的一篇论文中，计算机科学家们提出了一种新方法，可以近似长列表中独特项目的数量，这种方法只需要记住少数项目。这种被称为CVM算法（由其发明者Sourav Chakraborty、Vinodchandran Variyam和Kuldeep Meel分别来自印度统计研究所、内布拉斯加大学林肯分校和多伦多大学命名）是对被称为“独特元素问题”的重大进展，这个问题困扰计算机科学家已经超过40年。这个问题要求找到一种有效监控元素流（其总数可能超过可用内存）并估计独特元素数量的方法。
马萨诸塞大学阿默斯特分校的Andrew McGregor表示：“新算法惊人地简单且易于实现。我不觉得这不会成为实际处理[独特元素]问题时的首选方式。”
让我们通过一个例子来说明问题以及CVM算法如何解决它。假设你在听《哈姆雷特》的有声书。剧本中有30,557个单词。有多少是独特的？你可以边听边频繁暂停，按字母顺序在笔记本上写下每个单词，跳过已有的单词。读完后，只需数一数笔记本上的单词数量。这种方法可行，但需要的记忆容量大约等于独特单词的数量。
在典型的数据流场景中，可能有数百万个项目需要跟踪。“你可能不想存储所有内容，”Variyam说。这时，CVM算法就能提供更简便的方法。关键在于利用随机化。
分享这篇文章FacebookTwitter复制链接电子邮件PocketRedditYcombinatorFlipboard订阅通讯获取量子杂志发送到您的邮箱立即订阅最新通讯
回到《哈姆雷特》，但这次你的工作记忆——一块白板——只能容纳100个单词。一旦开始，你写下听到的前100个单词，跳过重复的。当空间满时，暂停并为每个单词抛硬币。正面，单词留在列表上；反面，删除它。完成初步筛选后，你大约剩下50个独特的单词。
接下来进入第一轮。继续听《哈姆雷特》，随着剧情推进添加新单词。遇到已经在列表上的单词，再抛一次硬币。如果是反面，删除；正面，单词保留。如此进行，直到白板上有100个单词。然后根据100次硬币投掷的结果随机删除大约一半。这就结束了第一轮。
进入第二轮，继续第一轮的操作，但现在让保留单词变得更困难。遇到重复的单词，再次抛硬币。反面，删除；正面，再抛一次硬币。只有连续两次正面才保留单词。填满白板后，这一轮结束时，根据100次硬币投掷结果删除大约一半的单词。
第三轮需要连续三次正面才能保留单词。第四轮需要四次，以此类推。
最终，在第k轮，你会到达《哈姆雷特》的结尾。这个练习的目的是确保每个单词，由于随机选择，都有相同的可能性出现在那里：1/2k。例如，如果你在听完《哈姆雷特》后列表上有61个单词，经过六轮后，你可以用61除以概率1/26来估计独特单词的数量——在这个例子中大约是3,904个。（很容易理解这个过程：假设你开始有100枚硬币，逐个翻转，只保留正面的。最后你会接近50枚硬币，如果有人用这个数量除以概率1/2，他们就能猜出最初大约有100枚硬币。）
Variyam和他的同事们数学上证明了这种技术的准确性随记忆大小而增加。《哈姆雷特》恰好有3,967个独特的单词。（他们数过。）在使用100个单词的记忆实验中，五次运行后的平均估计值为3,955个单词。使用1,000个单词的记忆，平均值提高到了3,964个。他说：“当然，如果记忆足够大，能容纳所有的单词，那么我们可以达到100%的准确性。”
哈佛大学的William Kuszmaul表示：“这是一个很好的例子，即使是基本且研究充分的问题，有时仍存在非常简单但不显而易见的解决方案等待发现。”
