5

四处寻找尝试的 python 实现，以便我能理解它们是什么以及它们是如何工作的，我遇到了 Justin Peel 的patricia trie，发现它非常有启发性：对于像我这样新的人来说，它很简单，可以使用它并且从中学习。

但是，有些事情我认为我不明白：

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

这里有什么我不明白的？

4

1 回答 1

4

我相信该错误位于您正在查看的以下代码片段中：

       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
于 2010-06-26T02:39:38.003 回答