Python的实施Patricia尝试

Question

四处寻找python的尝试实现，以便我能够理解它们是什么以及它们的工作方式，我遇到了贾斯汀·皮尔（Justin Peel） 帕特里夏·特里（Patricia Trie） 并发现它非常有启发性：它足够简单，对于像我一样新的人来说，它可以与之一起学习并从中学习。

但是我认为我不了解：

因此，使用贾斯汀的班级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