Python-Implementierung von patricia versucht
-
30-09-2019 - |
Frage
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?
Lösung
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