Conţinut
Introducere
Cuvântul trie este un inflix al cuvântului „retrieval ”, deoarece trie poate găsi un singur cuvânt într-un dicționar cu doar un prefix al cuvântului.
Trie este o structură eficientă de recuperare a datelor. Folosind trie, complexitatea căutării poate fi adusă la o limită optimă, adică lungimea șirului.
Este o structură de arbore multi-mod utilă pentru stocarea șirurilor peste un alfabet, atunci când le stocăm. A fost folosit pentru a stoca dicționare mari de cuvinte în engleză, să zicem, în programe de verificare ortografică. Cu toate acestea, penalizarea la încercări este cerința de stocare.
Ce este un trie?
Un trie este un arbore ca structura de date care stochează șiruri și vă ajută să găsiți datele asociate acelui șir folosind prefixul șirului.
De exemplu, să presupunem că intenționați să construiți un dicționar pentru a stoca șiruri împreună cu semnificațiile acestora. Trebuie să vă întrebați de ce nu pot folosi pur și simplu un tabel hash, pentru a obține informațiile.
Da, puteți obține informații folosind un tabel hash, dar mese de hash pot găsi doar date în care șirul se potrivește exact cu cel pe care l-am adăugat. Dar trie ne va oferi capacitatea de a găsi șiruri cu prefixe comune, un caracter lipsă etc. într-un timp mai mic, în comparație cu un tabel hash.
Un trie de obicei, arată cam așa,

Aceasta este o imagine a unui Trie, care stochează cuvintele {assoc, algo, all, also, tree, trie}.
Cum se implementează un trie
Să implementăm un trie în python, pentru stocarea cuvintelor cu semnificațiile lor dintr-un dicționar englez.
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.
După cum puteți vedea, marginile au o lungime de 26, fiecare index făcând referire la fiecare caracter din alfabet. „A” corespunde la 0, „B” la 1, „C” la 2… „Z” la cel de-al 25-lea indice. Dacă personajul pe care îl căutați indică None
, asta înseamnă că cuvântul nu este acolo în trie.
Un Trie tipic ar trebui să implementeze cel puțin aceste două funcții:
add_word(word,meaning)
search_word(word)
delete_word(word)
În plus, se poate adăuga și ceva de genul
get_all_words()
get_all_words_with_prefix(prefix)
Adăugarea Word la trie
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
Preluarea datelor
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
funcția ne va spune dacă cuvântul există sau nu în Trie. Deoarece al nostru este un dicționar, trebuie să preluăm și sensul, acum să declarăm o funcție pentru a face acest lucru.
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:])
Ștergerea datelor
Ștergând date, trebuie doar să modificați variabila ends_here
la False
. Dacă faceți acest lucru, nu modificați prefixele, dar totuși șterge semnificația și existența cuvântului din trie.
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:])

#Implementarea #structurii #date #Trie
Implementarea structurii de date Trie