Trie
De Viquipèdia
Un trie és un cas especial d' autòmat finit determinista (S,Σ,T,s,A), que serveix per a emmagatzemar un conjunt de cadenes E en el qual:
- Σ és l'alfabet sobre el qual estan definides les cadenes;
- S, el conjunt d'estats, cadascun dels quals representa un prefix de E;
- la funció de transició:
; està definida com segueix: T(x,σ) = xσ si 
, i indefinida altrament; - l'estat inicial s correspon a la cadena buida λ;
- el conjunt d'estats d'acceptació
és igual a E.
El seu nom procedeix del terme anglés retrieval.
Taula de continguts |
[edita] Avantatges
Els avantatges principals dels tries per sobre dels arbres de cerca binària són:
- cerca de claus més ràpida. La cerca d'una clau de longitud m tindrà, en el pitjor dels casos, un cost de l'ordre O(m). Un BST (Binary Search Tree, Arbre de cerca binària en anglés) té un cost de l'ordre O(logn), amb n elements a l'arbre, ja que la cerca depèn de la profunditat de l'arbre, logarítmica amb el nombre de claus
- necessita menys espai per emmagatzemar una gran quantitat de cadenes petites, ja que les claus no s'emmagatzemen explícitament
- té un millor funcionament per a l'algorisme de cerca del prefixe més llarg
[edita] Aplicacions
Com a substitució d'altres estructures de dades
[edita] Substituint taules de dispersió
Un Trie es pot utilitzar per substituir una Taula de dispersió, sobre la qual presenta els següents avantatges:
- el temps de cerca en una taula de dispersió imperfecta és de l'ordre de O(n), i en un trie es de l'ordre de O(l). Açò és degut a les colisions de claus
- en un trie no es produeixen colisions de claus
- no cal definir cap funció de dispersió, o modificar-la si afegim més claus
- els contenidors que emmagatzemen els distints valors associats a una única clau només són necessaris si tenim més d'un valor associat a una única clau. En una taula de dispersió sempre es necessiten aquestos contenidors per a les colisions de clau
- un trie pot proporcionar-nos una ordenació alfabètica de les entrades per clau
Els principals desavantatges dels tries respecte a les taules de dispersió són:
- en determinats casos poden ser més lents que les taules hash en la cerca de dades, especialment si les dades són consultades des de dispositius d'emmagatzematge secundaris, com el disc dur, on el temps d'accés és elevat respecte a la memòria principal
- no és senzill representar totes les claus com a cadenes. Un exemple poden ser els números reals, que poden tindre distintes representacions en forma de cadena per a un mateix nombre: p.ex. 1, 1.00, 1.000, +1.000,...
- moltes vegades els tries són més ineficients respecte a l'espai que les taules de dispersió
- els tries no solen estar disponibles amb les eines de desenvolupament de programari, al contrari que les taules de dispersió
[edita] Com a representació de diccionaris
Una aplicació freqüent dels tries es l'emmagatzematge de diccionaris, com els que es troben als telèfons mòbils. Aquestes aplicacions s'aprofiten de la capacitat dels tries per fer cerques, insercions i esborrats de manera ràpida. No obstant, si només es necessita desar paraules (per exemple, no es necessita informació auxiliar de les paraules del diccionari) un autòmat finit determinista acíclic mínim utilitza menys espai que un trie.
Els també són útils en la implementació d'algorismes de correspondència aproximada, com els utilitzats al programari de correcció ortogràfica.
[edita] Algorismes
El següent pseudocodi determina si una cadena representa un trie.
funcio cerca(node, clau) {
si (clau és una cadena buida) { # cas base
retorna (es un node terminal?)
} sinó { # cas recursiu
c = primer_caracter_de_la_clau # açò funciona perquè la clau no està buida
cua = clau_mens_el_primer_caràcter
fill = node.fills[c]
si (fill és nul) { # no es pot fer la recursió, encara que la clau no està buida
retorna fals
} sinó {
retorna cerca(fill,cua)
}
}
}
Nota: fills és un vector amb els fills del node, i un node terminal és aquell que conté una paraula vàlida.
[edita] Ordenació
L'ordre lexicogràfic d'un conjunt de claus es pot realitzar com un algorisme simple basat en tries de la següent forma:
- inserir totes les claus en el trie
- obtenir totes les claus mitjançant un recorregut en pre-ordre, per obtenir un ordenament lexicogràfic en ordre ascendent, o mitjançant un recorregut en post-ordre, per obtenir un ordenament lexicogràfic en ordre descendent. El recorregut en pre-ordre i en post-ordre són algorismes de cerca en profunditat d'arbres.
