帕特里夏尝试的python实现

Question

为了了解它们是什么以及它们是如何工作的，我四处寻找 tries 的 python 实现，我遇到了 Justin Peel 的 patricia trie并发现它非常有启发性:对于像我这样的新手来说，它足够简单明了，可以尝试并从中学习。

但是有些事情我觉得我不明白:

因此使用 Justin 的类 patricia():

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

我得到一个 trie 字典，看起来像这样:

>>> 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