帕特里夏嘗試的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實現

回答

相關問題