implementazione pitone di trie patricia

Question

Guardando in giro per le implementazioni di pitone di tentativi solo in modo che io possa capire che cosa sono e come funzionano, mi sono imbattuto di Justin Peel trie patricia e l'ho trovato molto istruttivo: è abbastanza semplice per uno come nuova come sono a giocare con essa e imparare da esso .

Tuttavia c'è qualcosa che penso che non sto rendendo conto:

con Patricia classe di Justin () in tal modo:

>>> p = patricia()
>>> words = ['foo','bar','baz']
>>> for x in words:
...     p.addWord(x)

ho un trie come un dizionario simile a questo:

>>> p._d
{'b': ['a', {'r': ['', {}], 'z': ['', {}]}], 'f': ['oo', {}]}

addword () e isWord () funzionano come previsto, ma isPrefix () mostra il seguente comportamento che mi lascia perplesso:

>>> p.isPrefix('b')
True
>>> p.isPrefix('f')
True
>>> p.isPrefix('e')
False

buona, come previsto; e poi

>>> p.isPrefix('ba')
True

anche buono, ma poi:

>>> p.isPrefix('bal')
True

e inoltre:

>>> p.isPrefix('ballance')
True
>>> p.isPrefix('ballancing act')
True

Qualcosa qui non ci sto capendo?

Answer 1

Credo che il bug è nel seguente frammento del codice che stai guardando:

       if w.startswith(node[0][:wlen-i],i):
            if wlen - i > len(node[0]):
                i += len(node[0])
                d = node[1]
            return True

dovrebbe in realtà essere:

       if w.startswith(node[0][:wlen-i],i):
            if wlen - i > len(node[0]):
                i += len(node[0])
                d = node[1]
            else:
                return True