字符串模糊查詢

Question

這是一個面試問題。

給定一個由名稱組成的文件，您將使用什麼數據結構來驗證名稱是否在列表中。如果我們說某個名稱與文件中的名稱相差不超過一個字符，則該名稱有效？

Answer 1

我想說它取決於上下文：如果你有數百萬個名字，一個合同履行和一個產品爲你做，那麼我會說去爲它，忘了自己寫。

但是，在面試問題的背景下，我的建議是DAWG，其中包含所有可能的錯誤。

很久以前，我聽說拼寫檢查器包含可能出現錯誤的單詞列表（而不是嘗試與有效單詞列表進行匹配），但我不知道這是多麼真實。

我曾經在一個單詞列表中找到一個單詞（帶有錯誤），但它並不侷限於一個單一的錯誤，也沒有大量的內存可用。所以這些單詞只是作爲一個列表存儲（一個DAWG需要節點和指針，這將需要太多的開銷）。

Answer 2

我建議將文件中的名稱存儲到trie或DAWG（更好的空間效率）中。 到達名稱後，開始遍歷數據結構。你將有4個變種：

1. 發現名稱 - >名稱是有效的數據結構
2. 死衚衕 - >檢查留在名稱中的字符數，如果沒有超過1 - >名稱有效;否則無效。
3. 名稱已結束且尚未到達結構中的葉子 - >檢查是否至少有一個葉子附加到當前位置（將採用O（字母大小）） - >如果是，名稱已驗證;否則無效。
4. 在詞語中間遇到的差異 - >繼續從下一個字符開始遍歷 - >不允許更多錯誤（從這一點開始，第2段& 3無效）。

Answer 3

對於第一個問題（確切搜索），您可以使用散列表或trie。布盧姆過濾器可能會在早些時候告訴您「否」，並且空間開銷很大，但永遠不會告訴您一個確定的「是」。

對於第二個問題（模糊搜索），需要更先進的技術。查看博客http://blog.srch2.com/2012/03/fuzzy-search.html，討論解決這個問題的不同方法。