シーケンシャルアルゴリズム

Boyer-Moore 過半数票アルゴリズム

Takami Torao #ストリーミングアルゴリズム
  • このエントリーをはてなブックマークに追加

概要

Boyer-Moore 過半数票アルゴリズム (Boyer-Moore majority vote algorithm) は多重集合から過半数を占める要素 (\(N/2\) 個より多い要素) を見つけるためのストリーミングアルゴリズムである。[1] において選挙で投票された票の過半数を獲得した候補者を特定するアルゴリズムを例に紹介された。このアルゴリズムは 1 セットのレジスターのみを使用し 2 回 (特定なケースでは 1 回) の走査で結果を特定する。つまり空間計算量 \(O(1)\) と時間計算量 \(O(n)\) の特性を持つ。

Table of Contents

  1. 概要
  2. アルゴリズム
  3. 参考文献

アルゴリズム

Boyer-Moore 過半数票アルゴリズムは「多重集合の中で要素 \(A\) が過半数を占める場合、異なる要素どうしを対消滅させてゆけば、必ず最後に \(A\) が残る」という考えに基づいている。ただし過半数となる要素が存在しない場合の結果は不確定となるため、選択された要素が本当に過半数を占めていることを確認するための追加の走査を必要とする。

最初のペアリングフェーズ (pairing phase) では異なる要素を検出したら共に消滅させて残った「候補」を選択する。アルゴリズムの擬似コードを Algorithm 1 に示す。使用する空間は現在の候補とそのカウンターの 2 つである。

1. \( {\rm candidate} \leftarrow {\tt null} \)
2. \( {\rm counter} \leftarrow 0 \)
3. \( {\bf function} \ {\rm update}(x) \)
4. \( \hspace{12pt}{\bf if} \ {\rm counter} = 0 \ {\bf then} \)
5. \( \hspace{24pt}{\rm candidate} \leftarrow x \)
6. \( \hspace{24pt}{\rm counter} \leftarrow 1 \)
7. \( \hspace{12pt}{\bf else \ if} \ {\rm candidate} = x \ {\bf then} \)
8. \( \hspace{24pt}{\rm counter} \leftarrow {\rm counter} + 1 \)
9. \( \hspace{12pt}{\bf else} \)
10. \( \hspace{24pt}{\rm counter} \leftarrow {\rm counter} - 1 \)
11. \( \hspace{12pt}{\bf return \ if} \ {\rm counter} = 0 \ {\bf then} \ {\tt null} \ {\bf else} \ {\rm candidate} \)
Algorithm 1. Boyer-Moore アルゴリズムによる過半数候補の選択。

このアルゴリズムは過半数の要素が存在しなかったことを報告しないことに注意。データストリームに過半数を占める要素が存在しない場合、アルゴリズムの選択する要素は任意である (最も頻繁に出現した要素であることは保証されない)。

データストリームに過半数の要素が存在していることが確かであれば、ペアリングフェーズで得られた候補が「過半数」の要素であることは正しい。例えば「賛成」か「反対」かしか含まれていないような 2 値のケースでは必ずどちらかが多数となる。

過半数の要素が存在するか不確定な場合、ペアリングフェーズで得られた候補 \(c\) が本当に過半数かを確認するためにもう一度データセットを走査する計測フェーズ (counting phase) を行う必要がある。計測フェーズでは再び Algorithm 1 を利用して true または false の入力で更新する。これは前フェーズの入力に使用したそれぞれの要素がペアリングフェーズで得られた候補 \(c\) と一致するかを表すブール値である。このフェーズは 2 値のデータストリームとなるため、最終的に Algorithm 1 の示す候補が true となればペアリングフェーズで得た候補 \(c\) が過半数であることが確定する。

参考文献

  1. MOORE, J. Strother. A fast majority vote algorithm. Automated Reasoning: Essays in Honor of Woody Bledsoe, 1981, 105-108.
  2. Dzejla Medjedovic, Emin Tahirovic, Ines Dedovic. 大規模データセットのためのアルゴリズムとデータ構造. マイナビ出版 (2024)