[SOLVED] python implementation of patricia tries

python implementation of patricia tries

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:

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

good, as expected; and then

>>> p.isPrefix('ba')
True

also good, but then:

>>> p.isPrefix('bal')
True

and furthermore:

>>> p.isPrefix('ballance')
True
>>> p.isPrefix('ballancing act')
True

Something here I'm not understanding?

Solution

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

it should actually be:

       if w.startswith(node[0][:wlen-i],i):
            if wlen - i > len(node[0]):
                i += len(node[0])
                d = node[1]
            else:
                return True