Python-Implementierung von patricia versucht

Question

Umsah für Python-Implementierungen von Versuchen nur so, dass ich verstehen kann, was sie sind und wie sie funktionieren, stieß ich auf Justin Peels patricia trie und finde es sehr lehrreich: es ist einfach genug für einen so neu, wie ich mit ihm zu spielen, um am und von ihnen lernen .

Allerdings gibt es etwas, was ich glaube, ich bin nicht verstehen:

mit Justins Klasse patricia () also:

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

ich ein Trie als Wörterbuch erhalten wie folgt aussehen:

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

addWord () und isWord () wie erwartet, aber isPrefix () zeigt das folgende Verhalten, das mir ein Rätsel:

>>> p.isPrefix('b')
True
>>> p.isPrefix('f')
True
>>> p.isPrefix('e')
False

gut, wie erwartet; und dann

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

auch gut, aber dann:

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

und darüber hinaus:

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

Etwas hier verstehe ich nicht?

Answer 1

Ich glaube, der Fehler im folgenden Ausschnitt des Codes Sie suchen an:

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

es eigentlich sein sollte:

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