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

Question

我正在使用Python实现Trie。目前我已经学习了两种不同的实现方法：

1）使用类节点（类似于C ++中的结构体节点），其中包含以下数据成员：

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

child - 节点类型字典（用于存储其他节点，即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操作？

- divyum

---

https://github.com/kmike/marisa-trie - Padraic Cunningham

你打算如何引用 self.child 中的 Node 对象，考虑到它是一个字典？如果你确实将其保留为 dict，并以某种方式引用 Node 对象，我认为这两种方法的时间复杂度相同，但第一种方法的空间复杂度更高。如果你将 self.child 引用为列表，则第一种方法可能会慢一些。 - hyades

@divyum，如果您没有具体说明您想要做什么，那么您只能期望基于个人喜好的意见。该问题中的答案讨论了优缺点并提供了示例。 - Padraic Cunningham

@divyum 是的，第一种方法允许您使用更结构化的形式，从而解决了繁琐的部分，但同时占用了更多的空间。如果您正在谈论大型数据集，则需要担心的是时间复杂度。无论使用哪种字典树，您都需要将遍历的时间复杂度设置为O(len(search_str))。上述两种方法都会产生完全相同的结果。 - hyades

如果你使用dict来实现trie树，那么你几乎是在作弊。 - Dima Tisnek

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

- Josep Valls

---

是的，我提到了大数据集。显然这取决于需求，但我的原因是为了使其结构化，并具有一些其他功能，如计数前缀、建议单词等等...通过第一次实现，我们可以添加更多功能，但在第二次实现中，我们将被限制在特定的功能上。 我想让它更具可扩展性和实时性。 - divyum

Answer 2

一个直接的替代方案是嵌套一个list；

然而，更符合Python风格、在内存上更紧凑、因此查找速度更快的是嵌套的tuple。

当然，更新这样的trie变成了logN，因为你需要重新创建每个祖先节点。但如果你的查找比更新频繁得多，那么它可能是值得的。

- Dima Tisnek

Answer 3

当涉及到空间复杂度时，Trie结构会出现失败。Trie倾向于使用大量的内存进行处理和操作。但为了避免这个问题，有一种称为紧凑数据结构的数据结构可以使用。尝试在这里实现它。

请参考这里获取更多信息。

- Ashik Vetrivelu