patricia tries的python实现

Question

为了了解python实现的尝试，我找到了justinpeel的patricia trie，我发现它非常有启发性：对于我这样一个新的人来说，它足够简单，可以玩玩它并从中学习。在

不过，有件事我想我不明白：

使用Justin的类patricia（），因此：

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

我得到了一本字典，看起来像这样：

^{pr2}$

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

实际上应该是：

^{pr2}$