如何實現類似「語音」的搜索

Question

目前我正試圖增強我的搜索算法。

爲了更好地理解，下面是它背後的當前邏輯：
我們有在db中連接n個關鍵字的對象。在數據庫中，這通過2個表（Object,Keyword）解決，其中Keyword -table具有FK到Object。當我構建搜索樹時，我創建了一個對象所有關鍵字的行值（ad：remove umlauts，轉換爲小寫，...）。搜索模式完成相同的轉換程序（NormalizeSearchPattern()）。我支持AND - 搜索和關鍵字的最小長度只有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; 
    } 

因此，這是相當直接的，因此很明顯，我只能用我在NormalizeSearchPattern()已經實現的source和searchPattern應對變種（如上面提到的：變音符號，大小寫區別，...）。

但是我應該如何提升算法（或NormalizeSearchPattern()）是不敏感的，當它歸結爲：

• 單數/複數
• misstyping（如 「hauserr」 < - >「豪瑟。 「）
• ...

只是爲了更多地瞭解設計：
這個應用程序是用C＃實現，它存儲的搜索樹和對象放在一個靜態變量中（在init中只查詢一次數據庫），性能必須非常好（目前500.000行值在300毫秒以內查詢）。

Answer 1

您可能也有興趣在Trigram and Bigram search matching algorithm：

八卦搜索是搜索文本的強大方法時，目標對象的確切的語法或拼寫不確知。它找到與輸入的搜索詞中最多三個字符的字符串相匹配的對象，即接近匹配。閾值可以被指定爲截止點，之後結果不再被視爲匹配。

Answer 2

嘗試尋找一種叫做levenstein distance它計算了許多變化是如何需要改變一個字到另一個。

很少變化表明非常類似的單詞。

對於複數匹配，你也可以使用別名表如果複數形式是單數很大的不同，但你仍然希望他們能夠匹配。我認爲Google會使用某種形式的別名列表來提供其他問題的建議。

Answer 3

您應該調查Soundex算法。它是一個將單詞轉換爲語音空間的算法，這樣類似的發音單詞（和有些拼寫錯誤的單詞）映射到相同（或相似）的值。還有的other phonetic algorithms on wikipedia列表：

• 探測法，這是發展到 編碼姓於人口普查。 Soundex代碼是四字符 由一個字母組成的字符串 後跟三個數字。
  • Daitch-Mokotoff Soundex，這是Soundex的改進設計，以 更好匹配斯拉夫姓氏和 日耳曼血統。 Daitch-Mokotoff Soundex代碼是由 六個數字組成的字符串。
  • KölnerPhonetik類似於Soundex，但更適合於 德語單詞。
  • Metaphone and Double Metaphone，適用於大多數 英文單詞，而不僅僅是名稱。 Metaphone算法是 許多流行的拼寫檢查器的基礎。
  • Miracode
  • 紐約州的識別和智能系統（NYSIIS）， 其相似音素映射到 相同的字母。結果是字符串 ，讀者 可以發音而不解碼。
  • 1977年西部航空公司開發的匹配評分方法 - 這種 算法有一個編碼和範圍 比較技術。