我的做法

1）我打算建立一個樹，以便進行搜索，就會有效。

2）我沒有得到如何實現自動校正功能。

3）我可以用樹木

My tree Image

什麼是最好的數據結構和算法，實現了上述所有功能，實現自動完成功能？

2013-12-11 Ankith

看起來像一個trie http://en.wikipedia.org/wiki/Trie –

這是上述問題的完整解決方案https://github.com/msankith/Trie/tree/1。1 – Ankith

雖然它的工作效率很高，但我發現這是一個相當低效的解決方案。嘗試不是有效的內存。此外，這隻能糾正拼寫錯誤的拼寫字母。 – Pawan

您可以通過查看給定子樹中的所有字符串來進行自動完成。有些分數可以幫助你選擇。如果你在樹中沿着這條路走下去，並遍歷整個子樹來獲得所有可能的結果，這就好像是一樣。

對於更正，您需要在樹上實現類似http://en.wikipedia.org/wiki/Levenshtein_distance的內容。您可以使用這樣一個事實，即如果您在trie中處理了給定路徑，則可以重用根路徑末尾處的子樹中的所有字符串的結果。

2013-12-11 08:09:53 Sorin

如何使用「Levenshtein距離」來實現自動校正？根據我的理解 - Levenshtein距離用於比較給定的字符串與字符串列表（字典）。但是如果我繼續比較字典中的每個字符串，它會花費很多時間。有沒有更好的運行算法存在相同的。 – Ankith

@Ankith：BK樹是一種利用Levenshtein距離是度量空間的事實的算法，用於優化在一組字符串（字典）中搜索一個字符串（查詢）的最近鄰居。 –

1）除了樹木，另一個有趣的方法是BWT
http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform
BWT後綴數組可以很容易地用於跟蹤與給定前綴字。

2013-12-11 21:32:39 Shelwien

我一直在努力的同樣的問題。到目前爲止，我遇到的最好的解決方案是使用三元搜索樹來自動完成。三元搜索樹比嘗試更節省空間。如果我無法在三元搜索樹中查找查找的字符串，那麼我使用已經構建的BK樹來查找最接近的匹配。 BK樹內部使用Levenshtein距離。你

metaphones也是你可能想探索的東西，但我沒有深入metaphones。

如果你喜歡，我有一個用於BK TREE +三級搜索樹的Java解決方案。

2013-12-26 14:22:36 Pawan

您可能也有興趣 - http://www.dhruvbird.com/autocomplete.pdf – Pawan

你有沒有實現自動更正或建議錯誤鍵入的單詞。我已經實施使用蠻力。需要更好的算法 – Ankith

就像我說的，使用BK樹進行自動更正。它在內部使用Levenshtein距離。例如，如果允許它在最多2個字符處糾正，Cabllge會被糾正爲捲心菜。它還會根據您允許的最大Levenshtein距離提出其他可能的建議。這是一個比蠻力更快的實施。 – Pawan

自動校正算法