Reconocimiento-de-palndromos-con-brecha-en-una-de-sus-mitades-y-su-implementacion-en-java

Vista previa del material en texto

UNIVERSIDAD NACIONAL AUTÓNOMA 
 DE MÉXICO 
 
 FACULTAD DE CIENCIAS 
 
 
RECONOCIMIENTO DE PALÍNDROMOS CON 
BRECHA EN UNA DE SUS MITADES Y SU 
IMPLEMENTACIÓN EN JAVA 
 
 
T E S I S 
 
 QUE PARA OBTENER EL TÍTULO DE: 
 
LICENCIADO EN CIENCIAS DE LA 
COMPUTACIÓN 
 
 
 P R E S E N T A : 
 
VÍCTOR ZAMORA GUTIÉRREZ 
 
 
 
 
DIRECTOR DE TESIS: 
DRA. ELISA VISO GUROVICH 
 
2018 
 
Margarita
Texto escrito a máquina
CIUDAD UNIVERSITARIA, CD. MX.
Margarita
Texto escrito a máquina
 
UNAM – Dirección General de Bibliotecas 
Tesis Digitales 
Restricciones de uso 
 
DERECHOS RESERVADOS © 
PROHIBIDA SU REPRODUCCIÓN TOTAL O PARCIAL 
 
Todo el material contenido en esta tesis esta protegido por la Ley Federal 
del Derecho de Autor (LFDA) de los Estados Unidos Mexicanos (México). 
El uso de imágenes, fragmentos de videos, y demás material que sea 
objeto de protección de los derechos de autor, será exclusivamente para 
fines educativos e informativos y deberá citar la fuente donde la obtuvo 
mencionando el autor o autores. Cualquier uso distinto como el lucro, 
reproducción, edición o modificación, será perseguido y sancionado por el 
respectivo titular de los Derechos de Autor. 
 
 
 
1. Datos del alumno
Zamora
Gutiérrez
Víctor
55 23 15 47
Universidad Naciona Autónoma de 
México
Facultad de Ciencias
Ciencias de la Computación
311529058
2. Datos del tutor
Dra.
Elisa
Viso
Gurovich
3. Datos del sinodal 1
Dr.
José de Jesús
Galaviz
Casas
4. Datos del sinodal 2
Dra.
María de Luz
Gasca
Soto
5. Datos del sinodal 3
Dra.
Amparo
López
Gaona
6. Datos del sinodal 4
Dr.
Canek
Peláez
Valdés
7. Datos del trabajo escrito
Reconocimiento de palíndromos con brecha en una de sus mitades y su 
implementación en Java
61 p
2018
Índice general
Introducción III
1. Preliminares 1
2. Algoritmo de Ukkonen 5
2.1. Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2. Código . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3. Construcción de estructuras auxiliares 27
3.1. Construcción de arreglos de sufijos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.1. Código . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2. Construcción del arreglo de sufijos invertido . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.1. Código . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3. Construcción de arreglo LCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.1. Código . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4. Cálculo de consultas de rango mı́nimo . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.4.1. Código . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4. Reconocimiento de SAGP 35
4.1. Propiedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.2. Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2.1. Código . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.3. Cálculo de Pals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3.1. Código . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3.2. Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.4. Cálculo de SAGP1(T ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
i
4.4.1. Algoritmo ingenuo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.4.2. Algoritmo cuadrático simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.5. Cálculo de SAGP2(T ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.5.1. Cálculo de FindR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.5.2. Código para calcular SAGP2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Conclusiones 55
Introducción
El análisis del ADN es uno de los campos más importantes de la bioloǵıa molecular, ya que
nos ayuda a entender mejor el funcionamiento de los organismos. Como el ADN se representa por
medio de cadenas, y estas contienen patrones, encontrar y estudiar estos patrones es un tema de
gran interés. En particular varias estructuras importantes tienen forma de paĺındromos. Por ejemplo,
algunas estructuras de horquillas y triplex con esta forma se pueden relacionar con la presencia de
cáncer en un organismo [7]. Por esto es importante diseñar algoritmos que encuentren rápidamente
presencias de paĺındromos en textos grandes.
Sin embargo, a veces buscar paĺındromos no nos basta para estudiar completamente estas es-
tructuras, ya que en la naturaleza pueden ocurrir mutaciones en el ADN.
Algunas veces es útil incluir paĺındromos con errores en nuestras búsquedas. De aqúı surgen los
paĺındromos aproximados, que son cadenas parecidas a los paĺındromos, pero con alguna imperfec-
ción, como puede ser un carácter de más o un hueco.
El incluir paĺındromos aproximados en nuestras búsquedas complica las cosas, ya que en general,
estas cadenas son más dif́ıciles de reconocer. Dado que los textos de ADN suelen ser bastante grandes,
buscamos que el reconocimiento de paĺındromos aproximados sea lo más eficiente posible. Además,
los algoritmos deben ser prácticos y fáciles de implementar.
Los SAGP 1 o paĺındromos con brecha en una de sus mitades son un tipo de paĺındromos
aproximados. Fueron descritos originalmente por Narisada et al. en [8].
El objetivo de este trabajo es mostrar e implementar algunos algoritmos de reconocimiento de
SAGP .
Como los SAGP son un concepto relativamente nuevo, casi no hay literatura sobre ellos. Este
trabajo está escrito con el fin de que más gente pueda entender cómo y por qué funcionan los
algoritmos de reconocimiento de estas cadenas.
Varios de los algoritmos quizá puedan parecer complicados al principio (sobre todo porque la
notación es una barrera grande en el reconocimiento de cadenas), y si uno los lee en las fuentes
originales, requiere bastante tiempo y paciencia entenderlos. Mi meta es hacer del reconocimiento
de SAP algo más fácil de entender, además de proporcionar al lector algunas pruebas de la validez
de los algoritmos y una implementación en código 2.
A lo largo del trabajo, mostraré el funcionamiento de cada algoritmo, aśı como fragmentos de
1Del inglés single-arm-gapped palindromes
2Este trabajo contiene fragmentos del código fuente. El código completo se encuentra en mi repositorio de Github,
en la siguiente liga: https://github.com/victorz3/Implementation-of-SAGP-recognition-in-Java
iii
iv INTRODUCCIÓN
su código fuente.
Los algoritmos están implementados en el lenguaje de programación Java, sin utilizar bibliotecas
externas.
El trabajo está organizado de la siguiente manera. En el caṕıtulo 1, explico algunos conceptos
básicos de cadenas para introducir al lector en el contexto del problema. En el caṕıtulo 2, me dedico
a construir árboles de sufijos por medio del algoritmo de Ukkonen. En el caṕıtulo 3, construyo otras
estructuras auxiliares para el reconocimiento de SAGP . En el caṕıtulo 4, explico cómo reconocer
los SAGP . Por último, el caṕıtulo 5 contiene las conclusiones del trabajo.
Caṕıtulo 1
Preliminares
Sea Σ un conjunto de caracteres, lo llamaremos alfabeto. Un lenguaje L es un subconjunto de
Σ∗, donde ∗ es la operación conocida como estrella de Kleene, es decir, el conjunto de todas las
cadenas posibles de tamaño finito sobre śımbolos en Σ (incluyendo a la cadena vaćıa, ε).
A lo largo de este trabajo, consideraremos al alfabeto Σ como fijo y finito. Dentro de la compu-tadora, podemos considerar al alfabeto como el conjunto de caracteres en la tabla ASCII.
Para toda cadena w, denotamos su longitud con |w|. Para todo 1 ≤ i ≤ |w|, denotamos con
w[i] al carácter en la i-ésima posición de w. Una subcadena de w es una cadena x tal que existe un
1 ≤ j ≤ |w| que cumple que para todo 1 ≤ i ≤ |x|, x[i] = w[j+ i]. En particular, la cadena vaćıa y la
cadena total son subcadenas. Podemos denotar a x como w[j..j + |x| − 1]. Por convención, decimos
que si i > j, w[i..j] es la cadena vaćıa.
En una cadena w = xyz, decimos que x es un prefijo y z es un sufijo. Es decir, un prefijo es
una subcadena x = w[1..i], para 0 ≤ i ≤ |w| y un sufijo es una subcadena z = w[j..|w|], para
1 ≤ j ≤ |w| + 1. En particular, w y ε son el prefijo y sufijo de w con mayor y menor tamaño,
respectivamente.
Denotamos la reversa de w como wR = w[|w|]...w[1].
Para dos cadenas X e Y , denotamos la longitud de su prefijo más grande en común con
lcp(X,Y )1.
Decimos que una cadena es paĺındromo si se lee de la misma forma hacia adelante y hacia atrás.
Es decir, un paĺındromo es una cadena x = wgwR, donde g es un carácter o la cadena vaćıa.
Una cadena se llama paĺındromo con brecha si es de la forma wgwR, donde w es una cadena no
vaćıa y |g| ≥ 0. En particular todo paĺındromo es también un paĺındromo con brecha.
Un paĺındromo con brecha en una de sus mitades (SAGP en inglés) es una cadena ya sea de la
forma wuguRbwR o de la forma wbuguRwR, donde w y u son cadenas no vaćıas, |g| ≤ 1 y |b| ≥ 1.
Llamamos brecha a la cadena b.
Para una cadena texto, su conjunto de subcadenas (también llamadas factores) se denota como
F(texto).
1Del inglés longest common prefix.
1
2 CAPÍTULO 1. PRELIMINARES
Sea T un árbol dirigido con ráız, tal que tiene etiquetas en las aristas. Denotamos con etiqueta(e)
a la etiqueta de la arista e. La etiqueta de un camino π es la concatenación de las etiquetas de las
aristas de π y se representa con etiqueta(π). Además, denotamos al conjunto de etiquetas de T con
Etiquetas(T ). Es decir, Etiquetas(T ) = {etiqueta(π)|π es un camino dirigido que empieza en la
ráız de T}.
Decimos que un árbol T representa a los factores de una cadena w si Etiquetas(T ) = F(w).
El árbol de sufijos T de una cadena w es un árbol dirigido con ráız que representa los factores
de w y además cumple que:
Todo nodo no hoja tiene al menos dos hijos (al menos dos aristas salientes).
Toda arista representa una cadena no vaćıa.
Todo camino π desde la ráız a una hoja de T representa un sufijo de w.
Todas las aristas salientes de un nodo empiezan con caracteres distintos.
En el árbol de sufijos de una cadena w, cada hoja representa un sufijo de w. Por lo tanto,
tendremos O(|w|) hojas, pues w tiene exactamente |w|+ 1 sufijos.
Como cada nodo no hoja tiene al menos dos hijos, entonces hay un número logaŕıtmico de nodos
internos.
Por lo tanto, el árbol tiene tamaño O(|w|).
El arreglo de sufijos de una cadena w, SAw, es un arreglo que contiene todos los sufijos de w
en orden lexicográfico. En realidad no es necesario guardar los sufijos como tales en este arreglo,
ya que podemos representar a un sufijo con un entero, el del ı́ndice con el que empieza. Es decir,
podemos decir que el ı́ndice i representar al sufijo w[i..|w|]. En general, consideraremos ambas
representaciones como válidas y utilizaremos la que más nos convenga. Cuando hablemos de cadenas,
utilizaremos la representación que guarda los sufijos completos, mientras que cuando hablemos de
enteros utilizaremos la otra. A la hora de programarlo, es más conveniente utilizar una representación
con enteros para no gastar memoria de manera innecesaria.
El arreglo de sufijos invertido de una cadena w, SA−1w , es un arreglo que cumple SA
−1
w [SAw[i]] = i
para 1 ≤ i ≤ |w|.
El arreglo LCP (Longest Common Prefix en inglés) o del mayor prefijo en común, guarda las
longitudes de los prefijos en común más grandes entre dos cadenas consecutivas en el arreglo de
sufijos. Este arreglo se denota como LCPw para una cadena w.
Formalmente, LCPw se define como:
LCPw[1] = −1.
Para 1 ≤ i ≤ |w|, LCPw[i] = lcp(SAw[i− 1], SAw[i]).
Definimos para una cadena T el arreglo Pals(T ) que tiene en la posición i la longitud de mitad
del paĺındromo más grande de T centrado en i.
3
También definimos la función LMostT que cumple que LMostT (c) = el ı́ndice de la primera
presencia de c en T (de izquierda a derecha).
Sea A un arreglo con valores enteros. Una consulta de rango mı́nimo (del inglés range minimum
query), CRM(i, j), nos dice el ı́ndice de [i, j] con menor valor en A.
Tras un preprocesamieno lineal, CRM(i, j) puede obtenerse en tiempo constante para cuales-
quiera dos ı́ndices i y j.
4 CAPÍTULO 1. PRELIMINARES
Caṕıtulo 2
Algoritmo de Ukkonen
Los árboles de sufijos tienen un uso muy amplio en algoritmos sobre cadenas [2]. Para construirlos
hay varios algoritmos entre los que se encuentra el algoritmo de Ukkonen, que es el que utilicé en
este trabajo.
Propuesto por Esko Ukkonen en 1995, el algoritmo de Ukkonen se utiliza para construir el árbol
de sufijos de una cadena en tiempo lineal sobre el tamaño de esta [9].
Aunque no fue el primer algoritmo de construcción de árboles de sufijos en tiempo lineal, el
algoritmo de Ukkonen tiene varias ventajas sobre sus predecesores. Primero, busca ser un algoritmo
fácil de entender, aunque en mi opinión no lo es tanto. Además, el algoritmo es en ĺınea, lo que
quiere decir que procesa la entrada carácter por carácter, leyendo de izquierda a derecha y conforme
va construyendo el árbol.
Esta implementación está hecha en el lenguaje de programación Java. Busqué que la implemen-
tación fuera transparente y fácil de entender. Por lo mismo, la implementación no está basada en
el art́ıculo original de Ukkonen, sino en la explicación, bastante más sencilla presentada por Goller
[4].
Al ser una explicación un tanto informal, hay varios casos que no deja claros para los cuales
tuve que idear estrategias, teniendo en cuenta el no incrementar la complejidad del algoritmo.
Para entender la implementación, es necesario entender el algoritmo de Ukkonen primero, aśı
que daré una breve explicación de este.
Lo que queremos es un árbol de tamaño lineal que contenga todos los sufijos de x. Vamos a ir
construyendo el árbol de manera iterativa y añadiendo sufijos en cada iteración.
Un detalle importante es que para que el árbol esté bien constrúıdo al final (con todos los sufijos
insertados), es necesario agregar un carácter especial de terminación. Esto es para asegurar que
todos los nodos que no son hojas tengan dos o más hijos, lo cual solamente se puede hacer si ningún
sufijo es prefijo de otro sufijo. Para este programa, decid́ı utilizar #.
El algoritmo a grandes rasgos funciona aśı:
Se empieza con un nodo ráız y tres variables, punto activo, restantes y el ı́ndice i del carácter
que está siendo procesado. La variable punto activo representa el punto del árbol sobre el que se
5
6 CAPÍTULO 2. ALGORITMO DE UKKONEN
insertará el siguiente sufijo, el cual puede ser tanto un nodo como un punto en una arista. La variable
restantes indica el número de sufijos por insertar en la iteración en la que estamos. La idea es que
restantes se incremente en 1 en cada iteración y que se disminuya cada vez que insertemos un sufijo.
Tanto restantes como i se inicializan en 0 y punto activo se inicializa en la ráız. El punto activo
se representa con una 3-tupla (nodo activo, arista activa, longitud), que tiene el siguiente significa-
do:
nodo activo es el nodo a partir del cual encontraremos el punto activo. El punto activo puede
ser el nodo activo o un punto sobre alguna de las aristas que salen de este.
arista activa es la arista sobre la que vamos a insertar el siguiente sufijo, si es aplicable (es
decir, si vamos a insertar sobre un nodo, la arista activa es nula). Para fines didácticos vamos
a representar a la arista activa conel carácter con el que empieza, ya que al ser este un árbol
de sufijos, todas las aristas salientes de un nodo (en este caso, el nodo activo) empiezan con
un carácter distinto. Sin embargo, a la hora de programar, veremos que no siempre conviene
esa representación. Inicialmente, la arista activa vale ‘\0’, es decir, el carácter nulo, lo que
quiere decir que la arista en śı es nula.
longitud es el punto en la arista activa sobre el que insertaremos. Al inicio del algoritmo vale
0. Siempre que longitud valga 0, insertaremos sobre un nodo en lugar de sobre una arista.
Se itera sobre los caracteres de la cadena. En cada iteración, se incrementa i y se le suma uno
a restantes.
El ı́ndice i no solo funciona como apuntador en la cadena, también tiene la función de decirnos
hasta qué punto llega una arista. Es decir, como las subcadenas de las aristas se representan por
dos ı́ndices, inicio y fin (donde inicio dice dónde empieza la subcadena y fin nos dice dónde
termina), cada vez que creamos una arista, decimos que termina en i. Aśı, cuando actualicemos i,
la subcadena de la arista se actualizará automáticamente.
Por ejemplo, digamos que estamos construyendo el árbol de sufijos para la cadena banana. En
la primera iteración, vamos a insertar la b. Pero en lugar de representarla con la pareja (1, 1), la
representaremos con la pareja (1, i). Aśı:
[1, i]
Es decir que nuestra arista representa a la cadena b:
b
Luego en la siguiente iteración, i se incrementa. Aunque nuestra arista sigue viéndose aśı:
[1, i]
La cadena que representa ahora es banana#[1..2]:
7
ba
Sabiendo esto, el algoritmo es el siguiente:
En cada iteración, leemos un nuevo carácter. Esto a su vez significa que tenemos que insertar
un nuevo sufijo.
Los sufijos que vamos a insertar en cada iteración no son sufijos de la cadena total en śı, sino
de la cadena léıda hasta el momento, ya que el algoritmo es en ĺınea. Aqúı es donde entra el truco
de que el extremo derecho de las aristas se actualice automáticamente conforme crece la i; aśı, no
tenemos que preocuparnos por hacer esta actualización a mano.
Para el carácter que léımos, tenemos dos casos:
(a) El carácter que léımos ya fue insertado justo después del punto activo.
(b) El carácter que léımos no ha sido insertado justo después del punto activo.
Caso (a)
En el caso (a), incrementamos longitud y actualizamos la arista activa de ser necesario. Si la
arista activa era nula, entonces hay que buscar la arista que comience con el carácter que léımos.
En otro caso, solo hay que movernos un espacio sobre la arista activa. A veces nos saldremos de
la arista activa y en estos casos hay que actualizar el punto activo, que va a quedar en el extremo
derecho de la arista activa.
Por ejemplo, observemos la siguiente arista activa:
n1 n2
abc
Supongamos que el punto activo está justo antes de la c. Es decir, longitud vale 2. Supongamos
también que el siguiente carácter léıdo es c. Entonces, nos damos cuenta de que c ya fue insertado
(pues bien, está justo después del punto activo) y lo único que hacemos es incrementar longitud
como dicta el algoritmo. Entonces longitud vale 3, que es la longitud de la arista activa. En este
caso, tendremos que actualizar el punto activo a (n2, ‘\0’, 0) para que sea válido.
Caso (b)
Ya sabemos que el carácter actual no ha sido insertado. El punto activo nos indica en dónde
tenemos que insertarlo.
Nos falta insertar restantes sufijos, desde cadena[i− restantes+ 1..i] hasta cadena[i]. Para ello,
utilizaremos un ciclo while. Mientras restantes sea mayor que 0, nos fijamos si el carácter actual
ya fue insertado (nótese que en la primera iteración del while, esta condición nunca va a darse;
podŕıamos utilizar un do..while para ahorrarnos esta verificación). Si ya fue insertado, entonces
incrementamos longitud (como en el caso (a)) y nos salimos del while. En otro caso, hay que
8 CAPÍTULO 2. ALGORITMO DE UKKONEN
insertar el siguiente sufijo, es decir, hay que insertar (cadena[i− restantes+ 1..i]). Para esto, si el
punto activo es un nodo, entonces creamos una nueva arista y lo insertamos ah́ı. En otro caso, lo
vamos a insertar por medio de una operación llamada split, que básicamente parte la arista activa
a partir del punto activo, dándonos aśı tres aristas (la arista original y dos nuevos hijos) lo cual nos
genera un nuevo sufijo. Por ejemplo, si tenemos la siguiente arista:
a1 a2
abcabcf
Si el punto activo está justo después de la primera ‘c’, entonces al hacer un split, obtenemos la
siguiente figura:
a1 a2
b1
abcf
b2
f
abc
Después de insertar, disminuimos restantes, actualizamos el punto activo y volvemos al inicio
del while. Además, en caso de que hayamos hecho un split, es necesario revisar si es el primero
de la iteración, ya que si no lo es, tenemos que crear una arista invisible que va desde el último
nodo al que se hizo split hacia este. Esta arista invisible se llama liga de sufijo y se utiliza en la
actualización del punto activo.
La actualización del punto activo es la parte más importante (y complicada) del algoritmo. Para
explicarla, será más fácil utilizar un ejemplo. Veamos cómo se construye el árbol de sufijos de la
palabra abcabxabc.
2.1. Ejemplo
El primer paso en el algoritmo es pegarle el carácter de terminación (#) a nuestra cadena.
Entonces, vamos a construir el árbol de sufijos de la cadena abcabxabc#. Partimos de un nodo ráız
al que llamaré root.
root
nodo activo=root
arista activa=‘\0’
longitud=0
restantes=0
El nodo activo siempre estará en color rojo. En este caso, el nodo activo empieza siendo la ráız,
como hab́ıamos mencionado anteriormente.
Luego, leemos el primer carácter de nuestra cadena. Es ‘a’. Incrementamos restantes e i, lo que
los pone en 1. Como ‘a’ no ha sido insertado, lo insertamos en el punto activo, y como este es un
nodo, hay que crear una nueva arista que vaya desde la posición de ‘a’ (1) hasta i. La arista irá a
un nuevo nodo n1. Se verá aśı:
2.1. EJEMPLO 9
root n1
[1..i]
Que es la implementación de:
root n1
a
nodo activo=root
arista activa=‘\0’
longitud=0
restantes=0
Disminúımos restantes y leemos el siguiente carácter. Para los siguientes dos caracteres, pasará
lo mismo (se insertarán sin problemas), quedando aśı nuestro árbol, tras tres iteraciones 1:
root
n1
abc
n2
bc
n3
c
nodo activo=root
arista activa=‘\0’
longitud=0
restantes=0
En la siguiente iteración empieza lo interesante. Leemos el siguiente carácter, es decir ‘a’. Nos
fijamos que a partir del punto activo (que en este caso consiste del nodo activo), el carácter ‘a’
ya fue insertado (en la arista que va a n3). Por lo tanto, en lugar de insertar el siguiente sufijo,
movemos el punto activo a (root,‘a’, 1). Es decir, el punto activo está en la arista que va de root a
n1, entre la a y la b. Además, como incrementamos i y léımos otro carácter, el árbol se actualiza
automáticamente y queda aśı:
root
n1
abca
n2
bca
n3
ca
nodo activo=root
arista activa=‘a’
longitud=1
restantes=1
En la siguiente iteración, volvemos a incrementar restantes (ahora vale 2) y leemos el siguiente
1De aqúı adelante graficaré la abstracción del árbol, que es más clara que su implementación
10 CAPÍTULO 2. ALGORITMO DE UKKONEN
carácter. Para esto, incrementamos i. Como el siguiente carácter (‘b’) ya fue insertado a partir del
punto activo, solamente incrementamos longitud y el árbol queda:
root
n1
abcab
n2
bcab
n3
ca
b
nodo activo=root
arista activa=‘a’
longitud=2
restantes=2
En la siguiente iteración incrementamos i y leemos ‘x’. Al actualizar la i, se actualizan las aristas
del árbol aśı:
root
n1
abcabx
n2
bcabx
n3
ca
bx
nodo activo=root
arista activa=‘a’
longitud=2
restantes=3
Como ‘x’ no ha sido insertado a partir del punto activo, debemos insertarlo por medio de un
split. El árbol queda como sigue:
root
n1
n4
cabx
n5
x
ab
n2
bcabx
n3
ca
bx
nodo activo=root
arista activa=‘b’longitud=1
restantes=2
2.1. EJEMPLO 11
Decrementamos restantes en 1. Además, actualizamos el punto activo de acuerdo a la siguiente
regla:
Regla de actualización 1: Cuando hagamos una inserción en la que
root es el nodo activo
o
el punto activo es un nodo,
el punto activo se actualiza de la siguiente manera:
El nodo activo es root.
La arista activa se actualiza a la arista correspondiente al primer carácter del siguiente sufijo
por insertar. Los sufijos se van insertando de más grande a más pequeño. Como acabamos de
insertar el sufijo abx (el más grande de los 3 restantes), el siguiente sufijo por insertar será
el siguiente en tamaño, es decir, bx. Por lo tanto, la arista activa se actualiza a ‘b’.
La longitud se reduce en 1.
Notemos que la actualización de la arista activa solo se da si longitud no se vuelve 0.
Como aún nos hace falta insertar 2 sufijos, volvemos a verificar si el carácter ‘x’ ya fue insertado
a partir del punto activo. Como no es aśı, hacemos otro split.
De nuevo, actualizaremos el punto activo de acuerdo a la regla de actualización 1. Como longitud
ya vale 0, el punto activo automáticamente vuelve a ser un nodo (el nodo activo), por lo que la
arista activa vuelve a ser nula y el punto activo es root. Además, como hicimos dos split en la
misma iteración, debemos aplicar la siguiente regla:
Regla de split: Si hacemos un split sobre un nodo n y este no es el primer split de la iteración,
entonces es necesario conectar el nodo sobre el que se hizo el último split a n por medio de lo que
se llama una liga de sufijo.
En este caso, creamos una liga de sufijo desde n1 hasta n2. En cada nodo, escribiremos su liga
de sufijo (si existe) debajo del nombre del nodo.
12 CAPÍTULO 2. ALGORITMO DE UKKONEN
root
n1
n2
n4
cabx
n5
x
ab
n2 n6
cabx
n7
x
b
n3
ca
bx
nodo activo=root
arista activa=‘\0’
longitud=0
restantes=1
Falta insertar un sufijo más. Como ‘x’ no ha sido insertado, lo insertamos en el punto activo.
Es decir, creamos una arista que sale directamente de root.
root
n1
n2
n4
cabx
n5
x
ab
n2 n6
cabx
n7
x
b
n3
cab
x
n8
x
nodo activo=root
arista activa=‘\0’
longitud=0
restantes=0
Como ya insertamos todos los sufijos restantes, seguimos con el algoritmo.
Incrementamos i, dejándonos el siguiente árbol:
2.1. EJEMPLO 13
root
n1
n2
n4
cabxa
n5
xa
ab
n2 n6
cabxa
n7
xa
b
n3
cab
xa
n8
xa
nodo activo=root
arista activa=‘a’
longitud=1
restantes=1
El siguiente carácter léıdo es ‘a’, y como ya fue insertado, el punto activo cambia a (root,‘a’, 1).
Nos movemos a la siguiente iteración.
De nuevo incrementamos i, lo que nos da el siguiente árbol:
root
n1
n2
n4
cabxab
n5
xab
ab
n2 n6
cabxab
n7
xa
b
b
n3
cab
xab
n8
xa
b
nodo activo=n1
arista activa=‘\0’
longitud=0
restantes=2
Como la ’b’ ya fue insertada, el punto activo debeŕıa moverse a (root,‘a’, 2). Pero notemos que
este punto activo se sale de la arista activa. En este caso, lo que tenemos que hacer es mover el
punto activo al nodo derecho de dicha arista. Es decir, el punto activo en realidad se mueve a (n1,
14 CAPÍTULO 2. ALGORITMO DE UKKONEN
‘\0’, 0).
Incrementamos i y leemos el siguiente carácter, que es ‘c’. Como este ya fue insertado, solo es
necesario actualizar el punto activo. El árbol queda aśı:
root
n1
n2
n4
cabxabc
n5
xab
c
ab
n2 n6
cabxabc
n7
xa
bc
b
n3
cab
xab
c
n8
xa
bc
nodo activo=n1
arista activa=‘c’
longitud=1
restantes=3
Por último, incrementamos i y leemos el carácter de terminación.
root
n1
n2
n4
cabxabc#
n5
xab
c#
ab
n2 n6
cabxabc#
n7
xa
bc
#
b
n3
cab
xab
c#
n8
xa
bc
#
nodo activo=n1
arista activa=‘c’
longitud=1
restantes=4
Esta vez, el carácter léıdo (#) no ha sido insertado a partir del punto activo (pues efectivamente,
es la primera vez que lo vemos). Por lo tanto, hay que insertarlo por medio de un split:
2.1. EJEMPLO 15
root
n1
n2
n4
n9
abxabc#
n10
#c
n5
xab
c#
ab
n2 n6
cabxabc#
n7
xa
bc
#
b
n3
cab
xab
c#
n8
xa
bc
#
nodo activo=n2
arista activa=‘c’
longitud=1
restantes=3
En este caso la actualización del punto activo se hace de acuerdo a una nueva regla:
Regla de actualización 2: Después de hacer un split sobre un punto activo con nodo activo
distinto de root:
Si el nodo activo tiene liga de sufijo, entonces el nodo al que está ligado se vuelve el nuevo
nodo activo. Si no la tiene, root se asigna como el nuevo nodo activo.
La arista activa se cambia dependiendo de si el nodo activo teńıa liga de sufijo o no. En el
primer caso, la arista activa se queda igual. En el segundo caso, la arista activa se actualiza
al carácter i− restantes (donde si restantes es 0, se asigna nula).
La longitud no se cambia.
Tras hacer la actualización siguiendo esta regla, el punto activo será (n2,‘c’, 1).
Ahora, como aún nos falta insertar sufijos, hay que revisar si el carácter actual ya fue insertado.
Como no es aśı, hacemos otro split, por lo que el árbol queda como sigue:
16 CAPÍTULO 2. ALGORITMO DE UKKONEN
root
n1
n2
n4
n6
n9
abxabc#
n10
#c
n5
xab
c#
ab
n2 n6
n11
abxabc#
n12
#
c
n7
xa
bc
#
b
n3
cab
xab
c#
n8
xa
bc
#
nodo activo=root
arista activa=‘c’
longitud=1
restantes=2
El nodo activo vuelve a actualizarse de acuerdo a la regla 2. Además, no olvidemos la regla de
split, que nos indica que debe haber una liga de sufijo entre n4 y n6.
Nos falta insertar dos sufijos. Como de nuevo ‘#’ no ha sido insertado, hacemos otro split,
quedando el árbol como se ve abajo.
root
n1
n2
n4
n6
n9
abxabc#
n10
#
c
n5
xabc#
ab
n2
n6
n3
n11
abxabc#
n12
#c
n7
xab
c#b
n3 n13
abxabc#
n14
#
c
n8
xa
bc
#
nodo activo=root
arista activa=‘\0’
longitud=0
restantes=1
Podemos observar en este árbol que insertamos el sufijo c#. Además, agregamos otra liga de
sufijo de n6 a n3.
2.2. CÓDIGO 17
Nos falta insertar un último sufijo. De acuerdo a la regla 1, el punto activo se actualizó a
(root,‘\0’, 0), por lo que el último sufijo se insertará directamente sobre la ráız, como se observa en
la siguiente figura.
root
n15
# n1
n2
n4
n6
n9
abxabc#
n10
#
c
n5
xabc#
ab
n2
n6
n3
n11
abxabc#
n12
#c
n7
xab
c#
b
n3 n13
abxabc#
n14
#
c
n8
xa
bc
#
nodo activo=root
arista activa=‘\0’
longitud=0
restantes=0
Como restantes ya vale 0 y ya no hay más caracteres que leer, el árbol queda terminado.
Con esto, tenemos todas las reglas de árboles de sufijos.
2.2. Código
Codificar el algoritmo de Ukkonen viene con varios problemas. En la teoŕıa, como pudimos
observar, el algoritmo no es terriblemente complicado. Sin embargo, hay varios detalles que hacen
que su implementación no sea tan limpia como uno deseaŕıa.
El código consiste de una clase principal (Ukkonen.java) y varias clases para definir tipos de
datos. La clase principal solamente implementa el algoritmo y varios métodos auxiliares.
La clase Ukkonen tiene las siguientes variables:
private final String s; /* La cadena para la cuál construı́mos el árbol */
/* Las siguientes variables son variables especiales del algoritmo de Ukkonen */
private Arista activeEdge = null;
18 CAPÍTULO 2. ALGORITMO DE UKKONEN
private int activeLength = 0;
private int restantes = 0; /* Sufijos por insertar en la ronda actual del algoritmo de
Ukkonen */
private final Nodo root = new Nodo(); /* La raı́z del árbol */
private Nodo activeNode = root; /* El nodo activo debe inicializarse en la raı́z */
Es necesario guardar la cadena s no solo para poder leer caracteres en ĺınea, sino también para
poder sacar las subcadenas correspondientes a cada arista (pues recordemos, la representación de
una arista debe tener tan solo dos ı́ndices que indiquen donde empieza y donde termina su subcadena;
de otra manera, el árbol no tendŕıa tamaño lineal). Por lo mismo, la cadena está declarada como
final. De modificarla, los ı́ndices de las aristas perdeŕıan sentido.
Las clases que utilizo además de esta son Nodo, Arista y SuffixTree,que definen los tipos
respectivos con sus operaciones.
La clase Nodo sirve para representar a los nodos del árbol. Cada nodo puede guardar su liga de
sufijos, de qué arista viene (es decir, a la derecha de qué arista está el nodo), una lista de aristas
que salen de él y la longitud de la subcadena que va desde la ráız hasta el nodo.
public class Nodo{
private Nodo suffixLink = null; /* Suffix Link */
private Arista padre; /* La arista que incide en el nodo */
private List<Arista> aristas = new ArrayList<>(); /* Aristas que salen del Nodo */
private int longitud = 0; /* Longitud de la subcadena que va desde la raı́z hasta este
Nodo en el árbol de sufijos. */
La longitud la guardamos para poder realizar la actualización del punto activo en tiempo cons-
tante. En algunos casos, saltamos desde un nodo a otro mediante una liga de sufijos, y es necesario
saber en qué parte de la cadena estamos para poder actualizar el punto activo de manera correcta.
Por ejemplo, si tenemos la siguiente figura:
n1 n2 n3
n4
bc
n5
a
ac
Supongamos que acabamos de saltar a n2. Digamos que el siguiente sufijo a insertar es cabcad
y la arista activa vale ‘a’. Si longitud es mayor que 1 entonces, nos vamos a salir de la arista y
debemos elegir una de las aristas que salen de n3 para insertar el sufijo por ah́ı.
Es importante saber si la a de la arista que acabamos de leer es la a después de la primera c o
después de la segunda (para saber hacia dónde tenemos que recorrer el punto activo). Utilizando la
longitud de n3, podemos saber en qué parte de la subcadena estamos parados.
Es necesario mantener ordenada la lista de aristas del Nodo. Esto para poder hacer DFS lexi-
cográfico en tiempo lineal.2
2Imprimir los sufijos en orden lexicográfico es una funcionalidad deseable de los árboles de sufijos.
2.2. CÓDIGO 19
La longitud de un nodo empieza en 0 y se actualiza cuando hacemos un split sobre él. Teniendo
esto en cuenta, la longitud no siempre va a estar actualizada. Sin embargo, śı estará actualizada
siempre que la necesitemos (la longitud solo será necesaria en nodos sobre los que hayamos hecho
split, pues solo se necesita para decidir “qué camino tomar”). Con esto, mantenemos la complejidad
en tiempo del algoritmo.
Mantener ordenada la lista de aristas de un Nodo nos toma tiempo constante, ya que un nodo
tiene a lo más tantas aristas que salen de él como el tamaño del alfabeto (esto por la regla de que
las aristas salientes de un nodo deben empezar con caracteres distintos) y el alfabeto es de tamaño
constante.
Utilicé el siguiente código para agregar una nueva Arista a la lista del Nodo.
public void nuevaArista(Arista a){
int pos = Collections.binarySearch(aristas, a);
if (pos < 0){
aristas.add(-pos-1, a);
}
}
El código anterior busca la posición de inserción utilizando búsqueda binaria y mete la Arista
ah́ı.
Para poder utilizar la búsqueda binaria de la clase Collections, fue necesario hacer a la clase
Arista comparable. Compararar dos aristas consiste en comparar el carácter con el que comienzan,
tomando en cuenta que el carácter especial ‘#’ debe ser menor que cualquier otro carácter.
Además, para evitar el trabajo de insertar aristas en la lista del Nodo, el constructor de Arista
la inserta automáticamente aśı:
20 CAPÍTULO 2. ALGORITMO DE UKKONEN
public Arista(char primero, Nodo desde, Nodo hasta, int inicio, MutableInt fin){
this.primero = primero;
this.desde = desde;
this.hasta = hasta;
this.hasta.setPadre(this);
this.inicio = inicio;
this.fin = fin;
desde.nuevaArista(this);
this.hasta.setLongitud(desde.getLongitud() + this.longitud());
}
Las aristas guardan: su primer carácter, sus nodos izquierdo y derecho, aśı como sus ı́ndices de
inicio y fin. El fin se guarda como un MutableInt. Más adelante, explicaré cómo funciona dicha
clase, pero por ahora, podemos verlo como una envoltura de enteros que puede mutar (a diferencia
de la clase Integer de Java, que utiliza valores constantes).
El algoritmo consiste de un ciclo principal. En dicho ciclo, se va actualizando la i y se lee el
siguiente carácter de la cadena, la cual fue recibida como entrada previamente.
Como queremos que el algoritmo ocupe memoria lineal sobre el tamaño de la cadena (pues no
tendŕıa chiste usar este algoritmo de otra manera), entonces es necesario que las aristas contengan
solamente dos ı́ndices, en lugar de subcadenas. Aśı, cada arista ocupa memoria constante. Además,
no nos basta usar una estructura de datos primitiva int para los ı́ndices, pues queremos que se
actualicen automáticamente en nuestras aristas en cada iteración. En Java, esto se logra con una
clase auxiliar MutableInt, que representa un objeto entero que, cuando se incrementa, automáti-
camente se actualiza en todas las estructuras que lo utilicen3. La clase MutableInt es muy sencilla,
ya que solo es una envoltura de int con operaciones de autoincremento y comparación. Su código
es el siguiente:
public class MutableInt implements Comparable<Integer>{
private int value; /* Valor del entero */
/* Crea un nuevo entero mutable */
public MutableInt(int value){
this.value = value;
}
/* Autoincremento */
public void plusplus(){
value++;
}
/* Regresa el valor del entero */
public int getValue(){
return value;
3En general, los objetos en Java son mutables, por lo que al actualizarlos se modifican todas las instancias que
hacen referencia a ellos. Por lo mismo, a primera vista, parece conveniente utilizar la clase Integer para nuestra
representación de aristas. Sin embargo, esto no basta, ya que la clase Integer no es mutable por diseño.
2.2. CÓDIGO 21
}
/* Compara nuestro mutableInt con un objeto de la clase Integer */
@Override
public int compareTo(Integer i){
return this.value - i;
}
/* Nos dice si dos enteros mutables tienen el mismo valor */
@Override
public boolean equals(Object o){
if(!(o instanceof MutableInt))
return false;
MutableInt otro = (MutableInt) o;
return otro.getValue() == value;
}
/* Devuelve una cadena con el número */
@Override
public String toString(){
return Integer.toString(value);
}
El ciclo principal del algoritmo consiste de un for que va incrementando un MutableInt me-
diante el método plusplus:
MutableInt i = new MutableInt(0); /* Contador. */
for(;i.compareTo(s.length()) < 0; i.plusplus()){
En cada iteración del ciclo, inicializamos unas variables y leemos el siguiente carácter de la
cadena (el i-ésimo).
Nodo ultimoSplit = null; /* Último nodo sobre el que se hizo split */
boolean primeroInsertado = true; /* Nos dice si el sufijo fue el primero en insertarse
en esta iteración */
actual = s.charAt(i.getValue()); /* Leemos el siguiente carácter */
restantes++; /* Un sufijo más por insertar */
if(insertado(actual))
avanzaPuntoActivo(actual);
La variable ultimoSplit representa el último nodo sobre el que se hizo un split. primeroInsertado
es un valor lógico que nos indica si ya hicimos split o no (para saber si hay que actualizar enlaces
de sufijo).
De ah́ı, para ver si este ya fue insertado, utilizamos el siguiente método:
/* Nos dice si el carácter ya fue insertado a partir del punto activo.
* También actualiza la arista activa si esta no existe. */
public boolean insertado(char caracter){
if(activeEdge == null){ /* No hay arista activa */
22 CAPÍTULO 2. ALGORITMO DE UKKONEN
for(Arista vecino : activeNode.getAristas()){
if(startsWith(caracter, vecino))
return true;
}
}else
if(get(activeLength, activeEdge) == caracter)
return true;
return false;
}
Básicamente lo que hace ese método es dividir en dos casos: el punto activo es un vértice o el
punto activo está dentro de una arista.
En el primer caso nos fijamos, para las aristas que salen del vértice, si alguna comienza con el
carácter léıdo. Si es aśı, regresamos true. De otra manera, regresamos false.
En el segundo caso, nos fijamos si el siguiente carácter en la arista activa es el que léımos.
El método startsWithnos indica si la arista inicia con un carácter dado. El método getAristas
devuelve todas las aristas que salen de un nodo.
Si el carácter se encuentra, se actualiza el punto activo tal cual de acuerdo a las reglas. Esto lo
realiza el método avanzaPuntoActivo:
public void avanzaPuntoActivo(char actual){
if(activeEdge == null) /* Si no hay arista activa, la creamos */
activeEdge = this.busca(actual); /* Buscamos la arista que empieza con el
carácter */
/* Verificamos si ya nos salimos de la arista */
if(activeLength +1 == activeEdge.longitud()){
activeNode = activeEdge.getHasta();
activeLength = 0;
activeEdge = null;
}else /* No nos salimos de la arista */
activeLength++;
}
Esta rutina incrementa la longitud activa y actualiza la arista activa de ser necesario.
Si tenemos el siguiente punto activo:
n1 n2
a nodo activo=n1
arista activa=‘\0’
longitud=0
Al leer ‘a’, el punto activo se actualizará a (n2,‘\0’, 0), en lugar de a (n1,‘a’, 1).
La parte dif́ıcil del algoritmo empieza cuando el carácter no ha sido insertado, ya que entonces
tenemos que insertar un sufijo. Aqúı utilizo otro ciclo. Esta vez es un while que en el mejor de los
casos, se ejecuta mientras restantes > 0 (esto no siempre será aśı, pues como vimos anteriormente
hay veces en las que no es posible insertar todos los sufijos en la misma iteración). El cuerpo del
while básicamente hace todo lo que ya vimos: ver si el nodo activo es arista o vértice, insertar o
2.2. CÓDIGO 23
hacer un split, y después actualizar el punto activo y las ligas de sufijo de acuerdo a las reglas.
while(restantes > 0){
if(insertado(actual)){
avanzaPuntoActivo(actual);
break;
}
if(activeEdge == null){ /* El caso de insertar en una arista completamente nueva */
Nodo nuevo = new Nodo(); /* Extremo de la nueva arista */
Arista nueva = new Arista(s.charAt(i.getValue()), activeNode, nuevo,
i.getValue(), i);
restantes--;
primeroInsertado = false;
if(activeNode != root){
if(restantes == 1){
activeNode = root;
activeEdge = null;
activeLength = 0;
continue;
}else
regla2(i);
}
}else{ /* Partimos la arista */
split(i);
if(!primeroInsertado)
ultimoSplit.setSuffixLink(activeEdge.getHasta()); /* Actualización de enlace
de sufijo */
else
primeroInsertado = false;
/* Actualizamos el último nodo insertado */
ultimoSplit = activeEdge.getHasta();
restantes--;
if(activeNode == root){
activeLength--;
activeEdge = activeLength == 0 ? null :
busca(s.charAt((i.getValue()-restantes)+1));
verificaSalida(i);
}else
regla2(i);
}
}
Si el carácter no ha sido insertado, se manejan dos casos: insertar de nodo o insertar de arista.
Aunque las cosas se vuelven un tanto complicadas aqúı, realmente solo es cuestión de seguir
las reglas con cuidado. Para saber si hay que actualizar alguna liga de sufijo, guardo una varible
ultimoSplit que contienen el último nodo sobre el que se hizo un split.
Para la actualización del punto activo, sigo las reglas del algoritmo. Sin embargo, estas no toman
en cuenta el hecho de que al actualizar el punto activo, podemos caer en un punto inválido. Para
esto, hice una rutina que verifica si en la actualización caemos en un punto inválido y si es aśı,
24 CAPÍTULO 2. ALGORITMO DE UKKONEN
mueve el punto activo a donde debeŕıa estar. El método que realiza esto es el siguiente:
public void verificaSalida(MutableInt i){
while(activeEdge != null && activeLength >= activeEdge.longitud()){
activeNode = activeEdge.getHasta();
activeLength -= activeEdge.longitud();
if(activeLength != 0 && s.length() >
((i.getValue()-restantes)+1)+activeNode.getLongitud())
activeEdge =
busca(s.charAt(((i.getValue()-restantes)+1)+activeNode.getLongitud()));
else
activeEdge = null;
}
}
Justamente aqúı es cuando utilizamos la longitud de los nodos.
El código para hacer un split es el siguiente:
public void split(MutableInt indice){
int puntoPartida = activeEdge.getInicio()+(activeLength-1); /* Punto en el que
partimos nuestra arista */
if(activeEdge.getHasta().esHoja()){
activeEdge.setFin(new MutableInt(puntoPartida));
/* Dos nuevos nodos en los que se divide la arista: */
Nodo nuevo1 = new Nodo();
Nodo nuevo2 = new Nodo();
Arista nueva1 = new Arista(s.charAt(puntoPartida+1), activeEdge.getHasta(),
nuevo1, puntoPartida+1, indice);
Arista nueva2 = new Arista(s.charAt(indice.getValue()), activeEdge.getHasta(),
nuevo2, indice.getValue(), indice);
}else{
Nodo nuevo1 = new Nodo(); /* Nuevo nodo hasta el que llega la arista */
Nodo derecho = activeEdge.getHasta(); /* Extremo derecho de la arista activa */
MutableInt acaba = activeEdge.getFin(); /* Donde acaba la arista activa */
activeEdge.setHasta(nuevo1);
activeEdge.setFin(new MutableInt(puntoPartida));
Arista conexion = new Arista(s.charAt(puntoPartida+1), nuevo1, derecho,
puntoPartida+1, acaba);
Nodo nuevo2 = new Nodo(); /* Nodo recién insertado */
Arista nueva = new Arista(s.charAt(indice.getValue()), nuevo1, nuevo2,
indice.getValue(), indice);
}
}
Como mencioné previamente, dentro de los split actualizamos la longitud de los nodos. Esto no
se hace directamente, sino en los métodos setFin y setHasta de la clase Arista:
public void setHasta(Nodo n){
this.hasta = n;
n.setPadre(this);
2.2. CÓDIGO 25
this.hasta.setLongitud(desde.getLongitud() + this.longitud());
}
public void setFin(MutableInt fin){
this.fin = fin;
this.hasta.setLongitud(desde.getLongitud() + this.longitud());
}
Al hacer un split solo hay que crear dos nuevas aristas y actualizar ı́ndices. Cuando nuestra
arista no termine en una hoja, debemos tener cuidado de no perder la referencia del subárbol que
sale de ella.
Para saber si una arista termina en hoja o no, utilizamos el método esHoja que nos dice si un
nodo tiene aristas o no.
Por último, el método regla2 es el siguiente:
public void regla2(MutableInt i){
activeNode = activeNode.getSuffixLink();
if(activeNode == null){
activeNode = root; /* Si no habı́a enlace de sufijo, la raı́z se vuelve el nodo
activo */
activeEdge = busca(s.charAt(i.getValue() - restantes + 1));
activeLength = restantes-1;
}else{
if(activeEdge != null)
activeEdge = busca(activeEdge.getPrimero());
}
verificaSalida(i);
}
Como su nombre lo dice, este método actualiza el punto activo de acuerdo a la regla 2 del
algoritmo. Al final, llamamos a verificaSalida por si el punto activo es inválido.
26 CAPÍTULO 2. ALGORITMO DE UKKONEN
Caṕıtulo 3
Construcción de estructuras auxiliares
En este caṕıtulo me dedicaré a construir otras estructuras auxiliares para el reconocimiento de
SAGP .
3.1. Construcción de arreglos de sufijos
Ahora que sabemos cómo construir árboles de sufijos, construir arreglos de sufijos es sencillo. El
algoritmo para construir un arreglo de sufijos de una cadena w es el siguiente:
1. Construimos el árbol de sufijos, T , de w.
2. Recorremos T con DFS, tomando la rama de menor orden lexicográfico en cada paso1. Como
nuestras aristas están ordenadas, esto no require ningún cómputo adicional.
3. Cada vez que lleguemos a una hoja, copiamos su sufijo correspondiente en un arreglo. Para
sacar el sufijo correspondiente a una hoja, basta con tener una variable auxiliar que contenga
la cadena perteneciente al camino que hemos recorrido.
El algoritmo anterior tiene complejidad O(|w|), ya que, como hab́ıamos visto, el paso 1 toma
O(|w|) y al tener T tamaño lineal, recorrerlo también toma O(|w|).
3.1.1. Código
El código para la construcción de arreglos de sufijos se encuentra en la clase SuffixTree.java,
la cual tiene los siguientes atributos:
public class SuffixTree{
private final String cadena; /* La cadena sobre la que se elaboró el árbol */
private final Nodo raiz; /* La raı́z del árbol */
1Consideraremos al carácter especial # como el carácter de menor peso lexicográfico.
27
28 CAPÍTULO 3. CONSTRUCCIÓN DE ESTRUCTURAS AUXILIARES
private List<Integer> suffixArray; /* El arreglo de sufijos de la cadena del árbol */
private int[] reversed;/* El arreglo de sufijos invertido */
//Resto del código
}
Es necesario guardar la cadena total para poder identificar la subcadena que representa cada
arista.
Como cada nodo tiene una referencia a las aristas que salen de él, no es necesario guardar nada
además de la ráız del árbol.
Guardé el arreglo de sufijos como variable porque lo vamos a necesitar en el futuro, y aśı
podremos tener acceso a él sin necesidad de calcularlo más de una vez. No lo instanciaremos sino
hasta que lo vayamos a utilizar por primera vez.
Similarmente, el arreglo de sufijos invertido y el arreglo LCP se guardan como variables.
Para obtener el arreglo de sufijos, utilicé los siguientes métodos:
public List<Integer> getSuffixArray(){
if(this.suffixArray == null)
this.suffixArray = suffixArray(this.raiz);
return this.suffixArray;
}
private List<Integer> suffixArray(Nodo n){
ArrayList<Integer> regreso = new ArrayList<>(); /* Lista a regresar */
n.visita(true);
if(n.esHoja()){
regreso.add(cadena.length()+1);
return regreso;
}
for(Arista vecino: n.getAristas()){
Nodo sig = vecino.getHasta(); /* Siguiente Nodo a visitar */
if(sig.visitado())
continue;
for(Integer sub: this.suffixArray(sig))
regreso.add(sub - vecino.subcadena(this.cadena).length());
}
return regreso;
}
El primer método es lo que llamamos un singleton, un método que verifica si algo ya fue instan-
ciado y si es aśı, simplemente lo regresa. En otro caso, lo crea.
La lista que regresa este método es una lista de enteros, no de cadenas. Esto va de acuerdo con
la definición de arreglos de sufijos que vimos anteriormente.
El método es recursivo y lo que hace es obtener la lista de sufijos a partir de un vértice. Para
esto se fija si el vértice es hoja. Si es aśı, su lista de sufijos contiene únicamente a la cadena vaćıa
(la cuál, como previamente vimos, se puede representar como s[|s|+ 1..|s|]). Si no es hoja, entonces
tenemos que sacar la lista de sufijos de cada uno de sus hijos y restarle a todos los elementos de esta
3.2. CONSTRUCCIÓN DEL ARREGLO DE SUFIJOS INVERTIDO 29
lista la longitud de la cadena que representa a la arista entre el vértice y su hijo. El método devuelve
las cadenas en orden lexicográfico gracias a que ordenamos previamente las aristas salientes de cada
vértice.
Para obtener el arreglo de sufijos de la cadena total, simplemente llamamos al método anterior
con la ráız como parámetro. Aunque el método técnicamente nos regresa una lista, al ser esta
instancia de ArrayList la complejidad de las operaciones es la misma que la de un arreglo.
3.2. Construcción del arreglo de sufijos invertido
Construir el arreglo de sufijos invertido de una cadena w es muy sencillo una vez que tenemos
el arreglo de sufijos. Lo que hace el algoritmo es recorrer el arreglo de sufijos utilizando un ı́ndice i.
En cada paso, se guarda este ı́ndice en la posición SAw[i].
3.2.1. Código
El siguiente código obtiene el arreglo de sufijos invertido.
private int[] reversedSuffixArray(){
List<Integer> sA = this.getSuffixArray(); /* Obtenemos el arreglo de
* sufijos utilizando el singleton */
int[] rev = new int[sA.size()]; /* El arreglo que vamos a regresar */
for(int i = 0; i < sA.size(); ++i)
rev[sA.get(i)-1] = i+1;
return rev;
}
Al igual que en el caso del arreglo de sufijos, hay un método singleton que acompaña al método
anterior.
El método es bastante directo. La única dificultad es cuidar los ı́ndices dentro del for.
3.3. Construcción de arreglo LCP
Para construir el arreglo LCP utilicé el algoritmo de Kasai et al. [5]. El algoritmo utiliza tanto
el arreglo de sufijos como el arreglo de sufijos invertido.
Sea w una cadena. Recordemos que el arreglo LCPw contiene la longitud del mayor prefijo en
común para sufijos consecutivos en SAw. Es decir, LCPw[i] = lcp(SAw[i− 1], SAw[i]).
Para calcular este arreglo, hay que notar varias propiedades de la función lcp.
Propiedad 1. lcp(SAw[i− 1], SAw[i]) ≥ lcp(SAw[x], SAw[i]) para x ≤ i− 1
Demostración.
Por contradicción. Supongamos lcp(SAw[x], SAw[i]) > lcp(SAw[i− 1], SAw[i]). Sea z el prefijo más
30 CAPÍTULO 3. CONSTRUCCIÓN DE ESTRUCTURAS AUXILIARES
grande en común entre SAw[i− 1] y SAw[i] y sea y el prefijo más grande en común entre SAw[x] y
SAw[i]. Tenemos que z es prefijo de y, es decir, y = zα, con |α| > 0.
Sabemos que SAw[i− 1] = zβ. Aqúı tenemos dos casos, que β sea vaćıa o que no lo sea. Si β es
la cadena vaćıa, entonces tenemos que SAw[i− 1] es lexicográficamente menor a SAw[x], lo cual es
una contradicción, pues está después en el arreglo de sufijos.
Supongamos entonces que β tiene al menos un carácter. Sea c el primer carácter de β.
De manera análoga, digamos que SAw[x] = zγ. Aqúı no podemos tener γ vaćıa porque sabemos
que |SAw[x]| ≥ |y| > |z|. Sea entonces d el primer carácter de γ. Sabemos que d 6= c, pues si fueran
iguales, habŕıa un prefijo en común más grande que z para SAw[i− 1] y SAw[i].
Aqúı tenemos nuevamente dos casos: d > c o d < c.2 Si d > c, entonces tenemos que SAw[i− 1]
debeŕıa estar antes de SAw[x] en el arreglo de sufijos, lo cual es una contradicción. En el otro caso,
tenemos que SAw[i− 1] debeŕıa estar después de SAw[i] en el arreglo de sufijos (pues zd es prefijo
de SAw[i]), lo cual también es una contradicción.
Por lo tanto, lcp(SAw[i− 1], SAw[i]) ≥ lcp(SAw[x], SAw[i])
También necesitamos el siguiente resultado:
Propiedad 2. LCPw[SA
−1
w [i+ 1]] ≥ LCPw[SA−1w [i]]− 1 para 0 ≤ i < |w|
Demostración.
Recordemos que SA−1w [i] contiene la posición en SAw del sufijo w[i..|w|].3 Entonces LCPw[SA−1w [i]]
es la longitud del mayor prefijo común entre la cadena w[i..|w|] y su predecesor lexicográfico, es
decir, la cadena inmediatamente anterior a esta en el arreglo de sufijos. Denotemos w[i..|w|] con wi
y a su predecesor lexicográfico como wj , de manera que wj = w[j..|w|].
Tenemos dos casos, lcp(wi, wj) = 0. En este caso, la propiedad se cumple, pues lcp(a, b) > −1
para todas las cadenas a y b.
El segundo caso ocurre cuando lcp(wi, wj) ≥ 1. Entonces sabemos que wi y wj empiezan con
el mismo carácter, digamos c. Es decir, wi = cwi+1 y wj = cwj+1. Y como wj < wi, tenemos que
wj+1 < wi+1.
Sea wk el predecesor lexicográfico de wi+1. Entonces LCPw[SA
−1
w [i+ 1]] = lcp(wi+1, wk).
Por la propiedad 1, sabemos que lcp(wi+1, wk) ≥ lcp(wi+1, wj+1). Pero lcp(wi+1, wj+1) =
lcp(wi, wj)−1. Por lo tanto LCPw[SA−1w [i+1]] = lcp(wi+1, wk) ≥ lcp(wi, wj)−1 = LCPw[SA−1w [i]]−
1, como queŕıamos demostrar.
Utilizando la propiedad 2, podemos derivar un algoritmo muy sencillo para calcular el arreglo
LCP .
2En estas desigualdades utilizamos el orden lexicográfico.
3Para evitarnos tecnicismos innecesarios, diremos que los ı́ndices de nuestros arreglos van desde 1 hasta n, con n
la longitud del arreglo, aunque esto no es cierto en Java.
3.3. CONSTRUCCIÓN DE ARREGLO LCP 31
El algoritmo empieza por calcular LCPw[SA
−1
w [1]] manualmente (recorriendo w1 y a su predece-
sor lexicográfico) y a partir de ah́ı, va incrementando un contador i y calculando LCPw[SA
−1
w [i+1]]
utilizando la propiedad 2; es decir que no tenemos que revisar los primeros LCPw[SA
−1
w [i]] − 1
caracteres de las cadenas para sacar su lcp.
El algoritmo termina cuando hayamos calculado LCPw[SA
−1
w [|w|]]. Además, el algoritmo no se
atora; todas las subcadenas de w tienen predecesor lexicográfico debido a que estamos utilizando el
carácter especial de terminado y este tiene el menor peso lexicográfico por convención.
Calcular el arreglo LCPw de esta manera toma tiempo lineal. Más adelante explicaré por qué
pasa esto. Pero primero, me gustaŕıa que veamos el código del algoritmo.
3.3.1. Código
El siguiente método obtiene el arreglo LCP . Nuevamente tendremos otro método singleton
getLCP() que será el que utilicemos para obtener el arreglo LCP . Por esto mismo, el método a
continuación es privado:
private int[] lcp(){
List<Integer> sa = this.getSuffixArray(); /* Arreglo de sufijos. */int[] rev = this.getReversedSuffixArray(); /* Arreglo de sufijos invertido */
int longest = 0; /* El lcp de los sufijos que están siendo analizados */
int[] arreglolcp = new int[sa.size()]; /* El arreglo que vamos a regresa. */
arreglolcp[0] = -1; /* La primera posición vale -1 pues el sufijo no
* tiene predecesor lexicográfico */
for(int i = 0; i < cadena.length()-1; i++){
int pos = rev[i] - 1; /* Posición en SA del sufijo que empieza en el
* i-ésimo carácter. */
int pred = sa.get(pos - 1); /* Predecesor lexicográfico del sufijo. */
while(i+longest < cadena.length() && (pred - 1)+longest < cadena.length() &&
cadena.charAt(i+longest) == cadena.charAt((pred-1)+longest))
longest++;
arreglolcp[pos] = longest;
if(longest > 0)
longest--;
}
return arreglolcp;
}
Teniendo este código, podemos calcular la complejidad del algoritmo.
El cuerpo del for se ejecuta O(|cadena|) veces. Dentro del for, todas las operaciones toman
tiempo constante excepto quizás el while. Cada vez que se ejecuta este while, longest crece en 1.
longest empieza valiendo 0, no puede crecer más que la longitud de la cadena, y se decrementa a
lo más O(|cadena|) veces, por lo que podemos concluir que el while se ejecuta O(|cadena|) veces
en total. Por lo tanto, el algoritmo tiene complejidad O(|cadena|).
32 CAPÍTULO 3. CONSTRUCCIÓN DE ESTRUCTURAS AUXILIARES
3.4. Cálculo de consultas de rango mı́nimo
Como mencioné en la sección de preliminares, una consulta de rango mı́nimo es una operación
que toma dos ı́ndices en un arreglo, x e y, y nos regresa el ı́ndice con el menor elemento en el
intervalo [x, y].
Para poder hacer consultas de manera rápida, vamos a realizar un preprocesamiento. Lo ideal
es optimizar tanto el tiempo de preprocesamiento como el tiempo por consulta individual.
Como mencioné anteriormente, es posible realizar consultas en tiempo O(1) tras un preprocesa-
miento de tiempo lineal, utilizando memoria auxiliar de tamaño lineal. Sin embargo, este algoritmo
implica una transformación muy elaborada del arreglo que considero fuera del alcance de este tra-
bajo.
Por esto, decid́ı implementar las consultas de rango mı́nimo mediante un algoritmo que toma
tiempo O(n log n) en preprocesamiento, donde n es el tamaño del arreglo. Las consultas siguen
siendo en tiempo O(1) y utilizamos un arreglo auxiliar de tamaño O(n log n).
Aśı, perdemos un poco de tiempo en preprocesamiento y un poco de espacio, pero no demasiado,
y podemos seguir realizando cada consulta individual en tiempo constante. A cambio, obtenemos
un algoritmo que es muy sencillo tanto de entender como de programar.
En este algoritmo, los ı́ndices van
El algoritmo hace lo siguiente. Creamos una tabla con filas de 0 a n−1 y columnas de 0 a dlog ne,
donde n es el tamaño del arreglo original. En la posición (i, j) de nuestra tabla, guardamos el ı́ndice
del mı́nimo en el intervalo [i, i + 2j ]. Es decir, que en cada posición de nuestra tabla guardaremos
el mı́nimo de un intervalo de tamaño potencia de 2. Por esto, la tabla tiene O(n log n) entradas.
Ahora, para llenar la tabla en tiempo O(n log n) utilizamos programación dinámica. Para todos
los intervalos de longitud 1 (los de la forma (i, 0)), su valor es i. Para el resto, utilizamos la siguiente
regla: el mı́nimo del intervalo (i, j) es el menor de los mı́nimos de los intervalos (i, j − 1) e (i +
2j−1, j − 1). En otras palabras, el mı́nimo de un bloque de tamaño 2j es el menor de los mı́nimos
de los dos bloques de tamaño 2j−1 que lo conforman.
Una vez llenada la tabla, podemos obtener el mı́nimo para dos ı́ndices arbitrarios (a, b). Sea
k = blog(b− a)c. Entonces el mı́nimo del intervalo (a, b) es el menor de los mı́nimos de los intervalos
[a, a + 2k − 1] y [b − 2k + 1, b], es decir la menor de las entradas (a, k) y (j − 2k + 1, k) en nuestra
tabla. Esta operación toma tiempo O(1).
3.4.1. Código
El código para realizar consultas de rango mı́nimo es sencillo. Utilicé una clase CRM que almacena
tanto el arreglo original como el arreglo para realizar las consultas. Su constructor es el siguiente:
public CRM(int[] arreglo){
this.arreglo = arreglo;
this.query = new
Integer[arreglo.length][(int)(Math.log(arreglo.length)/Math.log(2))+1];
}
3.4. CÁLCULO DE CONSULTAS DE RANGO MÍNIMO 33
El código para realizar una consulta es el siguiente:
public int consulta(int i, int d){
if(i == d)
return i;
if(i > d)
return consulta(d, i);
else{
int k = (int)(Math.log(d-i)/Math.log(2)); /* Tama~no de bloque a revisar */
int indice1 = getMin(i, k); /* Índice del bloque izquierdo */
int indice2 = getMin((int)(d-Math.pow(2, k)+1), k); /* Índice del bloque derecho
*/
int valor1 = arreglo[indice1]; /* Valor del bloque izquierdo */
int valor2 = arreglo[indice2]; /* Valor del bloque derecho */
return valor1 < valor2 ? indice1 : indice2;
}
}
Donde el método getMin(a, b) nos regresa la posición (a, b) de la tabla de consultas. Utilicé este
método para realizar el preprocesamiento conforme sea necesario. Esto nos ayuda si solo queremos
realizar un par de consultas.
El código del método getMin es el siguiente:
public int getMin(int i, int k){
if(query[i][k] == null){
if(k == 0)
query[i][k] = i;
else{
int indice1 = getMin(i, k-1); /* Índice del mı́nimo del lado izquierdo */
int potencia = (int)Math.pow(2, k-1); /* 2^k-1 */
int indice2 = i + potencia >= arreglo.length ? indice1 : getMin(i+potencia,
k-1); /* Índice del mı́nimo del lado derecho */
query[i][k] = arreglo[indice1] <= arreglo[indice2] ? indice1 : indice2;
}
}
return query[i][k];
}
34 CAPÍTULO 3. CONSTRUCCIÓN DE ESTRUCTURAS AUXILIARES
Caṕıtulo 4
Reconocimiento de SAGP
Siguiendo la visión de los autores del art́ıculo original, vamos a considerar únicamente paĺındro-
mos con brecha en la mitad izquierda y sin carácter a la mitad (es decir, la cadena c a la mitad del
paĺındromo siempre será ε). Los algoritmos para los demás casos son análogos.
Sea p = wbuuRwR un SAGP . El pivote de p es la posición i que está entre u y uR.
Podemos abreviar un SAGP s = wbuuRwR con una 4-tupla (i, |w|, |b|, |u|), donde i es el ı́ndice
del pivote de s en la cadena T en la que se encuentra.
Por ejemplo, para la cadena baaabaabaacbaabaabac, el SAGP baaab se representa mediante la
4-tupla (3, 1, 1, 1) y el SAGP abaacbaabaaba se representa con la 4-tupla (13, 4, 1, 2).
Definimos la longitud de brazo, longb(p) como |wu|.
Sea T una cadena que representa un texto sobre el que buscamos presencias de SAGP . Decimos
que para un pivote 1 ≤ i ≤ |T | − 1, el SAGP maximal centrado en i es una cadena x tal que:
1. x es SAGP
2. i es el pivote de x.
3. Para toda y tal que cumple 1 y 2, longb(x) ≥ longb(y).
Además, decimos que un SAGP x es maximal canónico para un pivote i si x es un SAGP
maximal centrado en i y para todo SAGP y maximal centrado en i, si x = w1b1u1u
R
1 w
R
1 e y =
w2b2u2u
R
2 w
R
2 , se cumple |u1| ≥ |u2|.
Denotamos con SAGP (T ) al conjunto de todos los paĺındromos que son maximales canónicos
para cada pivote i en T . En este trabajo, nos interesa obtener SAGP (T ) para algún texto T .
Para una posición i en T , se dice que es de tipo 1 si existe un SAGP wbuuRwR tal que uuR es
el paĺındromo maximal centrado en i. Es decir que para todo otro paĺındromo vvR centrado en i,
|u| ≥ |v|. Todas las posiciones que no son de tipo 1 se dicen de tipo 2.
Por ejemplo, si T = baaaccbbccca, la posición 5 es de tipo 1, pues el paĺındromo maximal centrado
en ella es cc y hay un SAGP con u = c, es decir baaaccb. En cambio, la posición 7 es de tipo 2,
pues el paĺındromo maximal centrado en 7 es ccbbcc pero este no forma parte de ningún SAGP .
35
36 CAPÍTULO 4. RECONOCIMIENTO DE SAGP
En particular, las posiciones que no son pivote para ningún SAGP son consideradas de tipo 2.
Sean SAGP1(T ) y SAGP2(T ) los conjuntos de paĺındromos maximales canónicos para posiciones
de tipo 1 y tipo 2 respectivamente. Como las posiciones forman una partición de los ı́ndices deT ,
SAGP1(T ) ∪ SAGP2(T ) = SAGP (T ) y SAGP1(T ) ∩ SAGP2(T ) = ∅.
Antes de presentar los algoritmos para calcular SAGP (T ), debemos presentar las siguientes
propiedades:
4.1. Propiedades
Lema 1. Sea T una cadena. Sea i una posición de tipo 1 en T y s un SAGP de la forma wbuuRwR
con pivote en i. Si T = t1wbuu
RwRt2, donde b es de la forma b
′α, con α un carácter y b′ una
cadena potencialmente vaćıa, entonces s es maximal canónico si y solo si se cumplen las siguientes
propiedades:
1. uuR es el máximo paĺındromo centrado en i.
2. wR es el mayor prefijo de wRt2 tal que w aparece al menos una vez en t1wb
′.
Demostración.
⇒) Tenemos que s es un SAGP maximal canónico. Supongamos que la propiedad 1 no se
cumple. Entonces existe otro paĺındromo mayor vuuRvR centrado en i. Como sabemos que i es una
posición de tipo 1, esto implica que existe un SAGP w2b2vuu
RvRwR con pivote en i. Pero este
paĺındromo tiene longitud de brecha mayor a |wu|. Por lo tanto, s no puede ser maximal canónico,
lo cual es una contradicción.
Ahora, para probar la propiedad 2, procedamos nuevamente por contradicción. Es decir, supon-
gamos que existe otra cadena más grande, xR, que es prefijo de wRt2 y que cumple que x aparece
al menos una vez en t1wb
′.
Entonces t1wb
′ = m1xm2 y w
Rt2 = x
Rt3. Entonces tenemos una cadena s
′ = xm2αuu
RxR que
es SAGP , ya que m2α > 0. Además longb(s
′) > longb(s). Por lo tanto, s no es maximal canónico,
lo que es una contradicción.
⇐) Queremos probar que s es maximal canónico. Esto significa que para todo s′ = w′b′u′u′Rw′R
SAGP con pivote en i, |w′u′| ≤ |wu| y |u′u′R| ≤ |uuR|.
La segunda condición se cumple por 1.
Para probar la primera condición supongamos que existe otro SAGP , s′ = w′b′u′u′Rw′R tal
que |w′u′| > |wu|. Como sabemos que |u| > |u′| por la segunda condición, entonces es necesario
que |w′| > |w|. Tenemos entonces que w′R es un prefijo de wRt2 que necesariamente aparece en
t1wb
′, pues hay un SAGP con pivote en i que lo contiene. Esto contradice 2, por lo que la primera
condición también debe cumplirse.
4.2. ALGORITMO 37
Lema 2. Sea i una posición en T y uuR el mayor paĺındromo centrado en i. Entonces, la posición
i es de tipo 1 si y solo si el carácter T [i+ |u|] aparece al menos una vez en T [1..i− |u| − 1].
Demostración.
⇒) Tenemos que la posición i es de tipo 1. Esto significa que existe un SAGP , s = wbuuRwR
con pivote en i. Como w no puede ser vaćıa, entonces T [i + |u|] = wR[1] y como w aparece en
T [1..i−|u|−1], entonces en particular wR[1] también aparece. Y esto es lo que queŕıamos demostrar.
⇐) Sea c el carácter T [i+ |u|]. Como c aparece en T [1..i−|u|− 1], existe un SAGP cbuuRc, con
|b| ≥ 1. Este SAGP tiene pivote en i y contiene al mayor paĺındromo centrado en i. Por lo tanto
podemos decir que i es una posición de tipo 1.
4.2. Algoritmo
El algoritmo para calcular SAGP (T ) se basa en la propiedad de que SAGP1(T ) y SAGP2(T )
forman una partición de SAGP (T ). Lo que vamos a hacer es calcular SAGP1(T ) y SAGP2(T ) por
separado.
Para esto, primero vamos a decidir, para cada posición de T si es de tipo 1 o de tipo 2, utilizando
el lema 2. Es decir, vamos a fijarnos si el carácter T [i+|u|] está en T [1..i−|u|−1]. Esto auxiliándonos
con el arreglo Pals, que como vimos al inicio, contiene la mitad de la longitud del mayor paĺındromo
centrado en i.
Afortundamente, el arreglo Pals(T ) puede construirse en tiempo O(|T |) utilizando el algoritmo
propuesto por Glenn Manacher en [6].
Una vez que hemos clasificado las posiciones como de tipo 1 y tipo 2, solo hace falta calcular
SAGP1(T ) y SAGP2(T ) por separado. Esto se puede hacer de varias formas, de las cuales hablare-
mos más adelante.
4.2.1. Código
Hice una clase SAGP, para la cual el constructor clasifica las posiciones en SAGP1 y SAGP2, y
crea los arreglos necesarios para ejecutar el algoritmo en general. Más adelante, mostraré el código
que obtiene espećıficamente los SAGP de tipo 1 y tipo 2 por separado.
El constructor mencionado es el siguiente:
public SAGP(String texto){
this.t = texto;
this.sagp = new ArrayList<>(texto.length());
while(sagp.size() < texto.length()) sagp.add(null); /* Incrementamos el tama~no de
nuestra lista con nulos para poder usar insert. */
/* Algoritmo para calcular SAGP(T): */
pals = StringUtil.pals(t);
38 CAPÍTULO 4. RECONOCIMIENTO DE SAGP
char c; /* El carácter actual */
nextPos = new Integer[texto.length()]; /* Arreglo con la siguiente posición en la que
aparece el carácter de cada ı́ndice */
int tamano = 256 < texto.length() ? 256 : texto.length(); /* Tama~no del alfabeto */
lMost = new Hashtable<>(tamano); /* Diccionario con la posición más a la izquierda de
cada carácter en el texto */
tipo1 = new LinkedList<>();
tipo2 = new LinkedList<>();
/* Llenamos arreglos necesarios para el algoritmo */
for(int i = texto.length()-1; i >= 0; --i){/* Solo vamos a clasificar pivotes entre 1
y length-1 */
c = texto.charAt(i);
nextPos[i] = lMost.get(c);
lMost.put(c, i);
}
/* Clasificamos posiciones de acuerdo a su tipo (1 o 2). */
for(int i = 1; i < texto.length(); ++i){
if(pals[i] > 0 && texto.length() > i + pals[i] && lMost.get(texto.charAt(i +
pals[i])) < i - pals[i])
tipo1.add(i);
else
tipo2.add(i);
}
}
La variable sagp es una lista de listas de pares. En cada posición de la lista, guardamos una lista
con los SAGP de dicha posición. Representamos los SAGP mediante pares de enteros (aśı como
representábamos las subcadenas en el árbol de sufijos), utilizando la clase Par, que funciona como
envoltura de dos enteros.
El método pals obtiene el arreglo pals de una cadena. Más adelante veremos su código.
lMost contiene la posición más a la izquierda de un carácter, y se va actualizando conforme
recorremos la cadena de derecha a izquierda. Este diccionario se utiliza para saber si el carácter
T [i+ |u|] de la cadena T está en T [1..i− |u| − 1].
nextPos[i] nos dice la siguiente posición del carácter en la i-ésima posición de una cadena. Por
ejemplo, para la cadena abba, nextPos[0] = 3, nextPos[1] = 2 y nextPos[3] = nextPos[4] = null.
Es importante usar Integer en este arreglo para tener acceso a valores nulos.
El arreglo nextPos se utilizará más adelante, pero es conveniente calcularlo en este recorrido de
la cadena.
4.3. Cálculo de Pals
Para calcular Pals(T ), utilizaremos el algoritmo de Manacher. Este algoritmo toma tiempo
O(|T |) y se basa en el principio de que, si se tiene un paĺındromo que tiene un subpaĺındromo con
centro en su mitad izquierda, entonces la mitad derecha debe contener un subpaĺındromo igual pero
reflejado.
4.3. CÁLCULO DE PALS 39
El algoritmo calcula las longitudes máximas de los paĺındromos en cada posición posible de la
cadena, donde una posición es el espacio entre dos caracteres.
Para poder utilizar la propiedad de reflejo mecionada anteriormente, tendremos a lo largo del
algoritmo un paĺındromo “grande” llamado actual sobre el cual utilizaremos las longitudes de
paĺındromos de la mitad izquierda para calcular las de la mitad derecha.
En cada posición de T , calcularemos la longitud del mayor paĺındromo centrado en ella y la
guardaremos en pals.
El algoritmo utiliza tres variables: centro, der, e i. El ı́ndice i itera sobre las posiciones entre
los caracteres de la cadena; centro y der son las posiciones del centro y el extremo derecho del
paĺındromo actual respectivamente. Notemos que teniendo el extremo derecho, no es necesario
guardar el extremo izquierdo de dicho paĺındromo.
Inicialmente, centro y der se declaran en 0 (pues al principio no hemos encontrado ningún
paĺındromo).
Haremos |T | − 1 iteraciones.
En cada iteración, primero revisamos si i se encuentra dentro del paĺındromo actual. Para esto,
basta con que i sea menor al extremo derecho de este.
Si no es aśı, entonces tenemos que revisar si i es centro de un paĺındromo de forma manual. Para
esto, hacemos lo que se llama una expansión, que consisteen comparar caracteres a ambos lados
de i hasta que estos dejen de ser iguales. Con ello, obtenemos la longitud del máximo paĺındromo
centrado en i.
Si i está dentro del paĺındromo actual, entonces podemos reutilizar algo de información. Calcu-
lamos el reflejo de i y sacamos de este su longitud respectiva en el arreglo pals, siempre y cuando se
cumpla la condición de que i+ pals[reflejo(i)] no se salga del paĺındromo actual, es decir, que no
sea mayor a der. Esto porque solo podemos reutilizar información dentro del paĺındromo actual.
Si i + pals[reflejo(i)] se sale de actual, entonces no nos queda más que expandir i a partir de
der (y el reflejo de der con respecto a i), que es hasta donde podemos asegurar que la información
es reutilizable.
Finalmente, después de expandir, si el paĺındromo que obtuvimos va más allá de der, entonces
reemplazamos el paĺındromo actual por este.
4.3.1. Código
El siguiente código regresa el arreglo Pals(s) de la longitud de mitad de los paĺındromos pares
en s:
public static int[] pals(String s){
String relleno = rellena(s); /* Cadena rellenada */
int[] pals = new int[s.length()];
int centro = 0, der = 0; /* Posición del centro y derecha del palı́ndromo sobre el que
estamos parados */
for(int i = 1; i < s.length(); ++i){
int espejo = 2*centro - i; /* Reflejamos i con respecto al centro del palı́ndromo
40 CAPÍTULO 4. RECONOCIMIENTO DE SAGP
actual. */
if(i < der)
pals[i] = Math.min(der -i, pals[espejo]);
while(relleno.charAt(pals[i]+i+1) == relleno.charAt(i - pals[i])) /* Expandemos
el palı́ndromo carácter a carácter. */
pals[i]++;
if(pals[i] > 0 && i + pals[i] - 1 > der){ /* Actualizamos el palı́ndromo actual */
centro = i;
der = i + pals[i] -1;
}
}
return pals;
}
Algo a notar es que cuando i < der se cumple, le asignamos a pals[i] el mı́nimo de der − i y
pals[espejo]. El código está hecho de esta forma para ahorrar ĺıneas, pero en realidad, en el caso
de que pals[espejo] < der − i, sabemos que el valor de pals[i] será exactamente pals[espejo]. Sin
embargo, en el código realizamos la expansión, pues toma tiempo constante y mejora la legibilidad.
El método rellena simplemente pega un carácter especial al principio y final de la cadena para
evitar que las comparaciones dentro del while se salgan de rango.
4.3.2. Complejidad
A primera vista, no es tan fácil ver por qué el algoritmo de Manacher toma tiempo lineal.
El método rellena toma tiempo constante y el ciclo for dentro del método que calcula pals se
ejecuta un número lineal de veces. Sin embargo, dentro de este ciclo tenemos otro ciclo que también
puede ejecutarse un número lineal de veces, el ciclo que expande carácter por carácter. Aqúı hay
que ver una invariante.
Cada vez que iteramos, ocurre una de dos cosas: o podemos copiar la longitud del paĺındromo
reflejado o tenemos que expandir; este segundo caso ocurre cuando el paĺındromo del reflejo se sale
de nuestro paĺındromo principal.
En el primer caso, como solo hay que copiar la longitud del paĺındromo; la operación toma
tiempo constante.
El segundo caso es más interesante. Copiamos la longitud hasta el ĺımite del lado derecho y
expandimos a partir de ah́ı. A su vez, esto nos lleva a dos casos. Si no podemos expandir más
entonces gastamos O(1) pasos y el algoritmo continua, leyendo el siguiente carácter. Si podemos
expandir más del extremo derecho, entonces nuestro paĺındromo principal cambia, lo cuál a su vez
mueve el extremo derecho a la derecha tantas veces como expansiones hagamos. Como el extremo
derecho solo puede moverse O(|T |) veces en total, el total de las expansiones no puede pasar de
O(|T |) (independientemente de que las expansiones se hagan dentro de un ciclo).
Por esto el algoritmo toma:
O(|T |) (número total de expansiones) +O(|T |) (iteraciones) +O(1) (relleno de la cadena) =
4.4. CÁLCULO DE SAGP1(T ) 41
O(|T |).
4.4. Cálculo de SAGP1(T )
Una vez que tenemos divididas las posiciones de tipo 1 y tipo 2, y tenemos el arreglo Pals,
debemos calcular, por separado, SAGP1(T ) y SAGP2(T ).
El art́ıculo original sobre el que se basa este trabajo lista varias formas de calcular SAGP1(T ).
Vamos a mostrar la implementación de cada una de ellas.
4.4.1. Algoritmo ingenuo
Como su nombre lo sugiere, el algoritmo ingenuo es el más intuitivo de todos. Sin embargo, es
también el de mayor complejidad computacional.
Sea i la posición para la cual buscamos encontrar el SAGP maximal canónico. Como i es de tipo
1, entonces sabemos que uuR es el paĺındromo máximo centrado en i, por lo cual podemos utilizar
Pals(T ) para conocer |u|.
Ahora solo nos falta encontrar w y la brecha del SAGP . Sabemos que la longitud de la brecha
debe estar entre 1 e i−|u|−1. Entonces, la idea es probar todas las brechas posibles hasta encontrar
la w más grande.
Es decir, para cada brecha b, tenemos que calcular la longitud del máximo prefijo común entre
T [1..i−pals[i]−|b|]R y T [i+pals[i]+1..|T |]. O dicho de otra forma, tenemos que calcular lcp(T [1..i−
pals[i]− |b|]R, T [i+ pals[i] + 1..|T |]). Para esto, utilizaremos el arreglo LCP de la cadena T$TR#
y la siguiente propiedad del arreglo LCP :
Propiedad 3. Sea T una cadena. Entonces, si i < j, lcp(SAT [i], SAT [j]) = min(LCPT [i +
1], LCPT [i+ 2], ..., LCPT [j]).
Demostración.
Primero, observemos que lcp(SAT [j−1], SAT [j]) ≥ lcp(SAT [j−2], SAT [j]) ≥ ... ≥ lcp(SAT [i], SAT [j]).
Si no fuera aśı, tendŕıamos que para k > n, lcp(SAT [n], SAT [j]) > lcp(SAT [k], SAT [j]), lo cual no
puede ser porque SAT [k] es lexicográficamente más cercano a SAT [j] que SAT [n].
Además, sabemos que para todo w < j−1, lcp(SAT [w], SAT [j]) ≤ lcp(SAT [w], SAT [w+1]). De
nuevo, esto es debido a que SAT [w + 1] es lexicográficamente más cercana a SAT [w] que SAT [j].
Entonces, juntando las dos desigualdades, tenemos que lcp(SAT [w], SAT [w + 1]) ≥
lcp(SAT [i], SAT [j]), para todo i ≤ w ≤ j − 1. Es decir, LCPT [w] ≥ lcp(SAT [i], SAT [j]) para todo
i ≤ w ≤ j − 1. Por lo que lcp(SAT [i], SAT [j]) ≤ min(LCPT [i+ 1], LCPT [i+ 2], ..., LCPT [j]).
Ahora, veamos que lcp(SAT [i], SAT [j]) ≮ min(LCPT [i+1], LCPT [i+2], ..., LCPT [j]). Sabemos
que lcp(SAT [i], SAT [j]) = y, con y ≥ 0. Es decir, SAT [i] = a1a2...ayα y SAT [j] = a1a2...ayβ, con
ai caracteres y α y β cadenas tales que |α| ≥ 0 y |β| > 0.
Ahora, supongamos que y < min(LCPT [i+ 1], LCPT [i+ 2], ..., LCPT [j]). Sea k el ı́ndice para el
cual LCPT [k] = min(LCPT [i+1], LCPT [i+1], ..., LCPT [j]). Entonces tenemos que LCPT [k] ≥ y+1.
42 CAPÍTULO 4. RECONOCIMIENTO DE SAGP
Como además sabemos que LCPT [i+1], LCPT [i+2], ..., LCPT [k] también son mayores o iguales
a y+ 1, entonces SAT [i] tiene al menos y+ 1 caracteres de prefijo en común con SAT [i+ 1], y como
este tiene al menos y + 1 caracteres de prefijo en común con SAT [i + 2], entonces también SAT [i]
y SAT [i + 2] tienen y + 1 caracteres de prefijo en común. Siguiendo este razonamiento, SAT [i] y
SAT [k] tienen y + 1 caracteres en común.
De manera similar, SAT [j] y SAT [j − 1] tienen al menos y + 1 caracteres de prefijo común, y
siguiendo el mismo procedimiento de arriba, podemos mostrar que SAT [j] y SAT [k] tienen y + 1
caracteres de prefijo en común.
Entonces los primeros y + 1 caracteres de SAT [i], SAT [j] y SAT [k] son iguales. Lo cual es una
contradicción, pues hab́ıamos dicho que lcp(SAT [i], SAT [j]) = y.
Por lo tanto, lcp(SAT [i], SAT [j]) = min(LCPT [i+ 1], LCPT [i+ 2], ..., LCPT [j])
Un corolario de esta propiedad es que podemos obtener lcp(T [1..i−pals[i]−|b|]R, T [i+pals[i] +
1..|T |]) sacando el mı́nimo del arreglo LCPT$TR# entre los sufijos correspondientes a estas cadenas.
Para esto, vamos a utilizar una CRM (mencionada en la sección 2), lo cual nos permite obtener
el lcp en tiempo constante tras un preprocesamiento lineal sobre el tamaño del arreglo LCP .
En resumen, el algoritmo consiste de los siguientes pasos:
Recorrer las posiciones de tipo 1.
Para cada una de estas posiciones, recorrer