- name
- Boyer-Moore majority vote algorithm
- short description
- Boyer-Moore majority vote algorithm は、列の過半数を占める要素を効率的に発見するアルゴリズムの一つである。 相異なる要素を繰り返し対にして、対にならずに残った要素が過半数となる候補であるという事実を用いる。 要素に対しては一致判定のみを用いるため、全順序などが定義されている必要が無い。 過半数を占める要素が存在しない場合何を出力しても良いことにすると、計算量をそのままに、列を一度走査するだけで計算することが可能になる。
- input
- 長さ $N$ の列 $a$
- output
- $a$ に $\frac{N}{2}$ 回を超えて出現する要素が存在するかどうか、存在する場合その要素
- time complexity
- $\Theta(N)$
- space complexity
- $\Theta(1)$
概要
Boyer-Moore majority vote algorithm は、列の過半数を占める要素を効率的に発見するアルゴリズムの一つである。 相異なる要素を繰り返し対にして、対にならずに残った要素が過半数となる候補であるという事実を用いる。 要素に対しては一致判定のみを用いるため、全順序などが定義されている必要が無い。 過半数を占める要素が存在しない場合何を出力しても良いことにすると、計算量をそのままに、列を一度走査するだけで計算することが可能になる。
詳細
$a$ から相異なる $2$ 要素を対にして、それらを取り除くことを操作が不可能になるまで繰り返すことを考える。 このとき、$a$ に残る要素が存在するならば全て等しくなっており、この要素のみが $a$ の過半数を占める可能性がある。
証明
$x$ が $a$ に $\frac{N}{2}$ 回を超えて出現するとする。 対を作るたびに $x$ は高々 $1$ つずつ $a$ から取り除かれるが、対は $\frac{N}{2}$ 個以下しか作れないため、$x$ は最後まで完全に取り除かれることが無い。 $\blacksquare$
アルゴリズムにおいては、$a$ を前から順に参照して、相異なる $2$ 要素を発見したら直ちに取り除く。 より正確には $i = 0, 1, \dots, N - 1$ の順に、$a _ j$ が取り除かれていないかつ $a _ j \neq a _ i, j \lt i$ となるような $j$ が存在するならば $a _ j$ と $a _ i$ を取り除く、という操作を繰り返す。 そのような $j$ の存在を効率的に判定するために、多重集合 $S \coloneqq \lbrace a _ j \mid j \lt i, a _ j$ は取り除かれていない $\rbrace$ を管理する。 $S$ は空であるか、あるいは $1$ 種類の要素だけから構成されているため、$1$ つの元と $\lvert S \rvert$ だけを管理すればよい。 この表現によって、$a _ j$ の発見や $S$ の更新は全て時間計算量 $\Theta(1)$ で実行される。
これによって得られた出力の候補が実際に過半数を占めるかどうかは、もう一度 $a$ を走査することで確認できる。
空間計算量は $a$ の元を $\mathrm{O}(1)$ で保持できると仮定すると $\Theta(\log(N))$ bits となる。 これは $\lvert S \rvert$ の保持や、最後の確認で数えるときに $N$ 以下の整数を持つ必要があるためである。 Word-RAM を仮定すれば $\Theta(1)$ となる。
一般化
長さ $N$ の列 $a$ と $1 \leq k \leq N$ を満たす整数 $k$ が与えられたとき、$a$ に $\frac{N}{k + 1}$ 回を超えて出現する要素を列挙することが $\Theta(Nk)$ の時間計算量、$\Theta(k)$ の空間計算量で可能である。 元のアルゴリズムとほとんど同様に、$k + 1$ 個の互いに相異なる要素を組にして、組になっていない高々 $k$ 種類の要素とそれぞれの個数を管理すればよい。 $k = 1$ の場合が Boyer-Moore majority vote algorithm である。
その他
- 同様の考え方で、Segment Tree を用いて、区間の過半数を占める要素の候補を発見できる。 それぞれのノードは対応する区間で対にならずに残る要素とその個数を管理し、区間をマージする際は必要なだけ対を作れば、常に $1$ 種類以下の要素が残る状態が保たれる。 発見した要素が本当に過半数を占めるかどうかを確認する必要がある場合、別途データ構造が必要となる。 例えば、各値について平衡二分探索木を管理する方法が挙げられる。
参考文献
- Boyer, R. S., & Moore, J. S. (1991). MJRTY—a fast majority vote algorithm. In Automated Reasoning (pp. 105-117). Springer, Dordrecht.
- Boyer-Moore majority vote algorithm が提案された論文
- changelog
- license
This work is licensed under a Creative Commons Attribution 4.0 International License.