Algoritme de Ukkonen

Archiu:Suffix Tree using Ukkonen's Algorithm.jpg

Un eixemple d'arbre de sufixos al final

En ciències de la computació, el algoritme de Ukkonen és un algoritme online de temps de computació llineal, dissenyat per a la construcció eficient d'un arbre de sufixos per a una cadena ___MATH_0___. Propost per Esko Ukkonen en 1995, es distinguix pel seu enfocament incremental i la seua relativa simplicitat en comparació a solucions anteriors.

Prèviament, existien dos algoritmes capaços de construir arbres de sufixos en temps llineal: l'algoritme de Weiner (1973) i l'algoritme de McCreight (1976). No obstant, l'algoritme de Ukkonen destaca per la seua naturalea online*, permetent el processament de la cadena d'entrada de manera progressiva, caràcter a caràcter, sense requerir la totalitat de la cadena a l'inici.

Fonaments de l'Algoritme

L'algoritme de Ukkonen es basa en la construcció iterativa d'arbres de sufixos implícits*. Per a una cadena ___MATH_1___, es definix ___MATH_2___ com l'arbre de sufixos implícit que representa tots els sufixos de ___MATH_3___. L'algoritme, aplicat a una cadena ___MATH_4___ de llongitut ___MATH_5___, construïx successivament ___MATH_6___. L'eixecució es dividix en ___MATH_7___ fases, a on la fase ___MATH_8___ genera ___MATH_9___ a partir de ___MATH_10___. L'inclusió del caràcter especial ___MATH_11___ al final de ___MATH_12___ garantisa que ___MATH_13___ represente l'arbre de sufixos complet de ___MATH_14___.

Cada fase ___MATH_15___ es subdivide en ___MATH_16___ extensions. En l'extensió j*-ésima de la fase ___MATH_17___, l'algoritme busca el punt final del camí des de la raïl etiquetat en la subcadena ___MATH_18___ i, si és necessari, estén dit camí en el caràcter ___MATH_19___.

Regles d'Extensió

L'extensió dels camins es realisa segons les següents regles, aplicades al sufix ___MATH_20___ de ___MATH_21___ en l'extensió j*, a on ___MATH_22___ és el caràcter a agregar:

Regles d'Extensió

L'extensió dels camins es realisa segons les següents regles, aplicades al sufix ___MATH_23___ de ___MATH_24___ en l'extensió j*, a on ___MATH_25___ és el caràcter a agregar:

Regla 1: Extensió en Full

Si el camí per a ___MATH_26___ termina en un full, el caràcter ___MATH_27___ s'afig al final de l'etiqueta de l'aresta incident en eixe full.

Explicació: Imagina que vares aplegar al final d'una branca en l'arbre. Esta regla diu que, si vols afegir el nou caràcter 'c', simplement lo "pegues" al final d'eixa branca. Per eixemple, si tens la paraula "ana" representada en l'arbre i vols afegir la lletra "n" per a formar "anan", simplement afiges la "n" al final de la branca que representa "ana".

Regla 2: Extensió en Aresta o Nodo Intern

Si el camí per a ___MATH_28___ no termina en un full i cap camí des del punt final de ___MATH_29___ s'inicia en el caràcter ___MATH_30___, es crea una nova aresta etiquetada en ___MATH_31___ des del punt final de ___MATH_32___. Esta nova aresta incidix en un nou full etiquetat en ___MATH_33___. Si ___MATH_34___ termina en l'interior d'una aresta existent, es crea un nou nodo per a dividir l'aresta en el punt final de ___MATH_35___.

Explicació: Ara imagina que no vares aplegar al final d'una branca, sino que et trobes en mig d'una branca o en un punt a on es dividixen vàries branques. Si no veus cap branca que escomence en el nou caràcter 'c', llavors tens que crear una nova branca que ixca des d'eixe punt i estiga etiquetada en 'c'. Si estàs en mig d'una branca existent, primer tens que crear un nou punt de divisió (un nodo) per a poder escomençar la nova branca en 'c'.

Regla 3: Extensió Implícita

Si algun camí des del punt final de ___MATH_36___ ya s'inicia en el caràcter ___MATH_37___, no és necessari realisar cap acció, ya que el sufix ___MATH_38___ ya està representat en l'arbre.

Explicació: En este cas, ¡tens sòrt! El nou caràcter 'c' ya està present en l'arbre, eixint des del punt a on et trobes. Açò significa que el sufix que volies afegir ya està representat en l'arbre, aixina que no tens que fer res.

Enllaços de Sufixos (Suffix Links)

Els enllaços de sufixos* són una estructura clau per a l'eficiència de l'algoritme:

Definició: Siga ___MATH_39___ un nodo intern en etiqueta ___MATH_40___, a on ___MATH_41___ és un caràcter i ___MATH_42___ és una cadena (possiblement buida). Si existix un atre nodo ___MATH_43___ en etiqueta ___MATH_44___, llavors es definix un enllaç de sufix* ___MATH_45___ com una busca de ___MATH_46___ a ___MATH_47___.

Els enllaços de sufixos faciliten la localisació ràpida de sufixos en l'arbre, optimisant les operacions d'extensió.

Optimisació de l'Algoritme

L'algoritme de Ukkonen incorpora tècniques d'optimisació per a alcançar un temps d'eixecució llineal:

• Skip/Count Trick: Permet recórrer ràpidament les arestes de l'arbre quan es coneix l'existència d'un camí específic.
• Stop Trick: Deté la fase actual quan la Regla 3 s'aplica, evitant extensions innecessàries.
• Pointer Trick: Manté busques als fulls creats, simplificant l'aplicació de la Regla 1 en fases posteriors.

Complexitat Computacional

Gràcies a les regles d'extensió i les tècniques d'optimisació, l'algoritme de Ukkonen conseguix construir l'arbre de sufixos en temps i espai ___MATH_48___, a on ___MATH_49___ és la llongitut de la cadena d'entrada. Esta notació, coneguda com "Big O", indica que tant el temps que tarda l'algoritme en eixecutar-se com la cantitat de memòria que necessita creixen linealment en la llongitut de la cadena d'entrada. En atres paraules, si dupliquem la llongitut de la cadena, el temps d'eixecució i la memòria requerida també es duplicaran aproximadament. Esta eficiència és crucial per a treballar en texts extensos, ya que algoritmes en complexitat majors (com ___MATH_50___ o ___MATH_51___) es tornarien prohibitivamente llents en estos casos. La complexitat llineal de l'algoritme de Ukkonen es deu a la combinació inteligent de les regles d'extensió i les tècniques d'optimisació, que eviten la necessitat de realisar operacions redundantes i permeten construir l'arbre de sufixos de manera incremental i eficient.