帕特里夏尝试的python实现

寻找python实现的尝试，以便我能理解它们是什么以及它们是如何工作的，我遇到了Justin Peel的patricia trie，并发现它非常具有启发性：对于像我这样新的我会玩弄它并从中吸取教训。帕特里夏尝试的python实现

但是有件事情我觉得我不理解：使用贾斯汀的类帕特里夏（

）这样的：

>>> 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

东西我不理解？

来源

2010-06-25 jjon

我相信错误是在代码的下面的代码片段你看：

 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-26 02:39:38

你说得对，亚历克斯。这看起来正是这个错误。我曾警告说它没有很好地测试。这只是我抓了起来，从那以后就没有真正使用过。我在我原来发布的答案中修复了代码。 – 2010-06-26 04:36:10

@Justin，太棒了，谢谢你的确认！ – 2010-06-26 04:52:26

亚历克斯，非常感谢您的发现，现在看起来像预期的那样工作。并感谢贾斯汀建立这个。以字典的形式访问根目录后，我发现非常具有启发性：我认为在轮廓，缩进文本（这是人文科学训练的结果，而不是Python的经验;但是，这正是我首先吸引到python的原因），所以能够相互打印这个句子确实有助于说明发生了什么。我希望你会发布你在这方面做的任何进一步的工作：基准测试或其他。我也很想听听关于Patricia尝试潜在用途的任何想法。 – jjon 2010-06-26 16:15:46

帕特里夏尝试的python实现

回答

相关问题