aplicación de pitón de intentos patricia
-
30-09-2019 - |
Pregunta
Mirando a su alrededor para las implementaciones de pitón de intentos sólo para que yo puedo entender lo que son y cómo funcionan, me encontré con Patricia trie y nos pareció muy instructiva: es lo suficientemente sencillo para uno tan nuevo como estoy para jugar un rato con él y aprender de ella .
Sin embargo hay algo que creo que no soy la comprensión:
Patricia usando la clase de Justin () así:
>>> p = patricia()
>>> words = ['foo','bar','baz']
>>> for x in words:
... p.addWord(x)
consigo un trie como un diccionario con este aspecto:
>>> p._d
{'b': ['a', {'r': ['', {}], 'z': ['', {}]}], 'f': ['oo', {}]}
addWord () y isWord () funciona como se esperaba, pero isPrefix () muestra el siguiente comportamiento que me intriga:
>>> p.isPrefix('b')
True
>>> p.isPrefix('f')
True
>>> p.isPrefix('e')
False
bueno, como era de esperar; y después
>>> p.isPrefix('ba')
True
también es bueno, pero a continuación:
>>> p.isPrefix('bal')
True
y además:
>>> p.isPrefix('ballance')
True
>>> p.isPrefix('ballancing act')
True
Algo aquí no voy a entender?
Solución
Creo que el error está en el siguiente fragmento de código que está buscando en:
if w.startswith(node[0][:wlen-i],i):
if wlen - i > len(node[0]):
i += len(node[0])
d = node[1]
return True
lo que realmente debe ser:
if w.startswith(node[0][:wlen-i],i):
if wlen - i > len(node[0]):
i += len(node[0])
d = node[1]
else:
return True