Rabin-Karp 法

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /rabin-karp#noredirect を利用してください。
name
Rabin-Karp 法
short description
Rabin-Karp 法とは、複数のパターン文字列をまとめて扱える乱択の文字列検索アルゴリズムのひとつ。$k$ 個のパターン文字列 $P_0, P_1, P_2, \dots, P _ {k-1}$ のそれぞれについて $\Theta(\sum \vert P_i \vert)$ などをかけてハッシュ値を求めておくことで、与えられたテキスト文字列 $T$ に対し平均 $O(\vert T \vert)$ などでこれらの検索ができる。ハッシュ関数は固定ではないが、ローリングハッシュが使われることが多い。
input
$k$ 個のすべて長さが等しいパターン文字列 $P_0, P_1, P_2, \dots, P _ {k-1}$ およびテキスト文字列 $T$
output
パターン文字列 $P_0, P_1, P_2, \dots, P _ {k-1}$ のどれがテキスト文字列 $T$ に含まれるか。含まれるならその位置も求める。
time complexity
前処理には $\Theta(\sum \vert P_i \vert)$ など、検索には平均 $O(\vert T \vert)$ など

概要

Rabin-Karp 法とは、複数のパターン文字列をまとめて扱える乱択の文字列検索アルゴリズムのひとつ。$k$ 個のすべて長さが等しいパターン文字列 $P_0, P_1, P_2, \dots, P _ {k-1}$ が与えられたとき、性質の良いハッシュ関数 $H$ を用意しておき、パターン文字列のそれぞれについてハッシュ値 $H(P_0), H(P_1), H(P_2), \dots, H(P _ {k-1})$ を $\Theta(\sum \vert P_i \vert)$ などをかけて求めておく。ただし、ハッシュ関数 $H$ の性質が良いとは、与えられた文字列 $T$ に対し、その長さ $\lvert P_i \rvert$ の部分文字列たちについて、それらのハッシュ値のすべてを高速に計算できるということである。このとき、与えられたテキスト文字列 $T$ に対しての検索が期待計算量 $O(\lvert T \rvert)$ などでできる。ハッシュ関数は固定ではないが、ローリングハッシュが使われることが多い。

Rabin-Karp 法は、競技プログラミング以外では、ハッシュ値が一致したときに文字列が実際に一致しているか愚直に確認する Las Vegas アルゴリズムとして用いられることが通常である1。 しかし競技プログラミングにおいては、ハッシュ値が一致したときの確認を省略して Monte Carlo アルゴリズムとして用いられることが多い。 また、用途によっては、いずれかのパターン文字列が含まれるかの判定のみやその出現位置をひとつ構成するのみでよい場合と、それぞれのパターン文字列について出現位置をすべて報告する必要がある場合とがある。 これらの組合せは $4$ 通りあるが、ものによっては計算量がすこし変化する。 それぞれのパターン文字列について出現位置をすべて報告することを考えたとき、Las Vegas アルゴリズムの形であれば出現位置の報告ごとに $\Theta(\lvert P_i \rvert)$ かかるので入力によっては計算量は $\Omega(\lvert P_i \rvert \cdot \lvert T \rvert)$ となってしまう23が、Monte Carlo アルゴリズムの形であればなお期待計算量 $O(\lvert T \rvert)$ のままである。

詳細

(省略)

メモ

参考文献

関連項目

外部リンク

注釈

  1. Rabin と Karp による提案論文においてもアルゴリズムイントロダクションでの説明においても、Rabin-Karp 法はハッシュ値が一致したときは厳密比較をするものとして説明されている。 

  2. たとえば、パターン文字列とテキスト文字列がすべて同じ文字からなる場合や、パターン文字列がアルファベット $\Sigma$ に対し $\lvert \Sigma \rvert^{\lvert P_i \rvert}$ 個あるような場合など。 

  3. パターン文字列の個数 $k$ が十分小さいもののみを入力として考えれば平均計算量 $\Theta(\lvert T \rvert)$ が言える。 

  4. 乱択アルゴリズム紹介(行列乗算の検査&多項式等価性の検査) | Preferred Networks Research & Developmentarchive.org