模糊句子搜索算法

Question

假設我有一組短語 - 約10 000個 - 的平均長度 - 7-20個單詞，我希望找到某個給定的短語。我正在尋找的短語可能會有一些錯誤 - 比如錯過一兩個單詞，有些單詞放錯了位置，或者是一些隨機的單詞 - 例如我的數據庫中包含「當我騎着紅色的自行車時，我看到了克莉絲汀」，而我「當我騎着藍色的自行車，看到克里斯蒂娜時」，或者「我騎着自行車，我看到了克里斯蒂娜和馬裏恩」。對這個問題有什麼好的方法？我知道萊文斯坦的距離，我也認爲這個問題可能並不容易，很好的解決方案。

Answer 1

一個好的文本搜索引擎將提供諸如你所描述的功能，fsh。一種典型的方法是創建一個與任何單詞發生匹配的查詢，並使用基於彼此接近發生的詞的數量的權重對結果進行排序，並且對它們的發生概率進行相反的加權，因爲不常見的單詞會少一些很可能偶然發生。有一種稱爲信息檢索的完整理論，但也許你知道這一點。此外，您希望確保通過規範化案例，標點符號等並應用一些基本的語言轉換（詞幹）來解決詞級模糊問題，並且在某些情況下引入同義詞詞典，特別是在有領域知識的情況下可用於調節它。

如果你對這個東西感興趣，試試開源搜索引擎，this article by Vik從2009年的角度給出了一個合理的調查，this one by Middleton and Baeza-Yates給出了一個很好的詳細介紹該主題。