patricia trys的python实现 [英] python implementation of patricia tries

问题描述

到处寻找try的python实现，以便我了解它们是什么以及它们如何工作，我遇到了Justin Peel的

Looking around for python implementations of tries just so that I can understand what they are and how they work, I came across Justin Peel's patricia trie and found it very instructive: it's straightforward enough for one as new as I am to play around with it and learn from it.

但是我觉得有些不明白:

However there's something I think I'm not understanding:

因此使用贾斯汀的class patricia():

using Justin's class patricia() thus:

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

我得到了一个字典里的特里，像这样:

I get a trie as a dictionary looking like this:

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

addWord()和isWord()可以正常工作，但是isPrefix()显示了以下使我感到困惑的行为:

addWord() and isWord() work as expected, but isPrefix() shows the following behavior which puzzles me:

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

这里我不明白吗?

推荐答案

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

I believe the bug is in the following snippet of the code you're looking at:

       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

这篇关于patricia trys的python实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！