Внедряване на структурата на данни Trie

Въведение

Думата trie е инфликс на думата „re trie val“, тъй като trie може да намери една дума в речник само с префикс на думата.

Trie е ефективна структура от данни за извличане на данни. Използвайки trie, сложността на търсенето може да бъде доведена до оптимална граница, т.е. дължина на низа.

Това е многопосочна дървовидна структура, полезна за съхраняване на низове над азбука, когато ги съхраняваме. Използвано е за съхраняване на големи речници на английски, да речем, думи в програми за проверка на правописа. Наказанието за опити обаче е изискванията за съхранение.

Какво е трие?

Trie е дървовидна структура на данни, която съхранява низове и ви помага да намерите данните, свързани с този низ, използвайки префикса на низа.

Например, да речем, че планирате да изградите речник, който да съхранява низове заедно с техните значения. Сигурно се чудите защо не мога просто да използвам хеш таблица, за да получа информация.

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

Трие обикновено изглежда нещо подобно,

Трие

Това е изображение на трие, което съхранява думите {assoc, algo, all, also, tree, trie}.

Как да приложим трие

Нека приложим трие в python, за съхраняване на думи с техните значения от английски речник.

ALPHABET_SIZE = 26 # For English class TrieNode: def __init__(self): self.edges = [None]*(ALPHABET_SIZE) # Each index respective to each character. self.meaning = None # Meaning of the word. self.ends_here = False # Tells us if the word ends here.

Както можете да видите, ръбовете са с дължина 26, като всеки индекс се отнася до всеки знак в азбуката. „A“ съответства на 0, „B“ на 1, „C“ на 2… „Z“ на 25-ия индекс. Ако символът, който търсите, сочи None, това означава, че думата не е там в трие.

Типичният трие трябва да реализира поне тези две функции:

  • add_word(word,meaning)
  • search_word(word)
  • delete_word(word)

Освен това може да се добави и нещо подобно

  • get_all_words()
  • get_all_words_with_prefix(prefix)

Добавяне на Word към трие

 def add_word(self,word,meaning): if len(word)==0: self.ends_here = True # Because we have reached the end of the word self.meaning = meaning # Adding the meaning to that node return ch = word[0] # First character # ASCII value of the first character (minus) the ASCII value of 'a'-> the first character of our ALPHABET gives us the index of the edge we have to look up. index = ord(ch) - ord('a') if self.edges[index] == None: # This implies that there's no prefix with this character yet. new_node = TrieNode() self.edges[index] = new_node self.edges[index].add(word[1:],meaning) #Adding the remaining word

Извличане на данни

 def search_word(self,word): if len(word)==0: if self.ends_here: return True else: return "Word doesn't exist in the Trie" ch = word[0] index = ord(ch)-ord('a') if self.edge[index]== None: return False else: return self.edge[index].search_word(word[1:])

Най search_wordфункция ще ни каже дали думата съществува в TRIE или не. Тъй като нашият е речник, трябва да извлечем и смисъла, сега нека декларираме функция, която да го направи.

 def get_meaning(self,word): if len(word)==0 : if self.ends_here: return self.meaning else: return "Word doesn't exist in the Trie" ch = word[0] index = ord(ch) - ord('a') if self.edges[index] == None: return "Word doesn't exist in the Trie" else: return self.edges[index].get_meaning(word[1:])

Изтриване на данни

Като изтривате данни, просто трябва да промените променливата ends_hereна False. Това не променя префиксите, но все пак изтрива значението и съществуването на думата от трие.

 def delete_word(self,word): if len(word)==0: if self.ends_here: self.ends_here = False self.meaning = None return "Deleted" else: return "Word doesn't exist in the Trie" ch = word[0] index = ord(ch) - ord('a') if self.edges[index] == None: return "Word doesn't exist in the Trie" else: return self.edges[index].delete_word(word[1:])
: ракета:

Изпълнете код