Реализация Python Патриция пытается

Question

Оглядываясь на реализации Python для попыток, просто чтобы я мог понять, что они из себя представляют и как они работают, я натолкнулся на пример Патрисии Джастина Пила и нашел его очень поучительным: он достаточно прост для того, чтобы новенький и новичок поиграть с ним и учиться на этом.

Однако есть кое-что, что я не понимаю:

используя класс Джастина 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