"音標的"な検索を実装するにはどうすればいいですか

Question

現在、私は検索アルゴリズムを強化しようとしています。

理解を深めるため、ここには現在のロジックがあります。
dbにn個のキーワードが関連付けられたオブジェクトがあります。データベースでは、これは2つのテーブル（Object,Keyword）によって解決され、KeywordテーブルのFKはObjectです。私は自分のsearchtreesを構築しているときに、オブジェクトのすべてのキーワードの行の値（広告：ウムラウトを削除する、小文字に変換する、など）を作成します。同じ変換ルーチン（NormalizeSearchPattern()）が検索パターンで実行されます。 AND -searchとキーワードをサポートしています。最小長は2文字です。

検索アルゴリズムが（この例では、最適化されていません）現在fast-reverse-searchの変形である：

bool IsMatch(string source, string searchPattern) 
{ 
    // example: 
    // source: "hello world" 
    // searchPattern: "hello you freaky funky world" 
    // patterns[]: { "hello", "you", "freaky", "funky", "world" } 

    searchPattern = NormalizeSearchPattern(searchPattern); 
    var patterns = MagicMethodToSplitPatternIntoPatterns(searchPattern); 
    foreach (var pattern in patterns) 
    { 
     var success = false; 
     var patternLength = pattern.Length; 
     var firstChar = pattern[0]; 
     var secondChar = pattern[1]; 

     var lengthDifference = input.Length - patternLength; 
     while (lengthDifference >= 0) 
     { 
      if (source[lengthDifference--] != firstChar) 
      { 
       continue; 
      } 
      if (source[lengthDifference + 2] != secondChar) 
      { 
       continue; 
      } 

      var l = lengthDifference + 3; 
      var m = 2; 
      while (m < patternLength) 
      { 
       if (input[l] != pattern[m]) 
       { 
        break; 
       } 
       l++; 
       m++; 
      } 

      if (m == patternLength) 
      { 
       success = true; 
      } 
     } 
     if (!success) 
     { 
      return false; 
     } 
    } 
    return true; 
} 

正規化はして行われます（この例では、最適化されていない）

string RemoveTooShortKeywords(string keywords) 
    { 
     while (Regex.IsMatch(keywords, TooShortKeywordPattern, RegexOptions.Compiled | RegexOptions.Singleline)) 
     { 
      keywords = Regex.Replace(keywords, TooShortKeywordPattern, " ", RegexOptions.Compiled | RegexOptions.Singleline); 
     } 

     return keywords; 
    } 

    string RemoveNonAlphaDigits(string value) 
    { 
     value = value.ToLower(); 
     value = value.Replace("ä", "ae"); 
     value = value.Replace("ö", "oe"); 
     value = value.Replace("ü", "ue"); 
     value = value.Replace("ß", "ss"); 

     return Regex.Replace(value, "[^a-z 0-9]", " ", RegexOptions.Compiled | RegexOptions.Singleline); 
    } 

    string NormalizeSearchPattern(string searchPattern) 
    { 
     var resultNonAlphaDigits = RemoveNonAlphaDigits(searchPattern); 
     var resultTrimmed = RemoveTooShortKeywords(resultNonAlphaDigits); 
     return resultTrimmed; 
    } 

だから、これはあります私がに実装したsourceとsearchPatternのバリアント（上記のとおり、ウムラウト、大文字と小文字の違いなど）にしか対応できないことは明らかです。 。 - >「ハウザー

• 単数/複数
• misstyping（例えば "hauserr" <：それがダウンしていたときに
  しかし、私はアルゴリズムを強化すべきか（またはNormalizeSearchPattern()）は非感受性が高いことが「）
• ...

ただ、設計の詳細を知るために：このアプリは、C＃で行われ
を、それは検索を保存します木やオブジェクトを静的変数に入れておくと（initで一度だけデータベースに問い合わせる）、パフォーマンスは優れていなければなりません（現在500.000行の値は300msec以内に照会されます）。

Answer 1

またTrigram and Bigram search matching algorithmに興味があるかもしれない：

トライグラム検索は、対象物の正確な構文やスペルは正確には知られていないときにテキストを検索する強力な方法であります。これは、入力された検索語の3文字の文字列の最大数、すなわちほぼ一致するものと一致するオブジェクトを見つける。しきい値はカットオフポイントとして指定することができます。その後、結果はもはや一致と見なされません。

Answer 2

levenstein distanceと呼ばれるものを見てみると、ある単語を別の単語に変更するために必要な変更の数が計算されます。

非常に単純な単語を示します。

複数の一致の場合、複数形が単数形と大きく異なる場合でもエイリアス表を使用できますが、依然として一致させる必要があります。私は別の質問の提案に対して、Googleがエイリアスリストを使用していると仮定します。

Answer 3

Soundexアルゴリズムを調べる必要があります。これは、類似の発音単語（およびややスペルミス）が同じ（または類似の）値にマッピングされるように、単語を発音スペースに変換するアルゴリズムです。

• のSoundex、センサスで使用するため エンコード姓に開発されました：other phonetic algorithms on wikipediaのリストがあります。 Soundexコードは、1文字が の3文字で構成された4文字の 文字列です。
  • スウェーデンの とよりよく一致する姓と ゲルマン起源に設計されたSoundexの洗練されたDaitch-Mokotoff Soundex。 Daitch-Mokotoff Soundexコードは、 の6桁の文字列です。
  • KölnerPhonetikはSoundexに似ていますが、 ドイツ語にはより適しています。
  • メタフォンとダブルメタフォン。ほとんどの場合、名前の他に、 英語の単語で使用するのに適しています。 多くの一般的なスペルチェッカー のメタファアルゴリズムが基本です。 同じ文字に類似した音素をマッピングし
  • Miracode
  • ニューヨーク州の同定およびインテリジェンス・システム（NYSIIS）、 。結果は、 の文字列であり、復号器なしで という読者が発音することができます。
  • 1977年にWestern Airlinesによって開発されたMatch Rating Approach - この アルゴリズムは符号化と範囲 の比較技術を持っています。