Trie adatstruktúra megvalósítása

Programozás

Bevezetés

A trie szó a „re trie val” szó inflixje , mert a trie egyetlen szót találhat a szótárban, csak a szó előtagjával.

A Trie hatékony adat-visszakeresési adatszerkezet. A trie használatával a keresési bonyolultságok optimális határértékig, azaz a karakterlánc hosszáig vihetők.

Ez egy többutas fa szerkezet, amely hasznos a karakterláncok ábécé fölötti tárolásához, amikor tároljuk őket. Nagy angol, mondjuk szavak szótárak tárolására használták a helyesírás-ellenőrző programokban. A próbálkozások büntetése azonban a tárolási követelmény.

Mi az a trie?

A trie egy fa-szerű adatstruktúra, amely karakterláncokat tárol, és segít megtalálni az adott karakterlánchoz társított adatokat a karakterlánc előtagja segítségével.

Tegyük fel például, hogy tervez egy olyan szótár felépítését, amely a húrokat és azok jelentését együtt tárolja. Biztos kíváncsi vagy arra, miért nem használhatok egyszerűen hash táblázatot az információk megszerzéséhez.

Igen, információkat hash tábla segítségével szerezhet be, de a hash táblák csak olyan adatokat találnak meg, ahol a karakterlánc pontosan megegyezik az általunk hozzáadott karakterlánccal. De a trie lehetővé teszi számunkra, hogy rövidebb idő alatt megtaláljuk a közös előtagokkal, hiányzó karakterekkel stb. Rendelkező húrokat, összehasonlítva a hash táblával.

A trie általában valami ilyesmit mutat,

Trie

Ez egy Trie képe, amely az {assoc, algo, all, also, tree, trie "szavakat tárolja.

Hogyan lehet megvalósítani a trie-t

Vezessünk be egy trie-t a pythonban, a szavak jelentéseinek tárolásához egy angol szótárból.

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.

Mint láthatja, az élek 26 hosszúak, minden index az ábécé minden karakterére utal. Az 'A' 0-nak, a 'B' 1-nek, 'C' 2-nek felel meg ... 'Z' a 25. indexnek felel meg. Ha a keresett karakter rámutat None, ez azt jelenti, hogy a szó nem szerepel a trie-ben.

Egy tipikus Trie-nek legalább ezt a két funkciót kell végrehajtania:

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

Ezenkívül hozzá lehet adni valami hasonlót is

  • get_all_words()
  • get_all_words_with_prefix(prefix)

Word hozzáadása a trie-hez

 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

Adatok lekérése

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

A search_wordfüggvény megmondja, hogy a szó létezik-e a Trie-ben, vagy sem. Mivel a miénk egy szótár, be kell szereznünk a jelentést is, most lehetővé teszi egy funkció deklarálását erre.

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

Adatok törlése

Adatok törlésével, akkor csak meg kell változtatni a változó ends_herea False. Ez nem változtatja meg az előtagokat, de mégis törli a szó jelentését és létezését a trie-ből.

 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:])
:rakéta:

Futtassa a kódot