內存Trie實現的高效數據結構

我正在python中實現Trie。到目前爲止我所遇到兩種不同的方法來實現它：內存Trie實現的高效數據結構

使用類節點（類似於C爲結構節點++）與數據成員 -

焦 - 存儲字符

is_end - 存儲字的結束（true或false）

prefix_count - 詞的門店數量與當前前綴

子 - 節點類型字典使用字典來存儲所有的數據（存儲的其它節點，即對於26個字母表）

class Node(object): 
    def __init__(self): 
     self.char = '' 
     self.word = '' 
     self.is_end = False 
     self.prefix_count = 0 
     self.child = {}

。

words = {'foo', 'bar', 'baz', 'barz'}

 {'b': {'a': {'r': {'_end_': '_end_', 'z': {'_end_': '_end_'}}, 
     'z': {'_end_': '_end_'}}}, 
     'f': {'o': {'o': {'_end_': '_end_'}}}}

哪一個是高效，規範的數據結構，這既是內存高效，快速的對字的大數據集遍歷和其他線索操作？

來源

2015-04-19 divyum

https://github.com/kmike/marisa-trie –

你如何計劃在'self.child'中引用'Node'的對象，考慮到這是一本字典？如果確實將它保留爲'dict'，並以某種方式引用'Node'對象，則我將這兩種方法看作具有相同的時間複雜度，但第一種方法具有更多空間複雜性。如果您將'self.child'作爲列表，那麼第一個可能會慢一點 – hyades

感謝您的回覆。 Node中的每個子節點都有另一個節點類型的對象，這將使它成爲一棵n-ary樹。@hyades – divyum

爲什麼不是兩個？就在昨天，我正在實現一個類似的數據結構來存儲和檢索對象的層次結構，並設想了這種確切的情況。使用帶有子字典的Node對象結束。作爲一個對象的主要節點，可以定製方法打印出來或得到的東西，如果需要的話，你甚至可以有一個延遲初始化（你提到大數據集嗎？）

class Node(object): 
    def __init__(self): 
     self.children = collections.defaultdict(lambda:self.__class__()) 
     self.stuff = ... 
    def __str__(self,depth=0): 
     if self.children: 
      return str(self.stuff)+'\n'+'\n'.join([' '*depth+k+' ' + v.__str__(depth+1) for k,v in self.children.items()]) 
     else: 
      return str(self.stuff) 
    def get_path(self,path): 
     node = self 
     while path: 
      node = node.children[path.pop(0)] 
     ...

來源

2015-04-30 21:07:00

是的，我提到了大數據集。它顯然取決於需求，但我的理由是將它與其他一些功能結合在一起，例如統計前綴，提示單詞等......在第一次執行時，我們可以添加更多功能，但在第二次執行中，我們將被綁定到具體的。我想讓它更具可擴展性和實時性。 – divyum

直接替換將是嵌套0;

然而[可以說]更多的Pythonic，更緊湊的內存，因此更快的查找將是一個嵌套的tuple。

當然，更新這個trie會變成logN，因爲您必須重新創建每個祖先節點。不過，如果你的查詢比更新更頻繁，這可能是值得的。

來源

2015-05-07 14:04:42

-2

Trie在空間複雜性方面失敗了。 Trie傾向於使用大量內存進行處理和操作。但爲了避免這個問題，有一個數據結構被稱爲簡潔的數據結構。嘗試在這裏實現。

有關更多信息，請參閱here。

來源

2016-08-30 18:11:36

內存Trie實現的高效數據結構

回答

相關問題