python - 内存高效的数据结构，可实现Trie

我正在用Python实现Trie。到目前为止，我已经遇到了两种不同的方法来实现它:
1)使用具有数据成员的类Node(类似于C++中的struct Node):char-存储字符is_end-存储单词结尾(对或错)prefix_count-存储具有当前前缀的单词数child-节点类型dict(用于存储其他节点，例如26个字母)

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

2)使用字典来存储所有数据:
例如用于输入words = {'foo', 'bar', 'baz', 'barz'}我们得到这个字典:

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

哪个是有效且标准的数据结构，哪个存储效率高，并且在大型单词数据集上进行遍历和其他trie操作时速度快？

最佳答案

为什么不兼得？就在昨天，我正在实现用于存储和检索对象层次结构的类似数据结构，并考虑了这种确切情况。最终使用带有子字典的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)]
        ...