多數投票算法

博耶-摩爾多數投票算法（英語：Boyer–Moore majority vote algorithm）,中文常作多數投票算法、摩爾投票算法等，是一種用來尋找一組元素中占多數元素的常數空間級時間複雜度算法。這一算法由羅伯特·S·博耶（英語：Robert S. Boyer）和J·斯特羅瑟·摩爾（英語：J Strother Moore）在1981年發表^[1]，也是處理數據流（英語：streaming algorithm）的一種典型算法。

這一算法應用的問題原型是在集合中尋找可能存在的多數元素，這一元素在輸入的序列重複出現並占到了序列元素的一半以上；在第一遍遍歷之後應該再進行一個遍歷以統計第一次算法遍歷的結果出現次數，確定其是否為眾數；如果一個序列中沒有占到多數的元素，那麼第一次的結果就可能是無效的隨機元素。對於數據流而言，則不太可能在亞線性空間複雜度的情況下中就尋找到出現頻率最高的元素；而對於序列，其元素的重複次數也有可能很低。^[2]

算法[編輯]

該算法在其局部變量中存儲一個數組元素和一個計數器，計數器初始化為 0。然後對數組進行遍歷操作，在遍歷到元素 x 的時候：如果計數器為 0，則算法將 x 存儲到數組元素變量，並將計數器設置為 1。否則，它將 x 與存儲的元素進行比較，然後遞增計數器（如果它們相等）或遞減計數器（不相等）。在此過程結束時，如果數組中存在占多數的元素，則它將是存儲的數組元素變量的值。

算法可以用偽代碼如下表示：

初始化元素 $m$ 並給計數器 $i$ 賦初值 $i = 0$
對於輸入隊列中每一個元素 $x$ ：
- 若 $i = 0$ , 那麼 $m = x$ and $i = 1$
- 否則若 $m = x$ , 那麼 $i = i + 1$
- 否則 $i = i - 1$
返回 $m$

即便輸入序列沒有多數元素，這一算法也會返回一個序列元素。然而如果能夠進行第二輪遍歷，檢驗返回元素的出現次數，就能判斷返回元素是否為多數元素。因此算法需要兩次遍歷，亞線性空間算法無法通過一次遍歷就得出輸入中是否存在多數元素。^[3]

參見[編輯]

元素唯一性問題，判斷序列中該元素唯一
多數函數（英語：Majority function），返回多數元素的布爾類型集合
多數問題 (元胞自動機)（英語：Majority problem (cellular automaton)），在細胞自動機計算模型中尋找多數元素

參考資料[編輯]

^ Boyer, R. S.; Moore, J S., MJRTY - A Fast Majority Vote Algorithm, Boyer, R. S. (編), Automated Reasoning: Essays in Honor of Woody Bledsoe, Automated Reasoning Series, Dordrecht, The Netherlands: Kluwer Academic Publishers: 105–117, 1991, doi:10.1007/978-94-011-3488-0_5 ^{[失效連結]}. Originally published as a technical report in 1981.
^ Trevisan, Luca; Williams, Ryan, Notes on streaming algorithms (PDF), CS154: Automata and Complexity (Stanford University), January 26, 2012 [2020-06-03], （原始內容存檔 (PDF)於2017-08-29） .
^ Cormode, Graham; Hadjieleftheriou, Marios, Finding the frequent items in streams of data, ACM通訊, October 2009, 52 (10): 97, doi:10.1145/1562764.1562789, no algorithm can correctly distinguish the cases when an item is just above or just below the threshold in a single pass without using a large amount of space .

[bm-1] Boyer, R. S.; Moore, J S., MJRTY - A Fast Majority Vote Algorithm, Boyer, R. S. (編), Automated Reasoning: Essays in Honor of Woody Bledsoe, Automated Reasoning Series, Dordrecht, The Netherlands: Kluwer Academic Publishers: 105–117, 1991, doi:10.1007/978-94-011-3488-0_5 ^{[失效連結]}. Originally published as a technical report in 1981.

[cs154-2] Trevisan, Luca; Williams, Ryan, Notes on streaming algorithms (PDF), CS154: Automata and Complexity (Stanford University), January 26, 2012 [2020-06-03], （原始內容存檔 (PDF)於2017-08-29） .

[3] Cormode, Graham; Hadjieleftheriou, Marios, Finding the frequent items in streams of data, ACM通訊, October 2009, 52 (10): 97, doi:10.1145/1562764.1562789, no algorithm can correctly distinguish the cases when an item is just above or just below the threshold in a single pass without using a large amount of space .

[1]

[2]

[3]