アルゴリズム・データ構造図鑑 · 基礎から応用へ

Rabin–Karp法:ローリングハッシュで候補を絞る

窓を一文字ずつ進めてハッシュを更新し、衝突の検証と期待時間・最悪時間を区別する。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. ハッシュが同じなら候補にする
  2. 123から234へ窓を進める
  3. 期待値と最悪値を混同しない
  4. 同じ長さの複数パターンへ広げる
  5. この記事をロゲイアに質問する理解を確かめる

ハッシュが同じなら候補にする

Rabin–Karp法は、長さmのパターンとテキストの各長さmの窓をハッシュ値で比べます。値が違えばその窓は一致しませんが、値が同じでも内容が等しいとは限りません。実際の文字列を比較して確かめる版と、ハッシュの一致をそのまま答えにする確率的な版を区別します。ハッシュは暗号学的な秘密を守る目的ではなく、候補を素早く絞るための指紋です。一般のハッシュ表と同様、衝突の性質と入力の与えられ方が性能や保証に影響します。

123から234へ窓を進める

十進の数字列で窓123を234へ進めるなら、先頭の1が担っていた100を引き、残り23を10倍し、新しい4を足せば234です。実際には法qを取った値で同じ操作を行い、先頭の桁に対応するr^(m−1) mod qを前計算します。q=17なら123と140はどちらも余り4で、異なる内容でも衝突します。余りが同じことだけで一致を返すと誤答になります。負の剰余の扱いが言語で異なる場合には、減算後の正規化にも注意します。

期待値と最悪値を混同しない

各窓のハッシュ更新が定数時間なら、一致候補が少ない場合は前処理と走査を合わせてO(n+m)に近い処理になります。しかし検証版で多数の窓が衝突し、毎回長さmの比較が必要なら最悪O(nm)です。法や基数の選択、乱択、入力の仮定を明記せず、常に線形時間だとは言えません。検証を省けば実行時間を抑えやすくなりますが、今度は偽陽性の可能性を持ちます。正確な一致検索なのか、衝突確率を許す探索なのかが仕様の分岐点です。

同じ長さの複数パターンへ広げる

複数の同じ長さのパターンのハッシュを集合に入れておけば、本文の一つの窓から候補となるパターン群を調べられます。ただし一致したハッシュに複数のパターンが対応する場合もあるため、内容確認の費用を別に数えます。異なる長さを無制限に増やすと窓の管理も増え、一回の走査だけという説明は崩れます。空パターン、m>n、繰り返し文字、意図的に衝突する小さな法で試験すると、境界処理と検証の欠落を見つけやすくなります。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 10

学習コースから次を選ぶ