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

1,093 0 0

文章摘要

计算机科学家们提出了一种名为CVM的新算法，用以估算数据流中不同元素的数量。该算法利用随机性，仅需记忆少量条目，便能近似计算长列表中不同条目的总数。这一创新在解决“不同元素问题”上取得了重大进展，该问题长期困扰计算机科学家超过40年，其挑战在于高效地监控元素流并估算独特元素的数量，尤其是在元素总数可能超过可用内存的情况下。

CVM算法的诀窍在于“随机化”。以《哈姆雷特》为例，如果音频中的30557个单词超出了记忆容量，算法可以通过掷硬币的方式来决定是否保留已记录的单词。在每一轮中，重复的单词需要掷硬币决定去留，而随着轮数增加，保留单词所需的连续正面次数也增加，以此确保每个单词都有相同的出现概率。通过这种概率估算，即使在有限的内存下，也能得出不同单词数量的近似值。

研究显示，算法的精确度与内存量成正比。在实际操作中，使用100个单词的内存进行五轮实验，平均估计的独特单词数量接近《哈姆雷特》实际单词数。增加内存量可提高估算准确性，当内存足以容纳所有单词时，理论上可以达到100%的准确率。

这一成果得到了业界的认可，被认为是一个简单但并不明显的解决方案，即使是基础且广泛研究的问题也可能存在突破的可能。CVM算法的提出不仅为处理大数据提供了新工具，也为计算机科学领域带来了新的启示。