走进科学
科学家发现了新的计数方法
这个新方法简单到连本科生都能理解，但一直没有人发现它。
科学在创新和改善我们的生活方面很棒，但有些东西我们似乎已经掌握得很牢了。比如，你不会想到我们还能改进像计数这样简单的事情。
所以，当一群计算机科学家找到了一种解决一个看似简单但已有几十年历史的问题的新方法时，可能会让你感到惊讶——这个问题就是：我面前有多少个不同的东西？
这个问题比你想象的要难，而解决方案也比你想象的要聪明得多。
不同元素问题
计算机可以非常聪明，但有时也非常……不聪明。看看最近涌现的AI聊天机器人就知道了：它们听起来很聪明，但一测试，你可能会发现它们满嘴跑火车。
有时候，对人类来说几乎可笑简单的事情，对计算机却是最大的难题。比如计数——特别是数不同的物体。对我们来说，这很简单：我们看看一堆物体，大脑自动把它们分成不同的组，几乎不费什么力气。
但对计算机来说，这是一个基本而且已有几十年历史的问题。而且这个问题必须解决，因为它在现代世界中的应用非常广泛，从网络流量分析(比如Facebook或Twitter监测有多少人在线)到欺诈检测、生物信息学、文本分析等等。
显然，我们已经有了这些问题的解决方案，但它们并不完美。
“以前已知的算法都是基于‘哈希’的，算法的质量取决于选择的哈希函数的质量，”内布拉斯加大学林肯分校计算机学院的教授Vinodchandran Variyam去年在一份声明中解释道。
但他和印度统计研究所的Sourav Chakraborty以及多伦多大学的Kuldeep Meel一起，发现了一种极大简化问题的方法：“新算法只使用采样策略，并且可以使用基本技术进行质量分析。”
它是如何工作的
这个新方法被命名为CVM算法，以纪念它的发明者。它大大减少了内存需求，这在大数据时代是一个重要的优势，并且使用了概率论的一个巧妙技巧。为了说明这个概念，考虑Variyam及其同事研究的例子，以及《量子杂志》最近的一篇文章：假设你在统计莎士比亚《哈姆雷特》中独特的单词数量，但你只能存储100个单词。
首先，你做显而易见的事情：记录你遇到的前100个独特单词。现在，你的内存满了——所以你对每个单词抛硬币。正面，就保留；反面，就忘掉。
在这个过程中，你的列表中大约会有50个独特单词。然后你重新开始——但这次，如果遇到列表中的单词，你再次抛硬币决定是否删除它。一旦达到100个单词，你再次遍历列表，为每个单词抛硬币并按提示删除或保留。
在第二轮中，事情变得稍微复杂一点：这次你需要连续两次正面才能保留一个单词；否则，它会被删除。同样地，在第三轮中，你需要连续三次正面才能保留；第四轮需要四次，依此类推，直到你读完《哈姆雷特》。
这个方法有其道理——而且很聪明。通过这样处理文本，你确保了列表中的每个单词都有相同的概率：1/2^k，其中k是你遍历列表的次数。假设你花了六轮读完《哈姆雷特》，列表中剩下61个不同的单词：你可以将61乘以2^6来估算单词总数。
我们帮你算好了：答案是3904——而根据Variyam和他的同事，实际答案是3967(是的，他们数了)。如果你的内存能存储超过100个单词，准确度会更高：如果能存储1000个单词，算法估算的答案是3964——几乎没有误差——而“当然，”Variyam告诉《量子杂志》，“如果内存大到可以容纳所有单词，我们就能达到100%的准确度。”
一种简单的方法
这个算法不仅高效，而且它的简单性更加令人着迷。马萨诸塞大学阿默斯特分校信息与计算机科学学院的教授Andrew McGregor在接受《量子杂志》采访时表示：“这个新算法令人惊讶地简单，且易于实现。我不会感到意外，如果它成为解决[不同元素]问题的默认方法。”
自从2023年1月发布以来，尽管期间出现了一些小问题和漏洞，这个算法已经吸引了许多计算机科学家的关注和赞赏。尽管详细介绍该算法的论文尚未正式经过同行评审，但实际上它已经得到了同行的认可。算法分析领域的“教父”，《计算机程序设计艺术》的作者Donald Knuth，在2023年5月还撰写了一篇赞扬该算法的文章。他评论道：“自从我看到这个算法以来……我几乎无法抗拒向我遇到的每个人解释这些想法。”
与此同时，包括Chakraborty、Variyam和Meel在内的多个团队在过去一年中一直在研究和优化这个算法。Variyam说，一些人甚至已经在他们的计算机科学课程中教授这个算法。
“我们相信，这将成为在算法和概率算法的基础课程中教授的主流算法，”他说。Knuth也表示赞同：“它非常适合教授正在学习计算机科学基础知识的学生，”他在5月的文章中写道。“我非常确定，这样的内容最终会成为标准教科书的一部分。”
那么，这样一个突破性的算法为何能在这么长时间内未被发现？根据Variyam的说法，这并不像听起来那么不可能。
“这个简单的算法没有被更早发现确实令人惊讶，”他说。“在科学领域，简单的东西多年未被发现并不少见。”
这篇论文已经在ArXiv上发布，并出现在《第30届欧洲算法年会论文集》(ESA 2022)中。
本文译自 IFLScience，由 BALI 编辑发布。