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 1 Avantatges 2 Aplicacions 2.1 Substituint taules de dispersi?? 2.2 Com a representaci?? de diccionaris 2.3 Algorismes 2.4 Ordenaci??

[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.