Удаление слова из определенной реализации trie в Python

Question

Я новичок в создании данных, и я реализую trie для устранения неоднозначности базы данных имен с использованием расстояния редактирования. Я использую следующую реализацию:

синтаксического дерева

http://stevehanov.ca/blog/index.php?id=114

, которая в основном:

class TrieNode: 

    def __init__(self): 
     self.word = None 
     self.children = {} 

     global NodeCount 
     NodeCount += 1 

    def insert(self, word): 
     node = self 
     for letter in word: 
      if letter not in node.children: 
       node.children[letter] = TrieNode() 

      node = node.children[letter] 

     node.word = word 

# read dictionary file into a trie 
trie = TrieNode() 
for name in names: 
    WordCount += 1 
    trie.insert(name) 

Это делает работу красиво, как он вставляет все имена в синтаксическое дерево. Теперь я просматриваю список имен, которые есть один за другим, и использую trie для возврата списка всех имен, находящихся на некотором расстоянии редактирования от переданного имени. Затем я хочу удалить все имена из trie, которые были возвращены в списке.

Есть ли быстрый способ сделать это?

Спасибо!

Answer 1

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

def delete(self, word): 
    node = self 
    for letter in word[:-1]: 
     if letter not in node.children: 
      return False 
     node = node.children[letter] 
    if word[-1] in node.children: 
     del node.children[letter] 
     return True 
    return False 

---

Можете ли вы сделать это быстрее? Да, но это не имеет значения.

Во-первых, вы знаете, что узлы всегда существуют, поэтому вы можете удалить некоторые ошибки. Что еще более важно, если вы можете заставить функцию поиска возвращать узлы, а не только их значения, это сделает вещи немного быстрее. Если вы можете добавить обратные ссылки на trie, это означает, что вы можете стереть узел в постоянное время, а не повторять поиск. Если вам не нужны обратные ссылки на trie, вы можете получить то же преимущество, вернув молнию вместо узла, или, проще говоря, просто вернув стек узлов.

Но в самом деле, худший случай здесь - это просто удвоение работы, а не увеличение алгоритмической сложности или умножение на большой коэффициент, поэтому простой, вероятно, побеждает.