Implementacija Trie strukture podataka

Uvod

Riječ trie infliks je riječi "re trie val", jer trie može pronaći jednu riječ u rječniku sa samo prefiksom riječi.

Trie je učinkovita struktura podataka za pronalaženje podataka. Koristeći trie, složenost pretraživanja može se dovesti do optimalne granice, tj. Duljine niza.

To je višesmjerna struktura stabla korisna za spremanje nizova preko abecede, kada ih pohranjujemo. Korišten je za pohranu velikih rječnika engleskog, recimo, riječi u programe za provjeru pravopisa. Međutim, kazna za pokušaje je zahtjev za pohranom.

Što je trie?

Trie je struktura podataka poput stabla koja pohranjuje nizove i pomaže vam pronaći podatke povezane s tim nizom pomoću prefiksa niza.

Na primjer, recimo da planirate izgraditi rječnik za spremanje nizova zajedno s njihovim značenjima. Sigurno se pitate zašto ne mogu jednostavno upotrijebiti hash tablicu kako bih dobio informacije.

Da, podatke možete dobiti pomoću hash tablice, ali hash tablice mogu pronaći samo podatke gdje se niz točno podudara s onim koji smo dodali. No, trie će nam pružiti mogućnost da u kraćem vremenu pronađemo nizove s uobičajenim prefiksima, nedostajućim znakom itd. U usporedbi s hash tablicom.

Trie obično izgleda otprilike ovako,

Trie

Ovo je slika Triea, koji pohranjuje riječi {assoc, algo, all, also, tree, trie}.

Kako provesti trie

Primijenimo trie u python, za pohranu riječi s njihovim značenjima iz engleskog rječnika.

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.

Kao što vidite, rubovi su duljine 26, a svaki se indeks odnosi na svaki znak u abecedi. 'A' odgovara 0, 'B' do 1, 'C' do 2 ... 'Z' 25. indeksu. Ako lik kojeg tražite pokazuje na to None, to znači da riječi nema u trieu.

Tipični Trie trebao bi implementirati barem ove dvije funkcije:

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

Uz to se može dodati i nešto poput

  • get_all_words()
  • get_all_words_with_prefix(prefix)

Dodavanje riječi u 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

Dohvaćanje podataka

 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_wordFunkcija će nam reći je li riječ postoji u Trie ili ne. Budući da je naš rječnik, trebamo dohvatiti i značenje, sada dopustimo deklarirati funkciju koja to radi.

 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:])

Brisanje podataka

Brisanjem podataka samo trebate promijeniti varijablu ends_hereu False. Na taj se način ne mijenjaju prefiksi, ali fotografije uklanjaju značenje i postojanje riječi iz 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:])
:raketa:

Pokreni kod