如何在python中實現trie的remove函數？

我讀過下面執行線索的蟒蛇： https://stackoverflow.com/a/11016430/2225221 如何在python中實現trie的remove函數？

，並試圖使刪除fnction它。基本上，即使在開始時我也遇到了問題：如果你想從一個trie中刪除一個單詞，它可以包含子字詞，或者它可以是另一個單詞的「子字詞」。

如果您使用「del dict [key]」刪除，您也正在刪除上述兩種字詞。任何人都可以在這幫助我，如何正確刪除所選單詞（讓我們假設它是在trie中）

2013-03-29 John Berry

基本上，要從trie中刪除單詞（因爲它在您鏈接的答案中實現），你只需要刪除其_end標記，例如像這樣：

def remove_word(trie, word): 
    current_dict = trie 
    for letter in word: 
     current_dict = current_dict.get(letter, None) 
     if current_dict is None: 
      # the trie doesn't contain this word. 
      break 
    else: 
     del current_dict[_end]

不過請注意，這並不保證該線索有其最小尺寸。刪除單詞後，可能會有樹狀結構中的分支不再被任何單詞使用。這不會影響數據結構的正確性，它只是意味着trie可能會消耗比絕對必要的更多的內存。您可以通過從葉節點向後迭代並刪除分支，直到找到一個具有多個子節點的分支來改善此問題。

編輯：下面是一個想法，你可以實現一個刪除功能，也可以剔除任何不必要的分支。有可能是一個更有效的方式來做到這一點，但是這可能讓你開始：

def remove_word2(trie, word): 
    current_dict = trie 
    path = [current_dict] 
    for letter in word: 
     current_dict = current_dict.get(letter, None) 
     path.append(current_dict) 
     if current_dict is None: 
      # the trie doesn't contain this word. 
      break 
    else: 
     if not path[-1].get(_end, None): 
      # the trie doesn't contain this word (but a prefix of it). 
      return 
     deleted_branches = [] 
     for current_dict, letter in zip(reversed(path[:-1]), reversed(word)): 
      if len(current_dict[letter]) <= 1: 
       deleted_branches.append((current_dict, letter)) 
      else: 
       break 
     if len(deleted_branches) > 0: 
      del deleted_branches[-1][0][deleted_branches[-1][1]] 
     del path[-1][_end]

從本質上講，它首先發現於即將被刪除，然後通過迭代往回走，找到單詞「路徑」可以刪除的節點。然後它刪除可以刪除的路徑的根目錄（這也隱含地刪除了_end節點）。

來源

2013-03-29 18:51:22 omz

謝謝，真是個好主意！我現在只有向後迭代的問題。既然你可以去任何字典，要得到的關鍵/價值，但你不能（據我所知）得到「父母」的字典。但是，如果你想重新添加相同的單詞，你只是「重新 - 添加「_end標誌，謝謝！ :) –

是的，這是有點棘手，沒有直接訪問「父」字典，請參閱我的編輯瞭解如何在不改變整體數據結構的情況下做到這一點。 – omz

再次編輯，使其更有效率。基本上，沒有必要單獨刪除所有已刪除的字典，只要刪除找到的路徑的「根」就足夠了（所有其他的都是子節點）。 – omz

處理這種結構的一種方法是通過recursion。在這種情況下遞歸的好處在於，它拉到了trie的底部，然後將返回的值通過分支返回。

以下功能就是這樣做的。它會跳到葉子上並刪除_end值，以防萬一輸入詞是另一個詞的前綴。然後它傳遞一個布爾值（boo），表明current_dict仍處於偏離分支。一旦我們達到當前字典中有多個孩子的地方，我們刪除相應的分支並將其設置爲False，這樣每個剩餘的遞歸都不會執行任何操作。

def trie_trim(term, trie=SYNONYMS, prev=0): 
    # checks that we haven't hit the end of the word 
    if term: 
     first, rest = term[0], term[1:] 
     current_length = len(trie) 
     next_length, boo = trie_trim(rest, trie=trie[first], prev=current_length) 

     # this statement avoids trimming excessively if the input is a prefix because 
     # if the word is a prefix, the first returned value will be greater than 1 
     if boo and next_length > 1: 
      boo = False 

     # this statement checks for the first occurrence of the current dict having more than one child 
     # or it checks that we've hit the bottom without trimming anything 
     elif boo and (current_length > 1 or not prev): 
      del trie[first] 
      boo = False 

     return current_length, boo 

    # when we do hit the end of the word, delete _end 
    else: 
     del trie[_end] 
     return len(trie) + 1, True

來源

2017-03-21 21:06:01

如何在python中實現trie的remove函數？

回答

相關問題