では、Michael RabinとRichard Karpはどのようにアルゴリズムをオーバークロックしましたか？
ブルートフォースがなぜそんなに遅いのですか？ おそらく、私たちが不必要な行動をしすぎているからでしょう。 次に、アイデアは内部サイクルを最適化するように見えます。 そしてどうやって？ 文字列を特徴付けるいくつかの数字で文字列を比較できます。
そのような数値があります 。 ハッシュ関数を使用して取得します 。
最初のアプローチ
「テンプレートと各サブストリングのハッシュコードを計算してみましょう。それらが同じ場合は、ここで偶然があります」のようなものが思い浮かぶでしょう。
独自のハッシュ関数を記述して問題を解決し、ハッシュコードが等しい場合にのみ文字列ごとにパターンと部分文字列を一致させるコードを追加してみましょう。 文字列のハッシュ関数を使用して、この文字列を構成する文字コードの合計を作成します。
private int GetHashOfString( string s)
{
int result = 0;
for ( int i = 0; i < s.Length; i++)
{
result += s[i];
}
return result;
}
部分文字列検索関数自体は次のようになります。
public int Match( string input, string pattern)
{
int inputLength = input.Length;
int patternLength = pattern.Length;
int patternHash = GetHashOfString(pattern);
int substringHash;
for ( int i = 0; i <= inputLength - patternLength; i++)
{
substringHash = GetHashOfString(input.Substring(i, patternLength));
if (patternHash == substringHash)
{
bool success = true ;
for ( int j = 0; j < patternLength; j++)
{
if (input[i + j] != pattern[j])
{
success = false ;
break ;
}
}
if (success)
return i;
}
}
return -1;
}
アルゴリズムをオーバークロックする
しかし、再び：各位置でハッシュコードを見つけるために、ブルートフォースとまったく同じアクションを実行します。 最適化する必要があります。 ハッシュ構築オプションを使用すると、後続の各ステップで計算を大幅に高速化できます。つまり、位置0にあった文字のASCIIコードを減算し、新しい文字コードを追加します。
コードは次のように変更されます。
...
int patternHash = GetHashOfString(pattern);
int substringHash = GetHashOfString(input.Substring(0, patternLength));
for ( int i = 0; i <= inputLength - patternLength; i++)
{
if (i > 0)
substringHash =
substringHash - input[i - 1] + input[i + patternLength - 1];
if (patternHash == substringHash)
...
オーバークロックを続けますか？
別のハッシュ関数を使用して、アルゴリズムをオーバークロックすることもできます。 これらのハッシュ関数の1つは、各部分文字列をある数体系の数として解釈します。その基数は大きな素数です。
新しいステップで以前の値からハッシュ値を取得する方法は？ テンプレートの長さは一定であるため、テンプレートの長さから1を引いた程度のベースを一度計算して記憶できます。maxBase= 61 ^（length – 1）。 スローされているコードの値を減算する代わりに、その値にmaxBaseを掛けた値、つまり 'a' * 61 ^ 3を減算します。
この後、新しいコードを追加し、取得した値にシステムのベースを掛ける必要があります（61）。
これは擬似コードとして書くことができます：
substringHash = substringHash - input[i - 1];
substringHash = substringHash + input[i + patternLength - 1];
substringHash = substringHash * base; // base –
別の質問：より長い行長のハッシュ（より正確には、十分に長いテンプレート長のハッシュ）はどうなりますか？ 61の6乗（7文字の長さ）は4バイト整数に収まりません。
「モジュロ算術」が助けになります。 32桁の整数に収まらない巨大な数値は保存しません。残りの部分を素数qで除算します。
念のため、「モジュロ算術」は次のようなアイデンティティに基づいていると言います。
(a + b + c) mod x = (a mod x + b mod x + c mod x) mod x
(a * b * c) mod x = (a mod x * b mod x * c mod x) mod x
アルゴリズムを実装します
そのため、ハッシュ関数は、選択されたベースベースを適切な程度まで乗算した文字コードの合計ではなく、qを法とするこの合計で構成されます。 qおよびbaseの値は、アルファベットの長さよりも大きく選択されます。つまり、ASCIIの場合は256を超え、Unicodeの場合は65536を超えます。
長さが3文字のstringの関数は次のようになります。
((ascii(s[0]) * base^2) mod q + (ascii(s[1]) * base^1) mod q + (ascii(s[2]) * base^0) mod q) mod q
テンプレートの長さは1回の検索で変更されないため、ベース^（長さ– 1）mod qは変更されません。 別の方法でこの数量の計算を取り出します。
private int GetMaxBase( int length, int q, int b)
{
int result = 1;
for ( int i = 0; i < length - 1; i++)
result = (result * b) % q;
return result;
}
前と同様に、ハッシュ関数のメソッドを作成します。
private int GetHashOfString( string s, int q, int b)
{
int result = 0;
int length = s.Length;
for ( int i = 0; i < length; i++)
result = (b * result + s[i]) % q;
return result;
}
検索機能自体：
public int Match( string input, string pattern, int b, int q)
{
int inputLength = input.Length;
int patternLength = pattern.Length;
qを法とする値ベース^（patternLength-1）を見つける
int maxBase = GetMaxBase(patternLength, q, b);
最初にテンプレートのハッシュ値と最初の部分文字列を見つけます
int patternHash = GetHashOfString(pattern, q, b);
int substringHash =
GetHashOfString(input.Substring(0, patternLength), q, b);
for ( int i = 0; i <= inputLength - patternLength; i++)
{
ハッシュ値が一致する場合-文字列を完全に比較します
if (patternHash == substringHash)
{
bool success = true ;
for ( int j = 0; j < patternLength; j++)
{
if (input[i + j] != pattern[j])
{
success = false ;
break ;
}
}
if (success)
return i;
}
最後のステップにいない場合、ハッシュ関数の新しい値を見つけます
if (i != inputLength - patternLength)
substringHash =
(b * (substringHash - input[i] * maxBase) +
input[i + patternLength]) % q;
負の数を取得する場合は、正数にしてください:)
if (substringHash < 0) substringHash += q;
}
return -1;
}
ついに
これで完了です。 このアルゴリズムの時間コストは、最悪の場合であっても、ブルートフォースアルゴリズムに劣るものではなく、平均してアルゴリズムのインジケーターを見るのは非常に楽しいことです。
近い将来、他の人々がどのように動いているかについて書き、効果的な部分文字列検索アルゴリズムを見つけようとすることを願っています。 最後まで読んでくれた人に感謝します。
テストプロジェクトはここからダウンロードできます。