開創性CVM演算法破解40多年計數難題！電腦科學家擲硬幣算出「哈姆雷特」獨特單字

計數，聽起來簡單，卻在實際執行很困難。

想像一下，你被送到一片原始熱帶雨林，進行野生動物普查。每當看到一隻動物，就拍一張照片。

數位相機只是記錄追蹤動物總數，但你對獨特動物的數量感興趣，卻沒有統計。

那麼，若想取得這獨特動物數量，最好的方法是什麼？

這時，你一定會說，從現在開始計數，最後再從照片中將每一種新物種與名單進行比較。

然而，這種常見的計數方法，有時並不適用於高達數十億條目的資訊量。

來自印度統計研究所、UNL、新加坡國立大學的電腦科學家提出了一種新演算法—CVM。

它可以近似計算長列表中，不同條目的數量，而且只需要記住少量條目就可實現。

#論文網址：https://arxiv.org/pdf/2301.10191

這個演算法適用於任何一次出現一個條目的清單，例如演講中的文字、傳送帶上的商品，或州際公路上的汽車。

CVM演算法是以三位作者首字母命名，在解決「不同元素問題」上所取得的重大進展。

而這問題，長期困擾電腦科學家40多年。

它要求有一種高效的方法來監控一個元素流（其總數可能超過可用記憶體），並估算其中獨特元素的數量。

那麼，CVM演算法究竟是如何解決問題的呢？

開創性CVM演算法，秘訣在於「隨機化」

假設你在聽《哈姆雷特》有聲書。

這部戲劇共有30557個字，有多少是不同的？

為了找到答案，你可以邊聽邊暫停，按字母順序寫下每個單詞，然後跳過清單上已有的單詞，最後，只需要數一下清單上每個單字數。

這種方法是可行的，但太考驗一個人的「記憶量」了。

研究者Vinodchandran Variyam表示，「在典型的資料流情況中，可能會有數百萬個專案需要追蹤。你可能不想把所有的資訊都儲存起來。

這就是，雲端伺服器演算法可以提供更簡單方法的地方」。

訣竅，就在於「隨機化」。

Vinodchandran Variyam幫助發明了一種估算資料流中不同元素數量的CVM演算法

「哈姆雷特」有幾個獨特字？擲硬幣大挑戰

再回到《哈姆雷特》，假設你的「有效記憶體」只能容納100個字。

一旦音訊開始播放，你記下聽到的前100個單詞，並跳過任何重複的單字。

當完成100個單字記錄後，剩下的就是為每個單字擲硬幣－

##正面，保留單字。若為反面，將其刪除。

在這一輪初選之後，你將留下大約50個不同的單字。

現在，你繼續團隊所說的第一輪遊戲Round 1，繼續閱讀《哈姆雷特》，加入新單字。

如果你再次遇到一個已經在清單上的單詞，再次擲硬幣決定，一直到你的記憶體白板中，有100個單字。

然後，根據100次擲硬幣的結果，再次隨機刪除大約一半的單字。 Round 1到此結束。

接下來，進入第二輪Round 2。

和第一輪一樣，我們要增加一個單字的難度－當你遇到重複的單字時，再擲硬幣。

條件是，如果是反面，就像之前一樣刪除它。但如果是正面，就再擲一次硬幣。只有當第二次出現正面時，才保留這個單字。

一旦記憶體白板寫滿，結束這一輪，然後根據100次拋擲結果，再次刪除大約一半的單字。

在第三輪Round 3中，你需要連續三次擲硬幣正面，才能保留一個單字。

在第四輪中，連續四次正面保留一個單詞，以此類推。

最終，在第k輪，你會聽完整部《哈姆雷特》戲劇。

這個練習的重點是，確保每個單字都有相同的出現機率：1/2 (k) 。

假設，如果在《哈姆雷特》音訊結束時，你的清單中有61個單詞，用了六輪的時間完成。

你可以用61除以機率1/2 (6)來估計不同單字的數量－最終在這個遊戲中的結果是3904個。

演算法精度與記憶體量成正比

研究人員Chakraborty、Variyam和Meel從數學上證明了CVM演算法的精確度與內存量的大小成比例。

而《哈姆雷特》剛好有3967個獨特的單字。 （透過普通的計數方法）

在使用100個單字記憶體的實驗中，5輪實驗結果的平均估計為3955個單字。

在1000個單字記憶體憶量下，平均提高到3964個。

Variyam表示，「如果（內存量）大到可以容納所有單詞，那麼我們就可以達到100%的準確率」。

哈佛大學William Kuszmau表示，「這是一個很好的例子，說明即使是非常基礎和被廣泛研究過的問題，有時也可能存在簡單但並不明顯的解決方案仍待被發現」。