ラビン-カープ文字列検索アルゴリズム

ラビン-カープ文字列検索アルゴリズム

ラビン-カープ文字列検索アルゴリズムは、マイケル・ラビンとリチャード・カープによって開発された、ハッシュ関数を利用してテキストから特定のパターン（サブ文字列）を探し出すためのアルゴリズムです。このアルゴリズムは、単一のパターンの検索にはあまり用いられませんが、理論的に重要な意味を持ち、特に複数パターンの検索においてその効果を発揮します。

アルゴリズムの概要

テキストの文字数を n、パターンの文字数を m とした場合、ラビン-カープ法の平均および最良の実行時間は O(n) となります。しかし、最悪の場合には O(nm) の時間がかかることがあります。このため、単一のパターン検索には他のアルゴリズムがより適している場合があります。

しかし、ラビン-カープ法には、k 個の文字列のいずれかにマッチする部分を検索するのに要する時間が k に依存せず、平均で O(n) となるという特徴的な利点があります。この特性が、複数パターンの検索において非常に有効に働きます。

応用例：盗作の検出

ラビン-カープ法の応用例として、盗作の検出が挙げられます。例えば、学生が論文を執筆した際、教授がその論文が既存の資料からの剽窃であるかどうかを判断するために、ラビン-カープ法を用いることができます。具体的には、論文内の各文が、教授が事前に収集した資料に含まれているかどうかを効率的にチェックすることができます。この際、大文字と小文字の区別や句読点を無視することで、微妙な修正による盗作も検出できます。このケースでは、検索対象の文字列数が非常に多くなるため、単一文字列検索アルゴリズムでは現実的ではありません。

文字列検索アルゴリズムの比較

文字列検索アルゴリズムの基本的な問題は、n 文字のテキストから m 文字のサブ文字列（パターン）を検索することです。例えば、「Hello sunshine in this vale of tears.」というテキストから「sun」という文字列を探すような場合です。

最も単純なアルゴリズムは、テキスト内のすべての可能な位置でサブ文字列を比較するというものです。この方法は、多くの場合にうまく機能しますが、最悪の場合には非常に時間がかかることがあります。例えば、1000万個の「a」で構成されるテキストから、1万個の「a」の後に「b」が続く文字列を検索する場合などです。

クヌース-モリス-プラット法（KMP法）では、各文字を一度だけ調べるように事前の計算を行うことで、検索時間を O(n) に短縮できます。ボイヤー-ムーア法では、可能な限りスキップすることで繰り返し回数を減らし、文字列を調べる回数を最良の場合 n/m 回にまで減らすことができます。

ラビン-カープ法におけるハッシュ関数の利用

ラビン-カープ法では、単純に比較するのではなく、ハッシュ関数を用いて、現在見ているテキストとパターンが同じであるかどうかを高速にチェックします。ハッシュ関数は、文字列を数値（ハッシュ値）に変換する関数です。例えば、「hello」という文字列のハッシュ値が 5 であるとします。

ラビン-カープ法では、文字列が等しいならばハッシュ値も等しいという事実を利用します。このため、サブ文字列のハッシュ値を計算し、同じハッシュ値を持つサブ文字列を見つけることで、検索を効率化します。

ただし、ハッシュ値は限られた範囲の数値であるため、異なる文字列が同じハッシュ値を持つことがあります。これをハッシュ衝突と呼びます。ハッシュ衝突が発生した場合、文字列そのものを比較する必要があります。しかし、ハッシュ関数が適切であれば、ハッシュ衝突はまれにしか発生せず、平均検索時間は小さく保たれます。

ラビン-カープ法のアルゴリズム

以下にラビン-カープ法のアルゴリズムを示します。

1. パターン（`sub`）のハッシュ値を計算する（`hsub`）。
2. テキストの最初の m 文字のハッシュ値を計算する（`hs`）。
3. テキスト全体に対して、以下の処理を繰り返す。
1. `hs` と `hsub` が等しい場合、テキストとパターンを実際に比較する。
2. 一致した場合、テキスト中のパターンの開始位置を返す。
3. 次のテキストのサブ文字列のハッシュ値を計算し、`hs` を更新する。

ローリングハッシュ

効率的にハッシュ値を計算するために、ローリングハッシュと呼ばれる手法が用いられます。ローリングハッシュは、サブ文字列のハッシュ値を定数時間で計算することを可能にします。例えば、文字列を構成する文字の値の合計をハッシュ値とすることができます。この場合、次のハッシュ値は、現在のハッシュ値から先頭文字の値を引いて、末尾に追加された文字の値を足すことで計算できます。

使用されるハッシュ関数

ラビン-カープ法の性能は、テキストのサブ文字列のハッシュ値を効率的に計算することにかかっています。一般的なローリングハッシュ関数として、大きな素数を基数とするものが挙げられます。例えば、基数を 101 とし、サブ文字列「hi」のハッシュ値は、各文字のASCIIコードを基数で累乗した値を合計することで計算できます（この例では 104 101^1 + 105 101^0 = 10609 となります）。

ラビン-カープ法と複数パターン検索

ラビン-カープ法は、最悪の場合には他のアルゴリズムよりも低速になりますが、複数パターンの検索においては優れた性能を発揮します。

テキストから k 種類の固定長パターンのいずれかに一致する部分を検索する場合、ブルームフィルタや集合を用いることで、ラビン-カープ法を効率的に利用できます。この場合、k 個のパターンの検索を O(n + k) の時間で実行できることが期待されます。

まとめ

ラビン-カープ法は、ハッシュ関数を利用することで文字列検索を効率化するアルゴリズムです。単一パターンの検索には他のアルゴリズムが適している場合もありますが、複数パターンの検索においてはその効果を発揮し、盗作検出などの応用例があります。ローリングハッシュを用いることでハッシュ値の計算を効率化し、複数パターンの検索を高速化することが可能です。

もう一度検索