首页 文章

内存Trie Implementation的高效数据结构

提问于
浏览 次
7

我在python中实现了一个Trie . 直到现在我遇到了两种不同的方法来实现它：

  • 使用数据成员的类Node（类似于C中的struct Node） -

char - 存储字符is_end - 存储单词结尾（true或false）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 = {}
  • 使用字典存储所有数据 .

words = {'foo'，'bar'，'baz'，'barz'} {'b'：{'a'：{'r'：{'_ end_'：'_ end ^'，'z'：{' end'：'_ end_'}}，
'z'：{'_ end_'：'_ end_'}}}，
'f'：{'o'：{'o'：{'_ end_'：'_ end}'}}}}

哪个是高效且标准的数据结构，对于大数据集单词的遍历和其他trie操作，它既高效又快速？

python data-structures tree nlp trie

3 回答

  • -3

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

    直接替换将嵌套 list ;

    然而[可以说]更多的Pythonic，更紧凑的内存，因此更快的查找将是嵌套的 tuple .

    当然，更新这样的trie会变成logN，因为你必须重新创建每个祖先节点 . 尽管如此，如果您的查找比更新频繁得多，那么它可能是值得的 .

    回复于
  • 1

    在空间复杂性方面，Trie失败了 . Trie倾向于使用大量内存进行处理和操作 . 但是为了避免这个问题，有一种数据结构被称为简洁的数据结构 . 试着在这里实现 .

    有关更多信息，请参阅here .

    回复于

相关问题