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

文章预览

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