什麼數據結構或算法用於自動完成？

當我們鍵入命令或名稱的一半，然後按Tab鍵，它立即找到剩餘部分。什麼數據結構/算法用於實現這種效率？什麼數據結構或算法用於自動完成？

2014-04-18 user2704831

此問題與此http://stackoverflow.com/questions/5570795/how-does-bash-tab-completion-work有關。我建議你看一下readline庫的源代碼以獲得肯定的答案。你可以在這裏找到這個庫http://cnswww.cns.cwru.edu/php/chet/readline/rltop.html – lego

@lego我不同意。這個問題專門針對解決問題的算法，鏈接問題和文檔都沒有談到這個問題 –

您可以將您的一組字符串存儲在Directed Acyclic Graph中。

圖的每個節點對應於可能的前綴，並且鏈接到所述前綴的可能的單字母擴展名。圖的根部帶有空白前綴。葉子是可能的完整條目。

在Python中有一個叫做DAWG的模塊來處理這些。

來源

2014-04-18 14:11:22

這更常被稱爲[trie]（http://en.wikipedia.org/wiki/Trie）。儘管我認爲將它描述爲一棵**樹，而不是一個DAG，它更簡單。 – Dukeling

@Dukeling號DAWG（或更確切地說，[確定性非循環有限狀態自動機]（https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_state_automaton））*不是樹，它共享後綴，所以它實際上是一個正確的DAG，如果這是最小的這種自動機準確接受字典字符串，它顯然節省了同一字典上的壓縮字體樹的空間，如果至少有兩個字共用一個後綴 –

A trie是一個很好的數據結構來解決這個問題。

這是一棵樹，其中每個邊代表下一個可能的字符，該字符將附加到由當前根路徑定義的字符串。

所以，如果你要輸入in，你會沿着root -i-> i -n-> in旅遊，探索子樹找到inn。

您可以在每個節點上包含一個標誌，以指示它是否包含有效的單詞（對於非葉子，因爲葉子只有在包含有效單詞時纔會創建）。

可以使用的更常見（但不太專業化）的數據結構是binary search tree (BST)。

二叉查找樹（BST）...是基於節點的二進制樹的數據結構，其中每個節點具有可比密鑰（和相關聯的值），且滿足限制，在任何節點的關鍵字大而不是該節點左子樹中所有節點中的密鑰，並且小於該節點右子樹中所有節點中的密鑰。

根據BST實施，就應該把能夠：

調用一個range函數來獲得兩個值之間的所有元素，特別是字符串之間的「增量'。例如，如果給出abc，那麼'遞增'字符串將是abd。如果給出abz，'遞增'字符串將是aca（假設我們在BST中只允許a-z，否則您可以在z字符集之後挑選字符，例如ASCII碼爲{）。
調用ceiling-類型函數以獲取大於或等於給定字符串的最小元素，然後重複獲取有序的後繼，直到gotten元素不再以給定字符串開始。

來源

2014-04-18 17:06:01 Dukeling

什麼數據結構或算法用於自動完成？

回答

相關問題