Как реализовать функцию удаления trie в python?

Question

Я прочитал следующую реализацию в питона синтаксического дерева: https://stackoverflow.com/a/11016430/2225221

и попытался сделать удалить fnction для него. В принципе, у меня были проблемы даже с самого начала: если вы хотите удалить слово из trie, оно может содержать подсловы, или это может быть «подсловом» другого слова.

Если вы удалите «del dict [key]», вы также удалите эти вышеупомянутые два типа слов. Может ли кто-нибудь помочь мне в этом, как правильно удалить выбранное слово (предположим, что оно находится в trie)

Answer 1

В принципе, чтобы удалить слово из 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 имеет минимальный размер. После удаления слова в левой части могут быть ветви, которые больше не используются никакими словами. Это не влияет на правильность структуры данных, это просто означает, что trie может потреблять больше памяти, чем это абсолютно необходимо. Вы можете улучшить это, итерации назад от листового узла и удаления ветвей, пока не найдете тот, у которого есть более одного ребенка.

EDIT: Представьте себе, как можно реализовать функцию удаления, которая также отбирает ненужные ветви. Там, наверное, более эффективный способ сделать это, но это может вам начать:

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

Answer 2

Один способ обработки таких конструкций, как это, составляет recursion. Самое замечательное в рекурсии в этом случае заключается в том, что оно застегивается на нижнюю часть trie, затем передает возвращаемые значения обратно через ветви.

Следующая функция делает именно это. Он переходит к листу и удаляет значение _end, на всякий случай, если входное слово является префиксом другого. Затем он переходит в булевское (boo), что указывает на то, что current_dict все еще находится в отдаленной ветке. Как только мы нажмем точку, где текущий dict имеет более одного ребенка, мы удалим соответствующую ветку и установите boo на 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