我读过以下实施蟒蛇特里树的:https://stackoverflow.com/a/11016430/2225221
并试图使删除功能吧。基本上,我即使一开始的问题:如果你想从特里删除一个单词,它可以有子“词”,也可以是另一个字的“子词”。
如果用“德尔字典[关键]”删除,要删除上述这些2种词也。谁能帮我在这,如何正确地删除所选单词(我们假设它在特里树)
基本上,从线索中删除的话,你只需要删除其_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]
但是请注意,这并不能保证该线索有其最小尺寸。删除字之后,有可能是在特里左那些不再使用的任何话分支机构。这并不影响数据结构的正确性,它只是意味着该线索可消耗比绝对需要更多的内存。您可以通过从叶节点向后迭代改进这一点,直到你找到一个有不止一个孩子删除分支。
编辑:这里有一个想法,你可以如何实现一个删除功能也剔除任何不必要的分支。有可能是一个更有效的方式来做到这一点,但是这可能让你开始:
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
节点)的路径的根。
我觉得这是更好地做到这一点递归,代码如下:
def remove(self, word):
self.delete(self.tries, word, 0)
def delete(self, dicts, word, i):
if i == len(word):
if 'end' in dicts:
del dicts['end']
if len(dicts) == 0:
return True
else:
return False
else:
return False
else:
if word[i] in dicts and self.delete(dicts[word[i]], word, i + 1):
if len(dicts[word[i]]) == 0:
del dicts[word[i]]
return True
else:
return False
else:
return False
处理结构,这样一种方法是通过recursion。关于在这种情况下,递归伟大的事情是,它呼啸而过到特里树的底部,然后通过返回的值回升穿过树枝。
下面的函数就是这样做的。它去叶并删除_end
值,以防万一输入字是另一个的前缀。然后将其传递了一个布尔型(boo
),这表明该current_dict
仍处于边远分支。一旦我们到了一个地步,目前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
def remove_a_word_util(self, word, idx, node):
if len(word) == idx:
node.is_end_of_word = False
return bool(node.children)
ch = word[idx]
if ch not in node.children:
return True
flag = self.remove_a_word_util(word, idx+1, node.children[ch])
if flag:
return True
node.children.pop(ch)
return bool(node.children) or node.is_end_of_word