電腦科學家突破性發現：用「硬幣翻面法」解決數十年難題

你可能沒想過，「數數」這麼簡單的事情，竟然會成為困擾電腦科學界數十年的難題。但最近一組研究團隊真的找到了一個創新的解決方案，而且方法簡單到令人驚訝。

對人類來說，辨識並計算眼前不同物體的數量簡直輕而易舉。但對電腦而言，這卻是個相當棘手的「相異元素問題」(Distinct Elements Problem)。這個問題在現代社會應用廣泛，從社群媒體監測線上人數、詐騙偵測，到生物資訊學和文字分析都派得上用場。

過去雖然有解決方案，但效果都不盡理想。內布拉斯加大學林肯分校的Vinodchandran Variyam教授解釋：「已知的演演算法都基於雜湊函式，其品質取決於所選用的雜湊函式。」

Variyam與來自印度統計研究所和多倫多大學的同事合作，開發出一種名為CVM的新演演算法。這個方法巧妙運用機率理論，大幅降低了記憶體需求——這在大資料時代至關重要。

舉個例子：假設你想計算莎士比亞《哈姆雷特》中使用的不重複單字數量，但記憶體只能儲存100個單字。新方法的運作原理如下：

首先記錄前100個不重複單字，之後對每個新單字擲硬幣決定是否保留。經過多輪篩選，最後根據保留的單字數和篩選輪次，就能估算出總數。實測結果顯示，即使只用100個單字的記憶空間，估算值3,904與實際值3,967也相當接近。

麻省大學阿默斯特分校的Andrew McGregor教授盛讚：「這個演演算法簡單得驚人，很可能成為業界處理此類問題的新標準。」就連被譽為「演演算法分析之父」的Donald Knuth也表示，自從看到這個演演算法後，他忍不住想向每個遇到的人解釋它的精妙之處。

目前已有電腦科學課程開始教授這個方法。Variyam教授預測：「這將會成為演演算法入門課程，特別是機率演演算法的標準教材。」Knuth也認同這個看法，認為它非常適合作為電腦科學基礎教學內容。

這項突破性研究已發表在arXiv平臺，並收錄於第30屆歐洲演演算法研討會論文集(ESA 2022)中。