Trie
În informatică , un trie (pronunțat / ˈtriː / sau / ˈtraɪ / ) este un tip de structură de date arborescentă ordonată utilizată pentru a reprezenta un set asociativ sau o matrice ale cărei chei sunt de obicei șiruri . Spre deosebire de un arbore de căutare binar , nodurile nu păstrează o copie a cheii lor, care depinde în schimb de locația nodului din arbore. Rădăcina arborelui este asociată cu șirul gol și toți descendenții unui nod împart prefixul asociat cu acel nod. Nu toate nodurile reprezintă în mod necesar o cheie semnificativă, care se găsește de obicei în frunze și posibil în unele, dar nu neapărat în toate nodurile interne.
Un trie poate fi văzut ca o instanță particulară a unui automat finit determinist : toate limbajele finite au un trie corespunzător care le reprezintă și fiecare trie poate fi asociat cu un automat finit deterministic aciclic.
Istorie
Încercările au fost descrise pentru prima dată de René de la Briandais în 1959. [1] [2] Termenul trie a fost introdus doi ani mai târziu de Edward Fredkin , care l-a pronunțat / ˈtriː / (ca arborele englezesc) și constă din silaba mijlocie a recuperării . [3] [4] Alți autori preferă pronunția / ˈtraɪ / (ca engleza try ) în loc să evite confuzia cu cuvântul copac în vorbire. [3] [4] [5]
Implementare
Un trie poate fi implementat în moduri diferite, cu diferite compromisuri între viteza operațiunilor și consumul de memorie. O implementare elementară se poate face printr-o listă legată de noduri, în care fiecare nod conține o serie de indicatori către copii, câte unul pentru fiecare caracter al alfabetului (deci 26 pentru alfabetul englez sau 256 pentru ASCII ). Această implementare este foarte simplă și eficientă în timp, dar ineficientă din punct de vedere al memoriei, deoarece dacă șirurile au relativ puține prefixe în comun (cum se întâmplă de exemplu în apropierea frunzelor), o mulțime de spațiu este ocupată de indicatori NULL (în cazul șiruri ASCII cu pointeri de 4 octeți, fiecare nod ocupă aproximativ 1 kB). [6] [7]
Problema consumului de memorie poate fi atenuată cu tehnica de reducere a alfabetului , care constă în reinterpretarea șirurilor ca șiruri noi, mai lungi, bazate pe un alfabet redus. De exemplu, un șir de n caractere din posibilul 256 în ASCII pe 8 biți poate fi reinterpretat ca un șir de 2n caractere pe un alfabet de 16 ciuguliri posibile. În acest fel, timpul de căutare se dublează, dar dimensiunea matricei indicatorului în noduri scade de 16 ori, economisind spațiu în care multe caractere sunt neutilizate. Cazul extrem constă în utilizarea unui alfabet cu un singur bit, adică să reprezinte șirurile în formă binară, cu toate acestea această alegere nu este adesea foarte convenabilă în practică datorită costului de accesare și manipulare a biților unici din memorie. [8]
O implementare alternativă utilizează o listă legată și reprezintă nodurile ca tripluri (simbol, copil, frate), unde copilul este primul copil al nodului, frate cel mai apropiat frate al nodului (următorul copil al tatălui actualului nod). [7] [9] Cu această codificare a nodului, trie poate fi reprezentat și ca un copac; un exemplu este structura cunoscută sub numele de "ternary trie" sau arborele de căutare ternar , introdus de Jon Bentley și Robert Sedgewick . [10]
Notă
- ^ René de la Briandais, Căutarea fișierelor folosind taste cu lungime variabilă , Proc. Western J. Computer Conf. , 1959, pp. 295–298.
- ^ Alamă , p. 336 .
- ^ a b Paul E. Black, trie , pe Dicționar de algoritmi și structuri de date , Institutul Național de Standarde și Tehnologie , 16 noiembrie 2009. Accesat la 15 iulie 2017 ( arhivat la 19 mai 2010) .
- ^ a b Franklin Mark Liang, Word Hy-phen-a-tion By Com-put-er ( PDF ), Universitatea Stanford, 1983. Accesat la 28 martie 2010 ( arhivat la 19 mai 2010) .
- ^ Donald Knuth , 6.3: Digital Searching , în The Art of Computer Programming Volume 3: Sorting and Searching , 2nd, Addison-Wesley, 1997, p. 492, ISBN 0-201-89685-0 .
- ^ Alamă , p. 341 .
- ^ a b Lloyd Allison, Tries , pe allisons.org . Adus la 18 februarie 2014 .
- ^ Brass , pp. 347–352 .
- ^ Sartaj Sahni, Tries , on Structures Data, Algorithms, & Applications in Java , University of Florida. Adus la 18 februarie 2014 .
- ^ Alamă , p. 353 .
Bibliografie
- Peter Brass, Advanced Data Structures , Cambridge University Press, 2008.
Alte proiecte
-
Wikimedia Commons conține imagini sau alte fișiere pe trie
