ラビン-カープアルゴリズムの概要
1. 概要
コンピュータサイエンスでは、文字列検索とは、大きなテキスト内の1つ以上の文字列（パターンと呼ばれる）の場所を見つけることを意味します。
この記事では、Rabin-Karp文字列検索アルゴリズムについて説明します。 最初に、単純な文字列検索アルゴリズムについて説明します。 次に、ラビン-カープアルゴリズムについて説明し、例に適用します。
最後に、このアルゴリズムのいくつかのバリエーションについて説明します。
2. ナイーブアルゴリズム
2.1. 擬似コード
このアルゴリズムの考え方は単純です。 テキスト内のすべての可能な場所からパターンを検索しようとすることで機能します。
素朴なアプローチを表す次のアルゴリズムを検討してください。
の可能なすべての位置から始めて、パターンを一致させようとします。 開始位置ごとに、パターンとテキストの両方を繰り返して、それらに一致させようとします。
一致する場合は、回答を1つ増やします。 それ以外の場合は、最初に見つかった不一致でループを解除します。
2.2. 例
例として、次の場所で検索したい場合は、アルゴリズムの手順を見てみましょう。
このアルゴリズムの複雑さはです。ここで、はテキストの長さ、はパターンの長さです。
3. ラビン-カープアルゴリズム
まず、Rabin-Karpアルゴリズムで使用されるハッシュ関数の背景が必要です。 その後、ラビン-カープアルゴリズム自体に移ります。
3.1. ハッシュ関数
以前は、テキスト内のすべての位置からパターンを一致させる必要がありました。 これを改善するために、任意の文字列を整数値にマップできる関数を作成します。
つまり、文字列を取得して整数にマップする関数（ハッシュ関数と呼ばれる）が必要です。 これ以降、のハッシュ値をと呼びます。
ただし、すべての機能が役立つわけではありません。 ハッシュ関数は簡単に計算できるはずです。 また、事前計算を実行できる必要があり、事前計算では、線形時間で文字列のハッシュ値を計算できる必要があります。
さらに、前処理後、任意の部分文字列のハッシュ値を一定時間で計算できるようになります。
3.2. ハッシュ関数の例
おそらく、使用できる最も単純なハッシュ関数の1つは、文字列内の文字のASCIIコードの合計です。 簡単にするために、のASCIIコードを示すために使用します。 正式に：
プレフィックスの合計を使用してサブストリングのハッシュ値をすばやく計算できるため、このハッシュ関数は有効な選択です。
仮定して、いくつかの例を見てみましょう：
にもかかわらず、注意してください。 この場合、2つの異なる文字列が同じハッシュ値を持つ場合、衝突と呼ばれます。
原則として、ハッシュ関数が引き起こす衝突が少ないほど、それは優れています。 私たちのハッシュ関数は、文字の順序と位置を考慮していないため、多くの衝突があります。 後で、より優れたハッシュ関数について説明します。
説明したハッシュ関数を使用して、ハッシュ構造の次の実装を確認します。
最初の関数は、指定された文字列に対して事前計算を実行します。 文字列を反復処理し、文字列の文字のASCII値のプレフィックス合計を計算します。
2番目の関数は、特定の範囲のハッシュ値を計算するために使用されます。 これを行うには、範囲の先頭のプレフィックス合計を減算した後、範囲の末尾のプレフィックス合計を返します。 したがって、範囲内の値の合計を取得します。
事前計算関数の複雑さはです。ここで、は文字列の長さです。 また、ハッシュ計算関数の複雑さはです。
3.3. ラビン-カープ文字の主なアイデア
先ほど、ハッシュ関数とは何かを説明しました。 ハッシュ関数の最も重要な特性は、2つの文字列ととがあれば、それを安全に想定できることです。
ただし、の場合、2つの異なる文字列が同じハッシュ値を持つ可能性があるため、それを保証することはできません。
それでは、Rabin-Karp文字列検索アルゴリズムを見てみましょう。
テキスト内のパターンを探していると仮定します。 現在、の場所にいるので、がに等しいかどうかを確認する必要があります。ここで、はの長さに等しいです。
このアルゴリズムの最悪の場合の複雑さは依然としてです。ここで、はテキストの長さであり、はパターンの長さです。
ただし、優れたハッシュ関数を使用すると、予想される複雑さはになります。ここで、は一致数です。
この背後にある理由は、優れたハッシュ関数が衝突を引き起こすことはめったにないためです。 したがって、一致するものがない場合、2つのサブストリングを比較する必要はほとんどありません。 さらに、パターンが存在するかどうかだけを確認したい場合、最初の発生後に壊れることがあるため、複雑さはになります。
3.4. ラビン-カープ文字の例
Rabin-Karpがどのように機能するかを理解するために、セクション2.2で使用した例をもう一度見てみましょう。 素朴なアルゴリズムとは異なり、すべての場所でパターンを一致させる必要はありません。
マッチングプロセスを見てみましょう。
ナイーブアルゴリズムと比較すると、5つの位置のうち2つをチェックするだけで済みます。
次のセクションでは、ほとんどの誤検知を取り除くことができる、より優れたハッシュ関数について説明します。 したがって、チェックする必要のある場所の数が減ります。
4. 優れたハッシュ関数
4.1. 意味
以前、ASCIIコードの合計に基づくハッシュ関数について説明しました。 ただし、そのハッシュ関数は文字の順序や位置を考慮していませんでした。 たとえば、文字列の順列はすべて同じハッシュ値を持ちます。
代わりに、文字列をベースの数値として表現しようとします。ここで、はすべてのASCIIコードよりも大きい素数です。
例として、文字列があると仮定します。 ベースでのその表現は次のようになります。
一般に、長さのある文字列のハッシュ値は次のとおりです。
有効な記数法で文字列を表しているため、個別の文字列のハッシュ値は個別になります。 ただし、長い文字列を表す場合、ハッシュ値は巨大になります。 したがって、それらを計算して保存するのは非効率的です。
代わりに、はを法としてハッシュ値を計算します。ここで、は大きな素数（通常は約）です。 プライムが大きいほど、発生する衝突は少なくなります。
4.2. 実装
前に説明したように、前処理後、一定時間内に任意のサブストリングのハッシュ値を計算できるはずです。
長さの文字列内のすべてのプレフィックスのハッシュ値を計算してみましょう：
があることに注意してください。 これにより、線形時間でプレフィックス配列を計算できるようになります。 また、素数のさまざまな累乗を格納する配列を計算する必要があります。
ただし、一定時間内に任意の部分文字列のハッシュ値を計算する方法を見つける必要があります。
例として、の値を計算するとします。 結果はになります。
この値はで使用できますが、とに対応する用語を削除する必要があります。 これらの2つの用語はで利用できます。 ただし、からに移動するときは、それらに。を掛けました。
それらを削除するには、を乗算してから減算する必要があります。 したがって、 。
原則として、 。
これらの方程式の準備ができたので、次のハッシュ構造を実装しましょう。
事前計算の複雑さはです。ここで、は文字列の長さです。 また、ハッシュ関数の複雑さはです。
このハッシュ関数を使用すると、衝突の可能性が低くなります。 したがって、ほとんどの場合、ラビン-カープの予想される複雑さを達成できます。 ただし、ハッシュ関数に関係なく、一致するものが多い場合、アルゴリズムは依然として低速になります。
次のセクションでは、ラビン-カープの非決定論的バージョンについて説明します。
5. ラビン-カープ文字のバリエーション
5.1. 非決定論的バージョン
このバージョンの背後にある考え方は、それぞれが異なるモジュロ値とベースを持つ複数のハッシュ関数を使用することです。
2つの文字列が複数のハッシュ関数で等しいハッシュ値を持っている場合、それらが等しい可能性が非常に高いため、機密性の低いアプリケーションでは等しいと安全に想定できます。
これにより、ハッシュ値が等しい場合に文字列を1文字ずつチェックする代わりに、これらのハッシュ関数に完全に依存することができます。 したがって、このバージョンの複雑さはです。ここで、はテキストの長さ、はパターンの長さです。
5.2. 複数の等しい長さのパターン
Rabin-Karpアルゴリズムは、同じ長さである限り、複数のパターンを処理するように拡張できます。
まず、各パターンのハッシュ値を計算し、マップに保存します。 次に、テキスト内のある場所をチェックするときに、サブストリングのハッシュ値がマップで使用可能かどうかを一定時間でチェックできます。
このバージョンの予想される複雑さは、決定論的バージョンに適用された場合、です。ここで、はテキストの長さ、はすべてのパターンの全長、はすべての一致の全長です。 一方、を非決定論的バージョンに適用すると、複雑さはになります。
6. 結論
この記事では、文字列検索の問題について説明しました。
まず、ナイーブなアルゴリズムを調べました。
その後、ハッシュ関数に依存することにより、Rabin-Karpがこのアルゴリズムをどのように改善するかについて説明しました。 次に、優れたハッシュ関数の選び方を説明しました。
最後に、非決定論的バージョンのようなRabin-Karpのいくつかのバリエーションを調べ、複数のパターンにRabin-Karpを適用しました。
