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,

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_word
fü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_here
a 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:])

Futtassa a kódot