快速動態模糊搜索C＃中的100k +字符串＃

Question

假設它們是預先加載的股票代碼，輸入到文本框中。我正在尋找可以複製的代碼，而不是要安裝的庫。

這個靈感來自於這樣一個問題：

Are there any Fuzzy Search or String Similarity Functions libraries written for C#?

的編輯距離算法似乎運作良好，但它需要時間來計算。 是否有任何優化的事實，查詢將需要重新運行，因爲用戶鍵入一個額外的信件？我有興趣展示每個輸入的最多10場比賽。

Answer 1

您需要確定字符串周圍的匹配規則。是什麼決定了「類似的字符串」

• 數量匹配字符的
• 數量的不匹配字符
• 類似長度
• 錯別字或拼音錯誤
• 業務特定的縮寫
• 必須以相同的子字符串
• 必須以相同的子字符串結尾

我已經完成了很多字符串匹配算法的工作，還沒有找到符合我的特定要求的任何現有庫或代碼。回顧他們，從他們那裏借鑑想法，但你總是必須自定義和編寫你自己的代碼。

Levenstein算法不錯，但有點慢。我在Smith-Waterman & Jaro-Winkler算法方面取得了一些成功，但我發現的最好的方法是Monge（從記憶中）。然而，閱讀原始研究並確定他們爲什麼編寫了他們的算法和他們的目標數據集是值得的。

如果您沒有正確定義要匹配和衡量的內容，那麼您可以在預期匹配中發現意外匹配的高分和低分。字符串匹配是非常具有域特定。如果你沒有正確定義你的域名，那麼你就像一個沒有頭緒的漁夫，不停地投擲鉤子並希望獲得最好的結果。

Answer 2

This blog post介紹了一些進入Lucene這方面的工作。他們能夠使用有限狀態轉換器（自動機）相當有效地實現Levenshtein距離模糊匹配，編輯距離爲2。儘管代碼是開源的，但代碼全部在Java中，並且有點複雜。

但基本的想法很簡單：把你的字典想象成一個巨大的字母狀態樹。在狀態0，你沒有字母。在狀態1，您承認任何可能是單詞第一個字母的字母。狀態2由狀態1調節;如果第一個字母是'x'，則下一個狀態只允許可能跟隨x的字母（位置2）。等等。

現在對於Levenshtein匹配，您可以遍歷字母樹，同時允許出現一些錯誤：刪除，插入（單字母通配符）和可能的轉置（Levenshtein的一個很好的擴展是將轉置作爲單個編輯比2）。您必須保持狀態，以便跟蹤允許進行多少次編輯。這可以非常有效地完成 - 當你輸入「拼寫建議者」的時候，這個速度肯定足夠快。