用于Trie实现的内存高效数据结构

Question

我正在用Python实现一个Trie。到目前为止，我遇到了两种不同的方法来实现它：

char-存储字符
is_end-存储单词结尾（true或false）
prefix_count-存储具有当前前缀的单词数

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

我们派生出这本词典：

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

哪一种是高效的、标准的数据结构，既能有效地存储内存，又能快速地进行字的大数据集上的遍历和其他trie操作？

Answer 1

为什么两者都不是呢？就在昨天，我实现了一个类似的数据结构来存储和检索对象的层次结构，并考虑了这种确切的情况。最终使用带有子字典的节点对象。作为对象的主节点允许您使用自定义方法来打印它或获取内容，如果需要，您甚至可以进行惰性初始化（您提到了大数据集，对吗？）

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)]
        ...