Python中的Trie（前綴樹）

Question

我不知道這是不是問問算法的地方。但讓我們看看，如果我得到任何答案... :)

如果有什麼不清楚我很高興澄清事情。

我剛剛在python中實現了一個Trie。然而，有一點似乎比它應該更復雜（就像一個熱愛簡單的人）。也許有人有類似的問題？

我的目標是通過在其根中存儲子樹的最大公共前綴來最小化節點數。例如，如果我們有話計算器，stackbase和stackbased，則樹會是這個樣子：

   [s]tack 
[o]verflow ______/ \_______ [b]ase 
            \___ [d] 

注意，仍然可以認爲有一個字符邊緣（在第一個孩子節點）。

查找 - 查詢很容易實現。 插入並不難，但有些較複雜的比我想.. :(

我的想法是插入後，其他的按鍵一個（從空開始特里），通過爲將要優先搜索（k）（查找（k）），然後在查找過程停止的地方對節點進行本地重新排列/分割，結果爲4種情況：設k是我們想要插入的密鑰和k '是節點，在此處搜索結束）的關鍵

1. k是相同的k'
2. k是一個「適當的」前綴k'
3. k'是k的「適當」前綴k和k'共享一些共同的前綴，但情況（1），（2）或3）發生。

似乎每個案例都是獨一無二的，因此意味着Trie的不同修改。但是：這真的很複雜嗎？我錯過了什麼嗎？有更好的方法嗎？

謝謝:)

Answer 1

一眼就可以看出您已經實施了Patricia Trie。這種方法在一些文獻中也被稱爲路徑壓縮。應該有不屬於ACM付費牆的文件副本，其中包含插入算法。

還有另一種壓縮方法，你可能想看看：級別壓縮。路徑壓縮背後的想法是用具有「跳過」計數的單個超級節點替換單個子節點的字符串。級別壓縮背後的想法是用超級節點替換完整或接近完整的子樹，其中「度」數表示節點解碼密鑰的數目。還有一種稱爲寬度壓縮的第三種方法，但是我擔心我的記憶會使我失敗，而且我無法用Google進行快速搜索。

級別壓縮可以顯着縮短平均路徑，但插入和移除算法變得非常複雜，因爲它們需要像動態數組一樣管理trie節點。對於正確的數據集，級別壓縮樹可以是快速。從我記憶中來看，它們是存儲IP路由表的第二快速方法，最快的是某種散列函數。

Answer 2

我沒有看到你的方法有什麼問題。如果您正在尋找一個高峯解決方案，可能在前三種情況下案例4採取的措施實際上是可行的，IE會找到k和k'的常見前綴，然後重新構建節點。如果碰巧密鑰是相互關聯的前綴，那麼結果中的trie仍然是正確的，只有實現做了比實際更多的工作。但是再一次，沒有任何代碼看它很難說這是否適用於你的情況。

Answer 3

有點切線，但如果你超級擔心你的Trie中的節點數量，你可能會考慮加入你的單詞後綴。我會看看DAWG（定向非循環詞圖）的想法：http://en.wikipedia.org/wiki/Directed_acyclic_word_graph

這些缺點是它們不是很動態，創建它們可能很困難。但是，如果你的字典是靜態的，它們可以超級緊湊。

Answer 4

我對您的實施有疑問。您決定將字符串拆分爲前綴樹的粒度級別是多少？您可以將堆棧分割爲s，t，a，c，k或st，ta，ac，ck和其他許多ngrams。大多數前綴樹實現都考慮到該語言的字母表，基於這個字母表，您可以進行拆分。

如果你正在構建一個前綴樹實施蟒那麼你的字母會之類的東西閃避，：如果，否則...等

選擇正確的字母，使構建高效的前綴樹的巨大差異。至於你的答案，你可以在CPAN上查找使用trie的最長公共子字符串計算的PERL包。你可能會有一些運氣，因爲他們的大部分實現都非常強大。

Answer 5

看看：朱迪數組和python界面在http://www.dalkescientific.com/Python/PyJudy.html