题
四处寻找python的尝试实现,以便我能够理解它们是什么以及它们的工作方式,我遇到了贾斯汀·皮尔(Justin Peel) 帕特里夏·特里(Patricia Trie) 并发现它非常有启发性:它足够简单,对于像我一样新的人来说,它可以与之一起学习并从中学习。
但是我认为我不了解:
因此,使用贾斯汀的班级Patricia():
>>> p = patricia()
>>> words = ['foo','bar','baz']
>>> for x in words:
... p.addWord(x)
我得到了像这样的词典的trie:
>>> 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
我在这里不了解吗?
解决方案
我相信该错误是您正在查看的代码的以下片段:
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
不隶属于 StackOverflow