Trie

U računarstvu, trie, ili često nazivano digitalno stablo i ponekad radiks stablo ili prefiksno stablo (pošto se može pretraživati po prefiksu), je struktura podataka u obliku uređenog stabla koje se koristi za čuvanje elemenata dinamičkog skupa ili asocijativnog niza gde su ključevi obično niske karaktera. Za razliku od binarnog stabla pretrage, nijedan čvor u stablu ne čuva ključ koji odgovara tom čvoru. Umesto toga, sama njegova pozicija u stablu određuje ključ koji mu odgovara. Svi naslednici nekog čvora imaju zajednički prefiks niske karaktera koja odgovara tom čvoru, a korenu odgovara prazna niska. Uobičajeno je da se vrednosti ne dodeljuju svakom čvoru već samo listovima i nekim unutrašnjim čvorovima koji odgovaraju traženim ključevima.

Trie sa ključevima "A", "to", "tea", "ted", "ten", "i", "in", and "inn".

Termin trie potiče od engleske reči retrieval. Ovaj termin je prvi put upotrebio Edvard Fredkin, koji ga je izgovarao kao /ˈtriː/ engl. tree kao u reči retrieval. Međutim, drugi autori ime ove strukture izgovaraju kao /ˈtraɪ/ engl. try, kako bi pravili razliku od engl. trее.

U prikazanom primeru, ključevi su deo samih čvorova a njihove odgovarajuće vrednosti ispod njih. Svaka celovita reč ima dodeljenu proizvoljnu celobrojnu vrednost. Trie se može posmatrati kao deterministički konačni automat bez petlji. Svaki konačni jezik se može generisati trie automatom, i svaki trie se može sabiti u Deterministički aciklični konačni automat.

Nije neophodno da ključevi budu eksplicitno čuvani u čvorovima. (Na slici, reči su prikazane samo kako bi se ilustrovao rad trie strukture).

Iako su kod ove strukture, ključevi obično niske karakter, ne moraju biti. Isti algoritam se lako može adaptirati da obavlja iste funkcije sa uređenim listama bilo koje konstrukcije, npr. permutacije liste cifara ili oblika. Konkretno, bitovski trie radi sa ključevima u vidu individualnih bitova.

Primene

Kao zamena za druge strukture podataka

Kao što se i u nastavku pominje, trie ima veliki broj prednosti u odnosu na binarno stablo pretrage. Trie se takođe može koristiti i kao zamena za heš tabelu u odnosu na koju ima sledeće prednosti:

• Pretraga trie strukture je brža i u najgorem slučaju, vremenske složenosti O (m) (gde je m dužina tražene niske karaktera), u odnosu na lošiju heš tabelu. Lošija heš tabela može imati kolizije ključeva (heš funkcija slika različite ključeve na istu poziciju heš tabele). U najgorem slučaju, pretraga u lošijoj heš tableli je vremenske složenosti O(N), ali mnogo češće O(1) sa vremenskom složenošću O(m) evaluacije heš tabele.
• Ne postoji kolizija različitih ključeva u trie.
• Prostor za skladištenje podataka sa istim ključem je potreban samo ako se podaci razlikuju.
• Nema potrebe za heš funkcijom ili za zamenom heš funkcije novom kada se doda više ključeva u trie.
• Trie može pružiti alfabetsko uređenje vrednosti po ključu.

Kod trie strukture podataka postoje i loše strane:

• Trie može biti sporiji od heš tabele pri pretrazi, posebno kada su podaci čuvani na diskovima sa slučajnim pristupom ili drugim uređajima sekundarne memorije kod kojih je vreme slučajnog pristupa veliko u poređenju sa glavnom memorijom.
• Neki ključevi, kao što su brojevi sa pokretnim zarezom, mogu dovesti do velikih lanaca prefiksa koji su beskorisni. Ipak, bitovski trie može da radi sa standardom IEEE.
• Neki trie može koristiti više memorije nego heš tabela, jer se memorija alocira za svaki karakter u traženoj niski karaktera za razliku od jednog parčeta memorije koje se alocira kod heš tabele za tu istu nisku.

Predstavljanje rečnika

Česta primeta trie strukture je čuvanje prediktivnog teksta ili rečnika sa mogućnošću automatskog kompletiranja reči, poput onih u mobilnim telefonima. Takva primeta koristi mogućnost trie strukture da brzo pronađe, unese i obriše vrednost; ipak, ako je čuvanje reči iz rečnika sve što je potrebno (tj. ako nije potrebno čuvanje dodatnih informacija uz reči), minimalni deterministički aciklični konačni automat koristi manje memorije nego trie. To je zbog toga što aciklični deterministički konačni automat može sabiti identične grane stabla koje odgovaraju istim sufiksima (ili delovima) različitih reči koje se čuvaju.

Trie se takođe koristi i kod implementacije algoritama približnog poređenja, kao i kod provere pravopisa.

Algoritmi

Lako se može opisati pretraga u trie strukturi. Neka trie ima rekurzivno svojstvo, u svakom čvoru se nalazi lista trie potomaka, indeksirani sledećim karakterom u stringu, a svaki čvor opciono sadrži i vrednost. Ovde je ovaj tip podataka predstavljen u programskom jeziku Haskel:

 import Prelude hiding (lookup)
 import Data.Map (Map, lookup)
 
 data Trie a = Trie { value    :: Maybe a,
                      children :: Map Char (Trie a) }

Vrednost u trie možemo pronaći na sledeći način

 find :: String -> Trie a -> Maybe a
 find []     t = value t
 find (k:ks) t = do
   ct <- lookup k (children t)
   find ks ct

U imperativnom stilu, pod pretpostavkom da već postoji odgovarajući tip podataka, može se opisati isti algoritam u programskom jeziku Pajton. Pritom, children predstavlja mapu potomaka čvora a krajnji čvor je onaj koji sadrži validnu reč.

def find(node, key):
    for char in key:
        if char not in node.children:
            return None
        else:
            node = node.children[char]
    return node.value

Dodavanje novog elementa se odvija prolaskom kroz trie na osnovu niske koja se dodaje a zatim dodavanjem novih čvorova za sufiks niske koji se ne nalazi u trie-u. U imperativnom pseudokodu se to može predstaviti na sledeći način:

algorithm insert(root : node, s : string, value : any):
    node = root
    i    = 0
    n    = length(s)

    while i < n:
        if node.child(s[i]) != nil:
            node = node.child(s[i])
            i = i + 1
        else:
            break

    (* dodaj nove cvorove ako je potrebno *)
    while i < n:
        node.child(s[i]) = new node
        node = node.child(s[i])
        i = i + 1

    node.value = value

Sortiranje

Leksikografsko sortiranje skupa ključeva se može postići sledećim algoritmom baziranom na trie strukturi:

• Ubaciti sve ključeve u trie.
• Odštampati sve ključeve iz tria putem prefiksnog obilaska stabla, što čini da izlaz bude u rastućem leksikografskom poretku

Ovaj algoritam predstavlja varijaciju radiks sortiranja.

Trie je osnovna struktura podataka [[Burstsort]|burtsorta], koji je (2007. godine) bio najbrži poznati algoritam za sortiranje niski karaktera. Ipak, danas postoje i brži algoritmi za sortiranje niski karaktera.

Potpuno pretraživanje teksta

Posebna vrsta trie strukture, sufiksno stablo, može se koristiti u indeksiranju svih sufiksa u tekstu kako bi se primenilo brzo pretraživanje celokupnog teksta.

Bitovski trie

Bitovski trie je sličan osnovnom koji je zasnovan na karakterima, osim što se u ovom slučaju obilazak vrši pomoću pojedinačnih bitova, čineći strukturu binarnim stablom. Implementacije ove strukture koriste posebne procesorske instrukcije da se brzo pronađe bit prvog skupa iz ključa određene dužine(npr. kod GCC prevodioca to je instrukcija __builtin_clz()). Ova vrednost se potom koristi u indeksiranju tabele veličine 32 ili 64 koja pokazuje na prve elemente bitovskog trie-a sa tim brojem vodećih nula. Pretraga se potom nastavlja uz provere svakog sledećeg bita iz ključa i odabirom potomka child[0] ili child[1] dok se ne nađe traženi element.

Iako ovaj proces zvuči sporo, zbog principa lokaliteta i mogućnosti efikasnog paralelizovanja operacija on zapravo daje odlične performanse na modernim procesorima. Tako recimo, crveno-crno stablo daje mnogo bolje performanse na papiru ali u praksi ne daje najbolje rezultate upravo kako zbog niske lokalnosti (i samim tim loše iskorišćenosti keša) tako i zbog toga što uzrokuje lošu iskorišćenost protočne obrade. S druge strane, bitovski trie retko pristupa memoriji a kada to uradi, obavlja samo čitanje. Zbog toga, bitovski trie sve više postaje primarni izbor u situacijama kada se obavlja dosta dodavanja i brisanja kao što su memorijski alokatori (npr. novije verzije čuvenog dlmalloc alokatora i njegobih potomaka).

Primer implementacije bitovskog trie-a u jezicima C i C++ može se naći na adresi http://www.nedprod.com/programs/portable/nedtries/.

Komprimovani trie

Kada je trie uglavnom statičan, tj. kada se operacije dodavanja i brisanja elemenata ne koriste već se samo izvršava pretraga i kada su ključevi nezavisni od vrednosti samih čvorova moguće je komprimovati predstavljanje trie strukture spajanjem istih grana. Ova primena se uglavnom koristi kod komprimovanja tabela pretraživanja kada je ukupan skup smeštenih ključeva vrlo proređen u odnosu na sam prostor podataka.

Na primer, može se koristiti za predstavljanje proređenih skupova bitova (npr. podskupovi mnogo većih fiksnih nabrojivih skupova) koristeći trie čiji su ključevi pozicije bitovskih elemenata u celokupnom skupu i to tako da se ključevi dobijaju od niske karaktera bitova koja je neophodna za kodiranje pozicije svakog elementa. Trie će tada imati degenerisan oblik sa nedostajućim granama, a kompresija se omogućava čuvanjem listova stabla (delovi skupa sa fiksiranom dužinom) i njihovim kombinovanjem kada se ustanovi da sadrže iste delove ili popunjavanjem odgovarajućih praznina.

Ovakvo komprimovanje se takođe koristi i u implementacijama raznih tabela za brzu pretragu koje vraćaju karakteristike Unikod karaktera (npr. tabele pretrage koje sadrže kombinacije baznih i kombinovanih karaktera koji su potrebni u normalizaciji Unikoda). Za takve primene, reprezentacija je slična transformisanju velikih jednodimenzionih retkih tabela u višedimenzione matrice a potom korišćenje koordinata hiper-matrice kao string ključ nekomprimovanog trie-a. Komprimovanje tada podrazumeva pronalaženje i spajanje istih kolona hiper-matrice kako bi se komprimovala poslednja dimenzija u ključu; svaka dimenzija hiper-matrice sadrži početnu poziciju u vektoru sledeće dimenzije za vrednost svake koordinate, a rezultujući vektor se može kompresovati ako je takođe redak, tako da se svaka dimenzija (vezana za jedan nivo u trie-u) može komprimovati posebno.

Neke implementacije podržavaju takve kompresije u dinamičkom retkom trie-u sa omogućenim unošenjem i brisanjem elementa trie-a. Ovakve implementacije imaju značajan trošak pri rastavljanju i spajanju grana, a određeni ustupci se prave između najmanje veličine kompresovanog trie-a i brzine ažuriranja, ograničavajući globalnu pretragu za upoređivanje istih grana u retkom trie-u.

Rezultat takve kompresije može delovati slično kao transformisanje trie strukture u usmereni aciklični graf, jer reverzna transformacija takvog grafa u trie je očigledna i uvek moguća, ipak ona je ograničena oblikom ključa kojim se indeksiraju čvorovi.

Jedan od drugih načina kompresije je preslikavanje strukture podataka u niz bajtova. Ovaj pristup eliminiše potrebu za pokazivačima na čvorove što znatno smanjuje memorijske zahteve i omogućava mapiranje memorije što dalje dovodi do mnogo efikasnijeg učitavanja podataka u memoriju.

Još jedan pristup komprimovanju je tzv. „pakovanje“ trie-a.

Prednosti u odnosu na druge algoritme pretrage

• Grafički prikaz ponašanja različitih algoritama u odnosu na broj elemenata
• 
  Ponašanje Fredkin trie strukture kao funkcija veličine
  (u ovom slučaju, nedtrie strukture, što podrazumeva implementaciju u mestu, što uzrokuje da ima znatno strmiju krivu u odnosu na dinamičke implementacije trie-a)
• 
  Ponašanje crveno-crnih stabala kao funkcija veličine
  (u ovom slučaju, BSD implementacija rbtree.h, koja pokazuje klasično O(log N) ponašanje)
• 
  Ponašanje heš tabele kao funkcija veličine
  (u ovom slučaju, uthash, koja u proseku ispoljava ponašanje složenosti O(1))

Za razliku od većine drugi struktura podataka, trie ima čudnu osobinu da je složenost koda, a samim tim i potrebno vreme, skoro identično za operacije dodavanja, brisanja i pretraživanja. Kao rezultat toga, u situacijama kada kod vrši dodavanje, brisanje i pronalaženje elemenata u jednakoj meri, trie može lako pobediti binarno stablo pretrage. S druge strane, ova trie struktura omogućava bolju podlogu za efikasno keširanje procesorskih instrukcija i grananja.

Glavne prednosti trie strukture nad binarnim stablom pretrage (BSP):

• Operacija pretrage ključeva je brža. Pretraga ključa dužine m ima vremensku složenost O(m). BSP vrši O(log(n)) poređenja ključeva, gde je n broj elemenata stabla, jer pretraga zavisi od visine stabla koje je logaritamsko ako je stablo balansirano. Stoga, u najgorem slučaju, pretraga u BSP ima O(m log n) vremensku složenost. Takođe, operacije koje koristi trie pri pretrazi (pristup nizu preko indeksa koji je karakter) su brze na realnim mašinama.
• Trie je prostorno efikasnija struktura kada sadrži veliki broj kratkih ključeva, jer su čvorovi zajednički ključevima sa istim prefiksima.
• Trie olakšava problem najdužeg zajedničkog prefiksa.
• Broj unutrašnjih čvorova od korena do listova je jednak dužini ključa, tako da nema potrebe za balansiranjem stabla.

Glavne prednosti trie-a nad heš tabelom su:

• Trie podržava uređene iteracije dok su iteracije nad heš tabelom u pseudo-slučajnom poretku, što zavisi od heš funkcije kao i rešavanja kolizija (što je određeno implementacijom)
• Trie olakšava problem najdužeg zajedničkog prefiksa.
• Trie je u proseku brži pri unošenju elementa od heš tabele jer heš tabela mora da prepravi indekse kada se napuni, što je skupa operacija. Trie stoga ima bolje ograničenu vremensku složenost u najgorem slučaju.
• Za ključeve manje dužine, trie je brži jer nema korišćenja heš funkcije.

Vidi još

• Sufiksno stablo
• Radiks stablo
• Deterministički konačni automat

Literatura

• Knuth, Donald (1997). „6.3: Digital Searching”. The Art of Computer Programming Volume 3: Sorting and Searching (2nd izd.). Addison-Wesley. str. 492. ISBN 978-0-201-89685-5. 
• de la Briandais, R. (1959). „File Searching Using Variable Length Keys”. Proceedings of the Western Joint Computer Conference: 295—298. 

Spoljašnje veze

• NIST's Dictionary of Algorithms and Data Structures: Trie
• Trie implementation and visualisation in flash
• Tries by Lloyd Allison
• ServerKit "parse trees" implement a form of Trie in C
• Data::Trie and Tree::Trie – Perl implementations