Boyer-Moore majority vote algorithm

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /boyer-moore-majority-vote-algorithm#noredirect を利用してください。
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 である。

その他

参考文献