パトリシアのPython実装は試みます

Question

彼らが何であり、どのように働くかを理解できるように、試行のPythonの実装を探していると、Justin Peel'sに出会いました パトリシア・トリー そして、それは非常に有益であることがわかりました：それは私がそれを遊んでそこから学ぶのと同じくらい新しいものにとって十分に簡単です。

しかし、私が理解していないと思う何かがあります：

JustinのクラスPatricia（）を使用する

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

私はこのように見える辞書としてトライを取得します：

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

addword（）とisword（）は予想どおりに機能しますが、isprefix（）は次の動作を示しています。

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

予想通り、良い。その後

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

また良いが、それから：

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

さらに：

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

ここで私が理解していない何か？

Answer 1

バグは、あなたが見ているコードの次のスニペットにあると思います。

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

それは実際にあるべきです：

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