5

それらが何であり、どのように機能するかを理解できるように、トライの Python 実装を探し回っていると、ジャスティン・ピールのパトリシア・トライに出くわし、非常に有益であることがわかりました。そこから学ぶ。

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

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

ここで何か理解できませんか？

4

1 に答える 1

4

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

       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
于 2010-06-26T02:39:38.003 に答える