Rabin-Karp 文字列照合
Rabin-Karp は固定長のテキスト窓のハッシュ指紋を比べる。窓が一つずれるたびにローリングハッシュが指紋を定数時間で更新するので、多くの窓は一回のハッシュ比較で除外でき、指紋が同じ窓だけを文字ごとに検証する。全て一致して初めて採用する。
ハッシュは文字列を小さな整数へ圧縮するため、異なる文字列が同じ値を持ちうる。正確さを保証するのは最後の文字比較だ。ハッシュ一致は検証を始める条件で、一致の証明ではない。本レッスンは計算を読みやすくするため十進数字を使うが、通常の文字も数値に写像して同じ方法を使える。
指紋をローリング更新する
パターン長を m、基数を 10、法を q とする。窓 31428 は十進数として扱え、アルゴリズムは q で割った余りだけを持つ。
最上位の因子を high = 10^(m - 1) mod q で求める。パターンと最初の窓は、一桁ずつ hash = (10 × hash + digit) mod q で初期化する。
窓を一位置右へ動かす。左から出る数字が out、右から入る数字が in なら、次の指紋は：
next = (10 × (windowHash - out × high) + in) mod q
最上位の寄与を引き、10 を掛けて残りを左へずらし、新しい一の位を加える。旧指紋、退出する数字、入る数字だけで計算でき、他の m - 1 文字は読み直さない。
JavaScript の % は負の余りを返すことがあるため、(raw % q + q) % q で正規化する。負の中間値そのものは誤りではなく、同じ剰余類の別表現だ。ただし保存と比較には統一した表現を使う。
Rabin-Karp のステップ
既定のテキストは 3142831415、パターンは 31415、q = 13。
- 長さは 5 なので
high = 10^4 mod 13 = 3。 - パターンを一桁ずつ計算すると指紋は 7。最初の窓
31428も 7 になる。 - 指紋が合うので文字を検証する。3、1、4 は合うが、オフセット 3 で
2 != 1となる。一致ではなく衝突だ。 - 一位置右へ動かすと、出る数字も入る数字も 3。生の計算は
10 × (7 - 3 × 3) + 3 = -17。法 13 で正規化すると 9 で、窓14283の指紋になる。 - ローリングと比較を続け、ハッシュが異なる窓では文字検証を省く。
- シフト 5 で窓が
31415になり、指紋は再び 7。五文字全てが合うので 5 を返す。
全体でハッシュ検査六回、ローリング五回、文字検査九回。最初の四文字検査でシフト 0 の偽候補を除き、残る五回でシフト 5 の一致を確認する。
法が処理量を変える理由
テキストとパターンを固定して q を 13 から 101 に変えると、答えは同じだが最初の偽候補が消える。
31428 と 31415 の差は 13 なので、法 13 では両方とも 7。法 101 ではそれぞれ 17 と 4 になり、最初の窓はハッシュで除外され、本当の一致だけが文字検証に進む。
大きい法は通常、偶然の一致を減らすが、衝突をなくすことはできない。実装では大きな法、マシンワードのハッシュ、独立した二つのハッシュなどを使う。正確な検索には最後の等値検査が必要で、省くならアプリケーションが衝突リスクを明示的に受け入れることになる。
正しさ
同じ文字列は同じ基数と法で同じハッシュを持つため、ハッシュが異なる窓を除外しても一致を失わない。逆に、同じハッシュでも文字列が同じとは限らないので、一文字ずつ確認する。
ローリング式は、窓全体を再計算した多項式指紋と一致する。最上位項を除き、残りをずらし、新しい項を足すと次の窓の多項式になる。途中で剰余を取っても最終的な余りは変わらない。
時間計算量と空間計算量
テキスト長を n、パターン長を m とする。窓の走査は m ≤ n を前提にしている。
| 処理 | 時間 | 補助空間 |
|---|---|---|
| パターンと最初の窓の初期化 | O(m) | O(1) |
| 全窓のローリング | O(n - m + 1) | O(1) |
| 一候補の検証 | O(m) | O(1) |
| 衝突が少ないときの期待検索時間 | O(n + m) | O(1) |
| 最悪 | O(nm) | O(1) |
ローリング自体は線形だ。最悪コストは、多くの窓が候補になり、それぞれ m 文字近く比較してから失敗するときに生じる。衝突の連続プリセットでは、五つの窓がハッシュ検査を通るが一つも一致しない。弱いハッシュ、敵対的な入力、不適切な法はフィルターの効果を失わせる。期待線形時間はハッシュと入力の仮定に依存し、小さな固定の法が任意入力で保証するものではない。
Rabin-Karp を使う場面
一度の通常検索なら言語の組み込み検索が適している。等長の複数パターンはハッシュを保存し、一回のローリング走査を共有して、命中した窓だけを検証できる。重複断片や盗用候補の検出にもローリング窓を使え、衝突処理が必要になる。二次元照合では行方向、列方向の順にローリングできる。
単一パターンの KMP は衝突頻度によらない決定的 O(n + m) を持つ。Rabin-Karp の固定幅走査は等長パターンの一括処理へ広げやすい。用途に応じて選ぶ。
境界ケース
- パターンがテキストより長ければ窓がなく、
-1を返す。 - 空テキストと非空パターンでも
-1を返す。 - 一桁パターンも同じ式で動き、
high = 1。 - 幅を固定するので先頭ゼロは安全。
0012と12を同じ長さとして比較しない。 - 最後の合法なシフト
n - mも調べる。 - UI は非空パターンを要求する。表示関数は別途規約を示し、空パターンには 0 を返す。
よくある間違い
- ハッシュ一致ですぐ返す。既定の最初の窓で偽一致になる。
- 毎回 m 文字から窓ハッシュを再計算し、ローリング段階まで O(nm) にする。
out × highではなくoutだけを引き、桁の寄与を消せない。- 負になりうる余りを標準の指紋と直接比べる。正規化して保存・比較の表現を統一する。
- 教材用の小さな法を実負荷でも使い、検証候補を増やす。
- 全てのハッシュ命中を衝突と呼ぶ。検証前は候補であり、文字列が違った場合だけ衝突になる。
続けて学ぶ
同じ手法につながるレッスンや、次の概念への入口です。
鍵マークのあるレッスンの操作には有料アクセスが必要です。解説はすべて無料で読めます。
誤りや気になる点を見つけましたか？ フィードバックを送る。