la mise en œuvre de python d'essais patricia
-
30-09-2019 - |
Question
En regardant autour pour les implémentations de python d'essais juste pour que je puisse comprendre ce qu'ils sont et comment ils fonctionnent, je suis tombé sur Justin Peel patricia et Trie trouvé très instructif: il est assez simple pour un aussi nouveau que je dois jouer avec elle et en tirer des leçons .
Cependant, il y a quelque chose que je pense que je ne comprends pas:
à l'aide de patricia () de la classe de Justin ainsi:
>>> p = patricia()
>>> words = ['foo','bar','baz']
>>> for x in words:
... p.addWord(x)
Je reçois Trie comme un dictionnaire qui ressemble à ceci:
>>> p._d
{'b': ['a', {'r': ['', {}], 'z': ['', {}]}], 'f': ['oo', {}]}
addword () et isWord () le travail comme prévu, mais isPrefix () montre le comportement suivant qui me déconcerte:
>>> p.isPrefix('b')
True
>>> p.isPrefix('f')
True
>>> p.isPrefix('e')
False
bon, comme prévu; puis
>>> p.isPrefix('ba')
True
aussi bon, mais:
>>> p.isPrefix('bal')
True
et en outre:
>>> p.isPrefix('ballance')
True
>>> p.isPrefix('ballancing act')
True
Quelque chose ici je ne comprends pas?
La solution
Je crois que le bogue est dans l'extrait suivant du code que vous cherchez à:
if w.startswith(node[0][:wlen-i],i):
if wlen - i > len(node[0]):
i += len(node[0])
d = node[1]
return True
il devrait en fait être:
if w.startswith(node[0][:wlen-i],i):
if wlen - i > len(node[0]):
i += len(node[0])
d = node[1]
else:
return True