それが私が書くことを決めた理由ですが、多かれ少なかれスムーズに始めるために、テキスト検索の基礎に関するいくつかの入門記事の形で紹介をします。
「普通の」人が「通常の」テキストで文字のサブシーケンスを見つける必要があるとき、彼はほぼ常に、つまり、必ずしも完全に一致するとは限りません。テキストに間違いがあるかもしれません。検索テンプレートから。
したがって、2つのタイプの検索、Exact String Matching AlgorithmとFuzzy String Matching Algorithmを区別できます。
完全一致検索
完全一致検索は実装が簡単ですが、最も単純な実装はブルートフォースであり、変換ブルートフォースアルゴリズムに従って呼び出されます。
int Match( string input, string pattern)
{
int inputLength = input.Length;
int patternLength = pattern.Length;
for ( int i = 0; i <= inputLength - patternLength; i++)
{
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;
}
このアルゴリズムは、ヌル文字で始まる同じ長さの入力文字列の一部に検索パターンを一致させようとします。 この試行が失敗した場合、最初の文字から照合が行われます。
ファジー検索
ファジー検索には何がありますか？ 原則として、ファジー検索は、すでに作成されたアルゴリズムをわずかに変更することで編成できます。
しかし、最初に、少し理論。
整数kと、サンプルからの考慮された部分文字列の距離（距離）の関数が与えられます。 距離（s）<kとなる部分文字列sを見つける必要があります。
ハミング距離
最も簡単なオプションは、同じ長さの2行の遠隔性を探すことです-対応する位置で不一致の文字の数、または同じ行を得るための置換の数を決定します。これは本質的に同じです。 このオプションはハミングによって提案されたため、遠隔機能はハミング距離と呼ばれます。
レーベンシュタイン距離
異なる長さの文字列を比較する場合は、削除および挿入操作を使用する必要があります。
2つのオプションもあります。
- 距離関数または距離dは、問題の行から目的のテンプレートを取得するために必要な置換、削除、または挿入の数として定義されます。
- dは、目的のテンプレートを取得するための部分文字列の変更の価格の合計として定義されます。ここで、
- 撤去価格= 1
- 広告掲載価格= 1
- 交換価格= 2（最初に1のシンボルを削除し、1の価格で目的のシンボルを挿入します）
ファジー検索を使用して、スペルをチェックするときに可能な修正を見つけることができます。主なことは、kを小さくしすぎないことです。そうしないと、Firefoxのような不具合が発生する可能性があります。
総当たりアルゴリズムでファジー検索を実装してみましょう。 内側のループを変更して、サブストリングごとにハミング距離を見つけます。 また、もう1つのパラメーターが必要です-k。 この場合、私の意見では、ゼロから1の範囲で実数kを使用する方が便利です。 この数値は、不一致の最大割合を示します。 その場合、式はわずかに異なります。
距離（s）<=長さ（s）* k。
実装：
int Match( string input, string pattern, double k)
{
if (k < 0 || k > 1)
throw new ArgumentException( "Invalid value for coefficient" , "k" );
int inputLength = input.Length;
int patternLength = pattern.Length;
for ( int i = 0; i <= inputLength - patternLength; i++)
{
int distance = 0;
for ( int j = 0; j < patternLength; j++)
{
if (input[i + j] != pattern[j])
{
distance++;
}
}
if (distance <= k * patternLength) return i;
}
return -1;
}
そして、良識のための小さなリファクタリングコード：
public int Match( string input, string pattern, double k)
{
if (k < 0 || k > 1)
throw new ArgumentException( "Invalid value for coefficient" , "k" );
int inputLength = input.Length;
int patternLength = pattern.Length;
for ( int i = 0; i <= inputLength - patternLength; i++)
{
if (GetDistance(input.Substring(i, patternLength), pattern) <= k * patternLength)
return i;
}
return -1;
}
private int GetDistance( string subString, string pattern)
{
int changesCount = 0;
int patternLength = pattern.Length;
for ( int i = 0; i < patternLength; i++)
{
if (subString[i] != pattern[i])
changesCount++;
}
return changesCount;
}
要約すると、提示されたアルゴリズムは非常に非効率的ですが、このトピックはテキスト検索の紹介以外のふりをするものではありません。
ここで 、テストを含むプロジェクトアーカイブをダウンロードできます。
ps次に、一連の「ダミーの解析」という形で努力を続ける予定です。