Boyer–Moore の過半数投票アルゴリズム：候補 1 つとカウンタで過半数を探す、2 回目の走査が要る理由

n 個の値のうち、半分より多く現れる値があるか、あるならどれかを知りたいとします。投票で過半数を得た候補を探す問題であり、配列の「過半数要素（majority element）」を探す問題でもあります。ここでの過半数は、厳密に n/2 より多いという意味です。13 票中 7 票は過半数ですが、12 票中 6 票は過半数ではありません。

Robert S. Boyer と J Strother Moore は、この問題を値 1 つとカウンタ 1 つで解くアルゴリズムを 1980 年に考案し、論文では MJRTY と呼びました。一般には Boyer–Moore の過半数投票アルゴリズム（majority vote algorithm）として知られています。この記事は、2 人の 1991 年の論文「MJRTY—A Fast Majority Vote Algorithm」（Bledsoe 記念論文集『Automated Reasoning』105–117 ページ、著者が公開している PostScript 版）と、Moore が公開している解説ページに基づきます。論文後半の Fortran 検証システムの詳細と、このアルゴリズムを一般化した後続研究の内容は扱いません。

よくある方法とそのコスト

論文はまず素直な方法を取り上げます。票を一度走査しながら、候補ごとに得票数を数えていく方法です。候補の数が固定なら、これは n に比例する時間で終わります。候補の数が決まっていないと事情が変わります。途中の集計を保存して探すコストのために、実行時間が票の数に対して線形より悪くなることがあり、論文は n² のオーダーになりうると書いています。

値に順序を付けられるなら、別の道もあります。線形時間の選択アルゴリズムで中央値を求め、その中央値が半分より多くの票を得たか確かめる方法です。過半数要素があれば、並べ替えたときに必ず真ん中の位置に来るからです（この理由はこの記事の説明です）。論文は、このとき使う Rivest–Tarjan のアルゴリズムの比較回数の上限として、n > 32 のとき 5.43n − 163 を挙げています。このような線形時間の選択は中央値の中央値（BFPRT）の記事で扱いました。

MJRTY の比較は多くても 2n 回です。しかも値どうしの大小関係を必要としません。論文の言い方では、行うのは「等しいか」の比較だけです。

規則は 2 つだけ

アルゴリズムは値を先頭から 1 つずつ読みながら、現在の候補（candidate）とカウンタの組を保ちます。最初は候補が決まっておらず、カウンタは 0 です。要素 e を読むたびに次のようにします。

カウンタが 0 なら、候補を e にしてカウンタを 1 にします。
カウンタが 0 でなければ、e が現在の候補と等しいときカウンタを 1 増やし、異なるとき 1 減らします。

最後まで読み終えたときに残っている候補が、過半数要素があるならその要素です。この「あるなら」という条件がこのアルゴリズムで最も大事な部分で、後で節を分けて扱います。

論文はこの過程を、党大会の会場で起きる乱闘にたとえます。代議員はそれぞれ支持する候補の名前を書いたプラカードを持っていて、別の候補を支持する 2 人が出会うと、互いに同時に倒れるとします。ある候補の支持者が残り全員を合わせたより多ければ、最後まで立っているのはその候補の支持者だけです。過半数がなければ、立っている人がいたとしても、その人たちの候補が過半数だという保証はありません。そのため議長は、残った候補のプラカードを、倒れた人が持っているものも含めて数え直す必要があります。

そこで論文はアルゴリズムを 2 つに分けます。異なる票どうしを対にして消す「対消し（pairing）フェーズ」と、残った候補が本当に半分より多くの票を得たかを数える「計数（counting）フェーズ」です。論文によれば、対消しは n 回の比較で行え、計数フェーズも多くても n 回の比較で済みます。

例で追ってみる

Moore の解説ページと論文が共通して使う例は、13 個の要素からなる列です。

A A A C C B B C C C B C C

各要素を読んだ直後の状態を「候補:カウンタ」と書くと、解説ページの段階ごとの図と同じになります。カウンタが 0 で候補がない状態は ? で表します。

順番	要素	状態
1	A	A:1
2	A	A:2
3	A	A:3
4	C	A:2
5	C	A:1
6	B	?:0
7	B	B:1
8	C	?:0
9	C	C:1
10	C	C:2
11	B	C:1
12	C	C:2
13	C	C:3

論文の解説に沿って読むと、4〜6 番目の要素（C 2 つと B 1 つ）が先頭の A 3 票を打ち消してカウンタが 0 になり、7 番目の B が一瞬リードした後、8 番目の C に消されます。その後は C が抜け出し、C:3 で終わります。この列では C が 13 個中 7 個なので（この記事で数えた値です）、実際に過半数です。

最後のカウンタ 3 が C の得票数ではない点に注意してください。カウンタは、対にならずに残った C の票の数です。

なぜ正しいのか

論文の証明は次の不変条件に基づきます。i 番目の要素まで処理した後、それまでに読んだ要素は 2 つのグループに分けられます。

候補 cand を支持する k 個（k は現在のカウンタ）
異なる値どうしで 2 つずつ対にできる残り

この不変条件が最後まで保たれれば結論が出ます。cand 以外のある値 x が n/2 より多くの票を得たと仮定します。2 つ目のグループは異なる値どうしで対にできるので、x がそのグループで得る票は多くても (n − k)/2 です。すると x が n/2 を超えるには 1 つ目のグループにも票がなければなりませんが、1 つ目のグループはすべて cand の票です。矛盾するので、過半数要素があるならそれは cand です。

不変条件そのものは i に関する帰納法で示されます。論文の場合分けをまとめると次のとおりです。

カウンタが 0 のときに新しい要素を読むと、それまでの要素はすべて対になったグループに入っているので、新しい要素 1 つだけで 1 つ目のグループを作り直します。
新しい要素が cand と等しければ、1 つ目のグループに加えます。
cand と異なれば、1 つ目のグループから 1 つを取り出して新しい要素と対にし、2 つ目のグループに移します。

過半数がないと誤った答えが出る

アルゴリズムは、過半数がない入力に対しても候補を 1 つ返します。Moore の解説ページは、上の例の最初の C を A に置き換えてみるよう示しています。

A A A A C B B C C C B C C

この列を同じ規則で追うと、やはり C:3 で終わります。ところが今度は C が 13 個中 6 個、A が 4 個、B が 3 個です（この記事で数えた値です）。過半数要素はないのに、候補は C です。

論文にはもっと短い例もあります。A A A B B B C では A と B が互いに打ち消し合い、最後の C が「不戦勝」で候補になって C:1 で終わります。論文は、別の順番で票を処理していれば A や B が勝っていたかもしれないと付け加えています。過半数がないときに残る候補は入力の順番に左右される値で、それ自体には意味がありません。

2 回目の走査を省けるのはいつか

過半数があることを確かめる必要があるなら、データをもう一度走査して候補の実際の個数を数えなければなりません。Moore の解説ページもこの点をはっきり書いています。この走査を省けるのは、過半数があると分かっているか、そう仮定できる場合だけです。

論文が挙げる例は SIFT という航空機制御システムです。冗長なプロセッサとソフトウェアによる投票で信頼性を得るシステムで、個々のプロセッサの故障率が十分に低いため、1 回の飛行のあいだ正常なプロセッサの過半数が各投票で一致すると仮定できるといいます。過半数を仮定できれば計数フェーズをなくせ、論文はそのとき票をためてからまとめて処理する代わりに、リアルタイムで処理することもできると書いています。

ほかに、論文の Fortran 実装には小さな改良が 1 つ入っています。

対消しフェーズが終わった時点でカウンタが 0 なら、過半数はないとすぐに答えます。
カウンタ k が n/2 より大きければ、計数フェーズを行わずに cand を過半数として報告します。cand の票が少なくとも k 個あるからです。

論文は、同じ検査を最初のループでカウンタを増やすたびに行えば 2 回目の走査を避けられる場合もあるが、それで実行時間が短くなるかどうかは票の分布によると述べています。そして、最初のフェーズを変えて 2 番目のフェーズを不要にする方法は見つけられなかったと書いています。

Python で書いた例

以下は、論文の Fortran サブルーチンと同じ手順で動くようにこの記事で書いたコードです。Fortran 版が BOOLE と CAND の 2 つの値で結果を返すように、過半数の有無と候補を一緒に返します。「過半数なし」を None で表さずに別のフラグを持たせているのは、None そのものが入力値になりうるからです。

def majority(xs):
    """(過半数要素があるか, その要素) を返す。xs は 2 回読む。"""
    n = len(xs)
    cand, k = None, 0
    # 対消しフェーズ
    for x in xs:
        if k == 0:
            cand, k = x, 1
        elif x == cand:
            k += 1
        else:
            k -= 1
    if k == 0:
        return False, None
    if k > n // 2:
        return True, cand
    # 計数フェーズ: 候補が本当に半分より多いか数える
    count = 0
    for x in xs:
        if x == cand:
            count += 1
            if count > n // 2:
                return True, cand
    return False, None


print(majority(list("AAACCBBCCCBCC")))  # (True, 'C')
print(majority(list("AAAACBBCCCBCC")))  # (False, None)
print(majority(list("AAABBBC")))        # (False, None)

整数の範囲では、count > n // 2 は「n/2 より大きい」と同じ条件です。n が奇数の 13 なら n // 2 は 6 で、7 以上で条件を満たします。計数フェーズでカウントが n/2 を超えた時点で終えるのも、論文の Fortran コードと同じです。

いくつか補足します。いずれもこのコードについてのこの記事の説明です。

データを 2 回読み、最初に len(xs) を呼びます。そのため、この関数にはリストのように長さが分かり、何度でも走査できるコレクションを渡す必要があります。1 回しか消費できないイテレータやストリームは、過半数が保証されていても len() の時点ですぐに失敗します。
== の比較しか使いません。並べ替えられない値やハッシュできない値にもそのまま使えます。その代わり、== が一貫して動く必要があります。同じ 2 つの値を比べた結果が毎回変わったり、ある値が自分自身と等しくないと判定されたりすると、上の証明が前提とする「等しい票どうしがグループを作る」という仮定が崩れます。
入力のほかに使う補助領域は O(1) です。候補とカウンタ、n、count、ループ変数など、入力の大きさに関係なく決まった数の変数しか使いません。

コストとアクセスのしかた

論文に基づいてまとめると次のとおりです。

比較回数：対消しが n 回、計数が多くても n 回で、合わせて多くても 2n 回です。確率や平均ではなく、すべての入力に対する上限です。
比較の種類：等しいかどうかだけを見ます。値に順序がなくてもかまいません。
アクセスの順番：配列の要素を先頭から順に読みます。論文はそのため、票が多すぎて磁気テープから読まなければならない場合でも効率よく使え、最初のフェーズの後にテープを 1 回巻き戻せば済むと説明しています。

出版にまつわる経緯

論文末尾の「Postscript 1991」の節は、このアルゴリズムの出版の経緯を自ら説明しています。アルゴリズムは 1980 年、2 人が SRI International にいたときに考案されました。耐故障性（fault tolerance）を研究していた同僚が、Boyer–Moore 定理証明器の論理の中でリストの過半数要素をエレガントに定義してほしいと頼み、その答えがこのアルゴリズムの再帰的な表現だったといいます。1980 年末に Fortran 版を書いて正しさを機械的に証明し、1981 年 2 月に論文を書いて投稿しました。

1981 年に 2 人はテキサス大学に移りました。論文が引用している Jay Misra の私信（1990 年）によると、Misra はこのアルゴリズムの発表を聞いて、n/k 回より多く現れる要素を見つけるよう一般化する方法を考え、その後 David Gries とともに 1982 年に「Finding Repeated Elements」（『Science of Computer Programming』2 巻）を発表しました。この論文は Boyer と Moore の技術報告を「投稿中」として引用しています。

一方で Boyer と Moore の論文は、Fortran と機械検証に重きを置いているという理由で何度も不採録になり、アルゴリズムを中心に書き直した版は、Misra と Gries の論文に取って代わられたという理由で不採録になりました。最終的に元の論文は 1991 年、Woody Bledsoe の記念論文集に収録されました。著者らは、新しいアルゴリズムが機械で検査された正しさの証明とともに初めて発表された例として、この論文を形式検証と自動推論の分野における小さな節目だと考えていると書いています。

使う前に確認すること

過半数の意味：厳密に n/2 より多い必要があります。ちょうど半分は過半数ではありません。
2 回目の走査：過半数が保証されていない入力なら、候補の個数を数え直します。最初の走査の結果だけでは、過半数がない入力でも候補が出てきます。
カウンタの意味：最後のカウンタは候補の得票数ではなく、打ち消し合った後に残った票の数です。
比較：等しさの比較だけを使うので順序のない値にも使えますが、その比較は一貫していなければなりません。
適用範囲：このアルゴリズムが扱うのは、半分より多く現れる要素 1 つだけです。n/k 回より多く現れる要素を探す問題は上の Misra–Gries の論文が扱っており、この記事の範囲外です。

参考資料

いずれも 2026-10-18 に確認しました。

J Strother Moore, A Linear Time Majority Vote Algorithm — 1980 年の考案、例の列、1991 年の論文の書誌情報
J Strother Moore, MJRTY の段階ごとの例 — 候補とカウンタの規則、各段階の状態、過半数がない反例、確認のための 2 回目の走査
R. S. Boyer, J S. Moore「MJRTY—A Fast Majority Vote Algorithm」（1991 年、PostScript） — 比較回数の上限、党大会のたとえ、正しさの証明、例、Fortran 実装と改良、SIFT の事例、出版の経緯

順番	要素	状態
1	A	A:1
2	A	A:2
3	A	A:3
4	C	A:2
5	C	A:1
6	B	?:0
7	B	B:1
8	C	?:0
9	C	C:1
10	C	C:2
11	B	C:1
12	C	C:2
13	C	C:3

順番	要素	状態
1	A	A:1
2	A	A:2
3	A	A:3
4	C	A:2
5	C	A:1
6	B	?:0
7	B	B:1
8	C	?:0
9	C	C:1
10	C	C:2
11	B	C:1
12	C	C:2
13	C	C:3

順番	要素	状態
1	A	A:1
2	A	A:2
3	A	A:3
4	C	A:2
5	C	A:1
6	B	?:0
7	B	B:1
8	C	?:0
9	C	C:1
10	C	C:2
11	B	C:1
12	C	C:2
13	C	C:3