реализация Python Патриция пытается - PullRequest
Новая
       18

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

3 голосов
/ 26 июня 2010

Оглядываясь на реализации Python для попыток, просто чтобы я мог понять, что они из себя представляют и как они работают, я наткнулся на 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

Что-то здесь я не понимаю?

1 Ответ

3 голосов
/ 26 июня 2010

Я считаю, что ошибка в следующем фрагменте кода, который вы просматриваете: 

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