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

AIGC动态欢迎阅读

原标题：开创性CVM算法破解40多年计数难题！计算机科学家掷硬币算出「哈姆雷特」独特单词
关键字：单词,算法,硬币,数量,内存
文章来源：新智元
内容字数：3970字

内容摘要：

新智元报道编辑：桃子
【新智元导读】预估一个数组中不重复数字的个数，最简便的方法是什么？计算机科学家们提出了一种全新CVM算法，通过利用随机性，预估出数据流中大量不同的对象。计数，听起来简单，却在实际执行很有难度。
想象一下，你被送到一片原始热带雨林，进行野生动物普查。每当看到一只动物，拍一张照片。
数码相机只是记录追踪动物总数，但你对独特动物的数量感兴趣，却没有统计。
那么，若想获取这一独特动物数量，最好的方法是什么？
这时，你一定会说，从现在开始计数，最后再从照片中将每一种新物种与名单进行比较。
然而，这种常见的计数方法，有时并不适用于高达数十亿条目的信息量。
来自印度统计研究所、UNL、新加坡国立大学的计算机科学家提出了一种新算法——CVM。
它可以近似计算长列表中，不同条目的的数量，而且只需要记住少量条目就可实现。
论文地址：https://arxiv.org/pdf/2301.10191
这一算法适用于任何一次出现一个条目的清单，比如演讲中的文字、传送带上的商品，或州际公路上的汽车。
CVM算法是以三位作者首字母命名，在解决「不同元素问题」上取得的一个重大进展。
而这一问题

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