什麼是最好的自動完成/建議算法，數據結構[C++/C]

我們看到Google，Firefox的一些AJAX頁面顯示可能項目列表，而用戶輸入字符。什麼是最好的自動完成/建議算法，數據結構[C++/C]

有人可以給一個很好的算法，實現自動完成的數據結構？

2009-11-23 subbul

A trie是一種數據結構，可用於快速查找與前綴匹配的單詞。

編輯：下面是示出了如何使用一個實現自動填充http://rmandvikar.blogspot.com/2008/10/trie-examples.html

這裏是3個不同的auto-complete implementations的比較（雖然它是一個Java不C++）的例子。

* In-Memory Trie 
* In-Memory Relational Database 
* Java Set

查找鍵時，trie比Set實現稍快。 trie和set都比關係型數據庫解決方案好一點。

Set的設置成本低於Trie或DB解決方案。您必須決定是否要頻繁構建新的「詞彙集」，或者查詢速度是否優先。

這些結果是用Java編寫的，你的里程可能會因C++解決方案而異。

來源

2009-11-23 15:03:59 Glen

有點關係是谷歌的彼得·諾維格的描述如何進行拼寫校正：http://norvig.com/spell-correct.html – 2009-11-23 15:23:03

標準Trie的內存密集程度很高，對於較大的套件，您希望使用壓縮Trie，這樣可以大大減少內存佔用量。其他優化包括節點值的延遲初始化和子/值集合的正確數據結構。前一段時間，我創建了一個[自動完成庫]（https://github.com/fmmfonseca/completely），能夠處理超大型數據集（10,000,000+），並有效地回答精確和近似的搜索。 – 2015-06-23 14:47:44

對於一個簡單的解決方案：你產生一個「候選」以最小的編輯（Levenshtein）距離（1或2），然後在測試用散列容器候選的存在（設置就足夠了一個簡單的soltion ，然後從tr1或boost使用unordered_set）。

例如：你寫了carr，你想要汽車。 arr是由1個刪除產生的。你的unordered_set是否是arr？號碼crr是由1次刪除產生的。在你的unordered_set中是crr嗎？號車是由1刪除產生的。你的車是在無序的？是的，你贏了。

當然還有插入，刪除，換位等等

您將看到，產生候選人的算法是真的，你是在浪費時間，特別是如果你有一個非常小unordered_set。

來源

2009-11-23 16:49:08 anno

對於大型數據集，後端的一個很好的候選者是三元搜索樹。它們結合了兩個最好的世界：二叉搜索樹的低空間開銷和數字搜索嘗試的基於字符的時間效率。

見Dr. Dobbs Journal的：http://www.ddj.com/windows/184410528

的目標是有限的結果集，作爲在用戶類型的快速檢索讓我們首先考慮的是要搜索「計算機科學」就可以啓動從「計算機」打字。或「科學」而不是「計算機」。因此，給定一個短語，生成以單詞開始的子短語。現在對於每個短語，將它們送入TST（三元搜索樹）。 TST中的每個節點將代表到目前爲止輸入的短語的前綴。我們將在該節點中存儲該前綴的最佳10個（說）結果。如果對於一個節點，有更多的候選人比有限的結果數量（10個），應該有一個排名函數來解決兩個結果之間的競爭。

根據數據的動態性，樹可以每隔幾個小時建立一次。如果數據是實時的，那麼我想其他一些算法會給出更好的平衡。在這種情況下，絕對要求是快速檢索鍵入的每個擊鍵的結果，它的表現非常好。

如果涉及到拼寫糾正的建議，會出現更多複雜問題。在這種情況下，編輯距離算法也必須考慮。

對於像國家列表這樣的小數據集，Trie的一個簡單實現就可以做到。如果您要在Web應用程序中實現此類自動完成下拉列表，則在您提供列表中的數據後，YUI3的自動完成小部件將爲您執行所有操作。如果您使用YUI3作爲大數據支持的自動填充的前端，請使用C++製作基於TST的Web服務，然後使用自動填充小部件的腳本節點數據源從Web服務獲取數據，而不是使用簡單列表。

來源

2009-11-23 19:17:01

如果你想建議最流行的完成，一個「推薦樹」可能是一個不錯的選擇： Suggest Tree

來源

2010-10-28 09:25:26 Nicolai