la mise en œuvre de python d'essais patricia

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?

Answer 1

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