Python实现的Patricia Trie

Question

我在寻找Python实现的字典树（trie），想搞明白它是什么以及怎么工作的过程中，发现了Justin Peel的patricia trie，觉得这个例子很有帮助：对于像我这样刚入门的人来说，它简单易懂，可以让我动手试试并学习。

不过，有些地方我觉得我没搞明白：

使用Justin的patricia()类，像这样：

>>> p = patricia()
>>> words = ['foo','bar','baz']
>>> for x in words:
...     p.addWord(x)

我得到了一个看起来像字典的字典树：

>>> p._d
{'b': ['a', {'r': ['', {}], 'z': ['', {}]}], 'f': ['oo', {}]}

addWord()和isWord()的功能都正常，但isPrefix()的表现让我有点困惑：

>>> p.isPrefix('b')
True
>>> p.isPrefix('f')
True
>>> p.isPrefix('e')
False

这个结果很好，符合预期；然后

>>> p.isPrefix('ba')
True

这个结果也不错，但接下来：

>>> p.isPrefix('bal')
True

而且：

>>> p.isPrefix('ballance')
True
>>> p.isPrefix('ballancing act')
True

这里面有什么我没理解的吗？

Answer 1

我觉得你正在查看的代码片段里有个错误：

       if w.startswith(node[0][:wlen-i],i):
            if wlen - i > len(node[0]):
                i += len(node[0])
                d = node[1]
            return True

其实应该是：

       if w.startswith(node[0][:wlen-i],i):
            if wlen - i > len(node[0]):
                i += len(node[0])
                d = node[1]
            else:
                return True