Trie Datastruktur Implementering

Introduktion

Ordet trie er et tilføjelse af ordet "re trie val", fordi trie kan finde et enkelt ord i en ordbog med kun et præfiks for ordet.

Trie er en effektiv datastruktur til datahentning. Ved hjælp af trie kan søgekompleksiteter bringes til en optimal grænse, dvs. strengens længde.

Det er en flervejs træstruktur, der er nyttig til lagring af strenge over et alfabet, når vi opbevarer dem. Det er blevet brugt til at gemme store ordbøger på engelsk, siger ord i stavekontrolprogrammer. Sanktionen ved forsøg er imidlertid lagringskravene.

Hvad er en trie?

En trie er et trælignende datastruktur, der gemmer strenge og hjælper dig med at finde de data, der er knyttet til den streng ved hjælp af præfikset for strengen.

Sig for eksempel, at du planlægger at opbygge en ordbog til at gemme strenge sammen med deres betydning. Du må undre dig over, hvorfor ikke jeg bare kan bruge en hash-tabel for at få oplysningerne.

Ja, du kan få oplysninger ved hjælp af en hash-tabel, men hash-tabellerne kan kun finde data, hvor strengen nøjagtigt matcher den, vi har tilføjet. Men trie vil give os muligheden for at finde strenge med almindelige præfikser, en manglende karakter osv. På kortere tid sammenlignet med en hash-tabel.

En trie ser typisk sådan ud,

Trie

Dette er et billede af en Trie, der gemmer ordene {assoc, algo, all, also, tree, trie}.

Sådan implementeres en trie

Lad os implementere en trie i python til lagring af ord med deres betydning fra en engelsk ordbog.

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.

Som du kan se, er kanterne 26 lange, hvert indeks henviser til hvert tegn i alfabetet. 'A' svarer til 0, 'B' til 1, 'C' til 2 ... 'Z' til det 25. indeks. Hvis det tegn, du leder efter, peger på None, betyder det, at ordet ikke er der i trien.

En typisk Trie skal implementere mindst disse to funktioner:

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

Derudover kan man også tilføje noget lignende

  • get_all_words()
  • get_all_words_with_prefix(prefix)

Tilføjelse af Word til 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

Henter data

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

Den search_wordfunktion vil fortælle os, hvis ordet findes i Trie eller ej. Da vores er en ordbog, skal vi også hente betydningen. Lad os nu erklære en funktion til at gøre det.

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

Sletning af data

Ved at slette data skal du bare ændre variablen ends_heretil False. At gøre det ændrer ikke præfikser, men stiller sletter betydningen og eksistensen af ​​ordet fra 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:])
:raket:

Kør kode