aplicación de pitón de intentos patricia

Question

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?

Answer 1

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