Rabin–Karp法とは｜仕組み・実装・衝突対策と応用を徹底解説
エバープレイ編集部概要：Rabin–Karp法とは何か
Rabin–Karp法は文字列検索のアルゴリズムで、特に単一または複数のパターンを長いテキスト中から高速に探索するために用いられます。1970年代後半に提案された手法で、ハッシュ関数を用いてパターンとテキスト中の部分文字列の指紋を比較することで、完全照合を行う回数を減らすのが特徴です。平均的な実行時間は線形に近く、実装が比較的簡単で、複数パターン検索や大きなデータ集合に対して有効です。
基本アイデア：ローリングハッシュで連続部分文字列を効率化
Rabin–Karp法の核心はローリングハッシュにあります。長さ m のパターン P と長さ n のテキスト T があるとき、T の各長さ m のスライディングウィンドウに対してハッシュ値を計算し、パターンのハッシュ値と一致する箇所だけを文字ごとに比較します。ウィンドウを一つ右にずらす際のハッシュ更新を O(1) で行える点がポイントです。
典型的には基数 b と素数モジュロ M を選び、文字列 S=s0s1…s_{m-1} のハッシュを次のように定義します：H(S) = (s0*b^{m-1} + s1*b^{m-2} + … + s_{m-1}) mod M。ウィンドウを右へ移すときは、古い先頭文字の寄与を差し引き、新しい末尾文字を乗じる操作で更新できます。
ローリングハッシュの更新式
ウィンドウ U=T[i..i+m-1] のハッシュを h_i、次のウィンドウ h_{i+1} を計算する場合、基本更新式は次のようになります：
h_{i+1} = (b*(h_i - T[i]*b^{m-1} mod M) + T[i+m]) mod M。ここで指数 b^{m-1} は事前に計算しておくか累乗高速化で用意します。実装上は負の値を扱わないように M を加算して正規化することに注意が必要です。
擬似コード（高レベル）
実装の流れは簡潔です。まずパターンのハッシュ hp を計算し、テキストの最初の m 文字のハッシュ ht を計算。i を 0 から n-m まで進め、hp==ht の場合にのみ文字列比較を行う。比較が一致すればマッチを報告。i を進めるごとにローリングで ht を更新する。
処理は平均的には O(n + m) に近いですが、最悪の場合においてはハッシュ衝突が頻発すると O(nm) になる点を理解しておく必要があります。
衝突（コリジョン）と確率的保証
ハッシュ値が一致しても文字列が異なる場合をハッシュ衝突と呼びます。Rabin–Karp法はこの点で確率的手法に分類され、良いハッシュ関数と十分大きなモジュロを選べば衝突確率は極めて小さくなります。衝突が起きた場合も最終的に文字列を直接比較して誤検出を除去するため、アルゴリズムは Monte Carlo 型ではなく Las Vegas 型、すなわち結果の正確性は保たれますが、実行時間が乱される点に注意です。
衝突対策としては次の方法が一般的です：
- 大きな素数 M を用いる（64-bit 程度の大きさ、例えば 2^61-1 のような Mersenne 系を利用することもある）
- 基数 b を適切に選ぶ（文字集合の分布に依存）
- 二重ハッシュを用いる（二つの独立したハッシュ関数を比較して一致を要求する）
- 一致時のみ完全照合を行うことで誤検出を排除する
実装上の注意点
いくつかの実践的なポイントがあります。
- 整数オーバーフローに注意する。64ビット整数で直接符号なし演算のオーバーフローを利用する実装もあるが、言語依存の振る舞いに気をつける必要がある。
- モジュロ演算は重いので、適切な最適化（累乗を事前計算、ループ外での乗算回数削減）を行う。
- テキストやパターンに非ASCII文字が含まれる場合は文字の数値化方法を決める（UTF-8 のバイト列に対してハッシュを取るか、コードポイント列にするかなど）。
- 基数 b を 256 や 127 などに固定することが多いが、文字分布によっては別の値が有利になることがある。
複数パターン検索への拡張
Rabin–Karp法は複数のパターンを同時に検索する場面で強みを発揮します。m1,m2,… の複数長のパターンがある場合、それぞれのハッシュをテーブルに格納しておき、テキストのウィンドウハッシュと照合していくだけです。全パターンが同じ長さであれば単純ですが、長さが異なる場合は長さごとにローリングウィンドウを別管理するか、ハッシュセットを工夫して扱います。
複数パターンの典型応用にはマルチキーワード検索や文書の重複検出、マルウェアシグネチャ検出などがあります。Aho–Corasick のような別手法と比較して実装が容易で、特にパターン数が少ないかハッシュ関数をうまく整えられる場合に有利です。
計算量解析
平均的な場合、Rabin–Karp法は各ウィンドウのハッシュ更新が O(1) で、ハッシュ一致が稀であれば文字ごとの完全照合は少ないため総時間は O(n + m) に近くなります。しかし最悪ケースでは、ハッシュが頻繁に衝突し、各位置で m 文字比較が発生すると O(nm) になります。これが理論的な弱点ですが、実務上は良いハッシュ関数選択で問題になりにくいです。
KMP や Boyer–Moore との比較
KMP（Knuth–Morris–Pratt）は常に O(n + m) の時間保証を持ち、ハッシュ衝突の心配がありません。Boyer–Moore 系は実データで非常に高速になることが多く、後方からの比較によりスキップが大きくなります。一方で Rabin–Karp は実装が簡単で、特に複数パターン同時探索や長いパターン群を扱う時に有利です。選択は用途とデータ特性次第になります。
実用的応用例
- 文書類似度検出や重複検出（文書の部分一致を素早く検出）
- ウイルスやマルウェアのシグネチャ検出（簡易フィルタとして）
- コードの差分検出やプラグiarism チェッカの一要素
- データベースのワイルドカード検索やログ解析でのパターン検出
最適化テクニック
実装を高速化するためのテクニック：
- 累乗 b^{m-1} を事前計算しておく
- モジュロに Mersenne 素数（2^61-1 など）を選んで高速な剰余処理を行う
- 64ビットの回り込みを利用したハッシュを用い、あえてモジュロ演算をしない高速化戦略（その場合は二重ハッシュで安全性を補う）
- 一致確認は短絡的に先頭や末尾だけ比較して高速に棄却するヒューリスティクスを入れる
実装例の注意点まとめ
実装時は次の点をチェックしてください：文字エンコーディング、整数オーバーフロー、負の値の正規化、二重ハッシュの導入の可否、パターン長がテキスト長より大きい場合の処理、長さが異なる複数パターンの管理方法。これらを適切に扱えば実世界での信頼性は高くなります。
まとめ
Rabin–Karp法はローリングハッシュを用いた文字列検索アルゴリズムで、理論と実装のバランスが良い実用的な手法です。平均的には高速かつ簡潔で、複数パターン探索や大規模データでの前処理的なフィルタとして有効です。一方、ハッシュ衝突による最悪時間が理論的な弱点であるため、ハッシュ関数やモジュロの選択、二重ハッシュなどの工夫が重要になります。用途に応じて KMP や Boyer–Moore と使い分けると良いでしょう。
参考文献
Rabin–Karp algorithm — Wikipedia
String Hashing — CP-Algorithms (e-maxx)
Rabin–Karp Algorithm for Pattern Searching — GeeksforGeeks
Lecture notes on randomized pattern matching — Stanford (参考講義資料)
投稿者プロフィール
