1. No category

Indexando Bases de Datos Textuales: Una Representación
Compacta del Trie de Sufijos
Darı́o Ruano, Norma Herrera
Departamento de Informática
Universidad Nacional de San Luis, Argentina
{dmruano, nherrera}@unsl.edu.ar
Abstract
Mientras que en bases de datos tradicionales los ı́ndices
ocupan menos espacio que el conjunto de datos indexados, en bases de datos de texto el ı́ndice ocupa más
espacio que el texto en sı́ mismo, pudiendo necesitar
de 4 a 20 veces el tamaño del mismo. Un trie de sufijos es un ı́ndice para bases de datos de texto que necesita en espacio 10 veces el tamaño del texto indexado.
En este trabajo presentamos una representación compacta del mismo que permite ahorrar hasta un 40% de
espacio manteniendo su eficiencia en búsquedas. Esta
representación tiene la ventaja además de permitir un
posterior proceso de paginado.
Palabras claves: Bases de Datos de Texto, Índices,
Trie, Memoria Secundaria.
1
Introducción
La mayorı́a de los administradores de bases de datos
actuales están basados en el modelo relacional, presentado por Edgard F. Codd en 1970 [2]. Bajo el modelo
relacional, cada elemento de la base de datos puede ser
almacenado como un registro (tupla) y cada registro a
su vez dividido en campos (atributos). La mayorı́a de
las consultas que se realizan a una base de datos relacional (conocidas también como bases de datos tradicionales) se corresponden con búsquedas exactas, esto
significa obtener todos los registros cuyos campos coinciden exactamente con los campos aportados durante la
búsqueda. También se pueden realizar búsquedas por
rango sobre valores numéricos, y búsquedas de subcadenas sobre campos alfabéticos; en estos casos debe
existir una relación de orden sobre los campos consultados.
La información disponible en formato digital aumenta dı́a a dı́a su tamaño de manera exponencial. Gran
parte de esta información se representa en forma de
texto, es decir, secuencias de sı́mbolos que pueden representar no sólo lenguaje natural, sino también música,
códigos de programas, secuencias de ADN, secuencias
de proteı́nas, etc.
Debido a que no es posible organizar una colección
de textos en registros y campos, las tecnologı́as tradicionales de bases de datos para almacenamiento y
búsqueda de información no son adecuadas en este
ámbito.
Una base de datos de texto es un sistema que
mantiene una colección grande de texto y que provee
acceso rápido y seguro al mismo. Sin pérdida de generalidad, asumiremos que la base de datos de texto es
un único texto T que posiblemente se encuentra almacenado en varios archivos.
Una de las búsquedas más comunes en bases de datos
de texto es la búsqueda de un patrón: el usuario ingresa
un string P (patrón de búsqueda) y el sistema retorna
las ocurrencias del patrón P en el texto T .
Para resolver eficientemente estas búsquedas se hace
necesario construir un ı́ndice que permita acelerar el
proceso de búsqueda. Un ı́ndice debe dar soporte a dos
operaciones básicas de búsqueda de patrón:
count que consiste en contar el número de ocurrencias de P en T .
locate que consiste en ubicar todas las posiciones
de T donde P ocurre.
Mientras que en bases de datos tradicionales los
ı́ndices ocupan menos espacio que el conjunto de datos
indexados, en bases de datos de texto el ı́ndice ocupa
más espacio que el texto en sı́ mismo, pudiendo necesitar de 4 a 20 veces el tamaño del mismo [6][12].
Algunos ı́ndices reducen el espacio ocupado restringiendo el tipo de búsqueda que se pueden resolver.
Ası́, un ı́ndice orientado a palabra, permite solamente
buscar palabras completas en el texto; de esta forma si
buscamos el patrón es en el texto es importante que
estén presentes el ı́ndice no retornará la ocurrencia de
este patrón dentro de la palabras estén y presentes. Algunos ı́ndices orientados a palabras permiten también
buscar patrones que sean inicios de palabras; en el ejemplo anterior estos ı́ndices encontrarı́an las ocurrencias
de es en es y estén pero no las ocurrencias en presentes. Los ı́ndices que son capaces de encontrar todas
las ocurrencias de un patrón dentro del texto se denominan ı́ndices orientados a caracteres o full text indexes;
este tipo de ı́ndices encontrarı́a las cuatro ocurrencias
de la palabra es en el texto dado.
Otra alternativa para reducir el espacio ocupado por
el ı́ndice es buscar una representación compacta del
mismo, manteniendo las facilidades de navegación sobre la estructura. En los últimos años se han realizado
grandes avances en este ámbito Las nuevas técnicas
de compresión de ı́ndices no sólo permiten reducir su
tamaño, sino que procesan búsquedas más rápido que
la versión sin comprimir [8, 13, 16].
Un trie de sufijos es un ı́ndice que permite resolver
eficientemente las operaciones count y locate pero que
necesita en espacio 10 veces el tamaño del texto indexado. Por ejemplo, si construimos un trie de sufijos
sobre un texto de 10GB, el espacio requerido para almacenarlo será de 100GB. Por esta razón, el diseño de
técnicas de representación compactas es de interés en
este ámbito.
En este artı́culo presentamos una propuesta de representación secuencial compacta de un trie de sufijo que
permite ahorrar hast un 40% de espacio manteniendo
su eficiencia en cuanto a los tiempos de count y locate .
Cabe mencionar que este trabajo es parte de un proyecto
mayor que consiste en lograr una implementación eficiente en disco del trie de sufijos.
Lo que resta del artı́culo está organizado de la siguiente manera. En las secciones 2 y 3 presentamos
el trabajo relacionado, dando los conceptos necesarios
para comprender el artı́culo. En las secciones 4 y 5 presentamos nuestra propuesta y la evaluación experimental de la misma. Finalizamos en la sección 6 dando las
conclusiones y el trabajo futuro.
2 Trabajo Relacionado
2.1 Indexación en Bases de Datos de Texto
Dado un texto T = t1 , . . . , tn sobre un alfabeto Σ de
tamaño σ, donde tn = $ ∈
/ Σ es un sı́mbolo menor en
orden lexicográfico que cualquier otro sı́mbolo de Σ,
definimos:
sufijo de T: cualquier string de la forma Ti,n =
ti , . . . , tn con i = 1..n. .
prefijo de T: cualquier string de la forma T1,i =
t1 , . . . , ti con i = 1..n.
Cada sufijo Ti,n se identifica unı́vocamente por i; llamaremos al valor i ı́ndice del sufijo Ti,n . Un patrón
de búsqueda P = p1 . . . pm es cualquier string sobre el
alfabeto Σ.
Entre los ı́ndices más populares para búsqueda de patrones encontramos el arreglo de sufijos [12] y el trie de
sufijos [21]. Estos ı́ndices se construyen basándose en
la observación de que un patrón P ocurre en el texto si
es prefijo de algún sufijo del texto.
Un arreglo de sufijos A[1, n] es una permutación de
los números 1, 2, . . . , n tal que TA[i],n ≺ TA[i+1],n ,
donde ≺ es la relación de orden lexicográfico. Buscar un patrón P en T equivale a buscar todos los sufijos de los cuales P es prefijo, los cuales estarán en
posiciones consecutivas de A. El proceso de búsqueda
consiste entonces en dos búsquedas binarias que identifiquen el segmento del arreglo A que contiene todas las
posiciones de T donde P ocurre. La figura 1 muestra
un ejemplo de un arreglo de sufijos; en el ejemplo se ha
indicado junto con cada valor del arreglo el sufijo que
ese valor representa.
Un trie de sufijos [6] es un trie[5] construido sobre
el conjunto de todos los sufijos de T . Cada rama está
rotulada por un sı́mbolo de T y cada hoja representa un
sufijo de T . El conjunto total de sufijos se obtiene recorriendo todos los caminos posibles desde la raı́z hasta
una hoja y concatenando los rótulos de las ramas que
forman cada uno de esos caminos. En cada nodo hoja
se mantiene el ı́ndice del sufijo que esa hoja representa.
La figura 1 muestra un ejemplo de un texto y su correspondiente trie de sufijos. Notar que si recorremos los
sufijos del texto según el orden dado por las hojas (de
izquierda a derecha) obtenemos todos los sufijos ordenados lexicográficamente, es decir, el arreglo de sufijos.
Una forma de reducir el uso de espacio es reemplazar
las ramas del árbol que han degenerado en una lista,
Trie de Sufijos:
Texto:
1
a
2
b
3
c
4
c
5
a
6
b
7
c
8
a
9
$
$
a
b
c
9
Arreglo de Sufijos:
b
$
c
a
c
8
$
a
c
$
c
a $
a b c a $
$
b
3
7
$
a
c
$
a b c c a b c a $
$
b c a $
b c c a b c a $
6
$
c a $
2
4
$
9
8
5
1
6
2
7
4
3
c a b c a $
c c a b c a $
5
1
Figure 1: Un ejemplo de un arreglo de sufijos y de un trie de sufijos
para un texto dado
por una única rama y agregar a cada nodo interno la
longitud de la rama que se ha eliminado. Esta longitud
se conoce con el nombre de valor de salto. La figura
2 muestra esta modificación para el trie de la figura 1.
Esta última versión es la que utilizamos en este trabajo.
Para encontrar todas las ocurrencias de P en T , se
busca en el trie utilizando los caracteres de P para direccionar la búsqueda. La búsqueda comienza por la
raı́z y en cada paso, estando en un nodo x con valor de
salto j, avanzamos siguiendo la rama rotulada con el jésimo caracter de P . Durante este proceso se pueden
presentar tres situaciones:
contenidos en las hojas que forman la respuesta a la
consulta. Si la búsqueda es una operación count y es
exitosa, basta con contar la cantidad de hojas que forman parte de la respuesta.
• que la longitud de P sea menor que j, por lo cual
no hay caracter de P para seguir buscando en el
árbol. En este caso se compara P con una de las
hojas del subárbol con raı́z x; si esa hoja es parte
de la respuesta todas las hojas de ese subárbol lo
son, caso contrario ninguna lo es.
En bases de datos tradicionales, si construimos un
ı́ndice para una relación R la cantidad de puntos de indexación está dado por la cantidad de nuplas de R y no
por el espacio ocupado por R: si la relación ocupa k
bytes y tiene n nuplas, en el ı́ndice existirán n puntos
de indexación; notar que siempre n < k.
• que x sea una hoja del árbol y por lo tanto no tiene
un valor de salto asignado sino el ı́ndice de un sufijo. En este caso se debe comparar P con el sufijo
indicado por la hoja para saber si ese sufijo es o no
la respuesta.
2.2
Índices Comprimidos
Como ya mencionáramos en la Sección 1, el principal
problema que surge al indexar una bases de datos de
texto es el espacio ocupado por el ı́ndice.
En bases de datos de texto, cada caracter del texto
debe ser considerado dentro del ı́ndice, en consecuencia
la cantidad de puntos de indexación está dado por el
tamaño del texto: si el texto ocupa k bytes, existirán k
puntos de indexación.
Una forma de tratar con este problema es buscar una
representación
compacta del ı́ndice, manteniendo las
• que el nodo x no tenga ningún hijo rotulado con el
facilidades
de
navegación
sobre la estructura. Esto sigj-ésimo caracter de P . En este caso la búsqueda
nifica
encontrar
una
representación
que ocupe menos
fracasa.
espacio que la representación clásica, pero que perEn cada caso, si la búsqueda es una operación locate mita navegar sobre el ı́ndice sin necesidad de descomy es exitosa, hay que recuperar los ı́ndices de sufijos primirlo [3, 4, 7, 8, 11, 15, 17, 19].
0
$
a
b
a
a
6
3
a
c
1
2
7
3
b
4
Figure 2: Trie de sufijos con valores de salto.
3
A1
C 1,1 C 2,1 C 3,1 C 4,1 C 5,1
C 4,1 C 4,2 C 5,1
1
0
1
1
0
c
2
$
8
C 1,1 C 1,2 C 2,1 C 3,1 C 3,2 C 3,3
B1
c
b
$
5
1
2
1
9
C
c
Códigos de Longitud Variable de
Acceso Directo
Dentro de la temática de compresión de datos, un problema central es la asignación de códigos de longitud
variable a los sı́mbolos de alfabeto del texto que se
está comprimiendo. Los métodos de compresión estadı́sticos, como por ejemplo Huffman, asignan códigos
más corto a los sı́mbolos más frecuentes y códigos más
largos a los menos frecuentes. El principal problema
de estos métodos es que no permiten acceder eficientemente al i-ésimo sı́mbolo en la secuencia codificada. La
solución tı́pica a este problema implica un overhead en
tiempo y espacio que ocasiona perder parte del espacio
ganado al comprimir.
El Directly Addressable Variable-Length Code
(DAC), presentado en [1], es una técnica que permite
acceso aleatorio y eficiente a cada código en una secuencia de códigos de longitud variable.
Dada una secuencia de códigos de longitud variable
C = C1 , C2 , . . . , Ck , se divide cada código Ci en
bloques de b bits. Luego se crea un arreglo A1 conteniendo la concatenación de los primeros bloques de
cada sı́mbolo, y un mapa de bits (bitmap) B1 de k bits,
donde el i-ésimo bit está en 1 si el código Ci está formado por más de un bloque. Se continua con la creación
de un arreglo A2 conteniendo la concatenación de los
segundos bloques de cada sı́mbolo y un bitmap B2 con
1 en aquellos bits correspondientes a los códigos con
más de dos bloques. Se continua ası́ hasta alcanzar la
máxima cantidad de bloques.
La figura 3 muestra un ejemplo para una secuencia
A2
C 1,2 C 3,2 C 4,2
B2
0
A3
C 3,3
B3
0
1
0
Figure 3: Representación de una secuencia C de
códigos de longitud variable usando DAC.
C formada por 5 códigos de longitud variable, Ci,j representa el j-ésimo bloque del i-ésimo código de la secuencia.
Para acceder al código Ci de la secuencia original
primero buscamos su primer bloque en A1 [i]. Si el
i-ésimo bit de B1 está en 0, se finaliza retornando
Ci = A1 [i]. Caso contrario, continuamos buscando
el segundo bloque del código Ci en A2 [rank1 (B1 , i)],
donde rank1 (B1 , i) es la cantidad de unos en B1 [1..i].
Este proceso continúa hasta llegar al último nivel de
arreglos o hasta encontrar el bit del correspondiente
bitmap en cero.
Los autores muestran que esta técnica de compresión
logra reducciones de alrededor del 30% en el espacio
requerido para representar la secuencia.
4 Representación Compacta de un
Trie de Sufijos
La representación habitual de un trie consiste en mantener en cada nodo los punteros a sus hijos, junto con
el rótulo correspondiente a cada uno de ellos. Existen
distintas variantes de representación que consisten en
organizar estos punteros a los hijos sobre una lista secuencial, sobre una lista vinculada o sobre una tabla de
hashing [10]. Una de las propuestas de representación
que mejor desempeño tiene en memoria principal es
la de Kurtz, quien basándose en la idea de la representación sobre una lista vinculada, propuso que cada
nodo mantenga un apuntador al primer hijo y almacenar los nodos hermanos en posiciones consecutivas de
memoria. Esto permite durante una búsqueda, realizar
una búsqueda binaria sobre los rótulos para decidir por
cual hijo seguir.
La mayorı́a de las propuestas existentes mantienen
explı́citamente la forma del árbol con punteros, los que
pueden ser punteros fı́sicos (direcciones de memoria
principal) o punteros lógicos (posiciones de un arreglo).
En [18] se presenta una nueva representación de un
trie de sufijos que permite reducir el espacio necesario
para almacenar el ı́ndice, eliminando la necesidad de
mantener los punteros explı́citos a los hijos. Esta representación surge como una extensión a árboles r-arios de
la técnica presentada en [9] y tiene la ventaja de permitir
un posterior proceso de paginado para manejar eficientemente el trie de sufijos en memoria secundaria [20].
Notar que la información contenida en el trie está
compuesta por: la forma del árbol, el rótulo de cada
rama, el valor de salto de cada nodo, el grado de cada
nodo y el ı́ndice del sufijo asociado a cada hoja. En
[18] se propone representar de manera secuencial cada
una de estas componentes, manteniendo la posibilidad
de navegar eficientemente sobre el trie:
• La forma del árbol se representas utilizando la
técnica de representación de paréntesis [14]. Esta
representación consiste en realizar un barrido preorden sobre el árbol colocando un paréntesis que
abre cuando se visita por primera vez un nodo y un
paréntesis que cierra cuando se termina de visitar
todo el subárbol de ese nodo. Esta representación
utiliza un total de 2n bits para un árbol de n nodos, manteniendo las facilidades de navegación sobre el mismo [14]. La figura 4 muestra esta representación para el mismo árbol de la Figura 2.
• Para la representación de los rótulos de cada rama,
de los valores de salto de cada nodo y del grado de
cada nodo, se utilizan arreglos colocando los elementos que forman cada arreglo en el orden indicado por un barrido preorden del árbol. Esto
permite durante la navegación del árbol moverse
coordinadamente sobre todas las secuencias que
conforman la representación del mismo.
• Para la hojas también se mantiene un arreglo de
ı́ndices de sufijos, tomados en orden de izquierda
a derecha del árbol.
La figura 4 muestra esta representación para el trie de
sufijos de la Figura 2.
Para poder navegar sobre esta representación los autores se basan en el algoritmo que permite navegar sobre una representación de paréntesis [14], adaptándolo
para moverse coordinadamente sobre los 5 arreglos. Estos algoritmos necesitan realizar operaciones findclose,
excess y enclose sobre secuencias binarias [14].
En este trabajo proponemos comprimir esta representación usando códigos DAC para los arreglos que
representan la secuencia de saltos y de grados. La navegación sobre esta nueva representación sigue los lineamientos generales propuestos en [18], adaptándolo a
los códigos DAC. Esto significa que cada vez que el algoritmo necesita acceder al i-ésimo salto o al i-ésimo
grado, realizará la secuencia de operaciones rank necesarias para reconstruirlo (ver la Sección 3). Esto puede
implicar una degradación en los tiempos de resolución
de las operaciones count y locate .
5 Evaluación Experimental
Recordemos que este trabajo forma parte de un
proyecto mayor cuyo objetivo principal consiste en lograr una implementación eficiente en disco del trie de
sufijos. Esto significa que como paso posterior a la
creación del ı́ndice se realizará un paginado del mismo.
El proceso de paginación de un ı́ndice consiste en
dividir el mismo en partes, cada una de las cuales se
aloja en una página de disco. Luego el proceso de
búsqueda consiste en ir cargando en memoria principal
una parte, realizar la búsqueda en memoria principal sobre esa parte, para luego cargar la siguiente y proseguir
la búsqueda.
Cuando un ı́ndice se maneja en disco, el costo de
búsqueda queda determinado por la cantidad de accesos a disco realizadas [20]. En base a esto es muy importante tratar de reducir el tamaño del ı́ndice lo más
posible.
Denotaremos con rs a la representación del trie propuesta en [18] y con rs-DACS a la representación compacta propuesta en este trabajo.
El objetivo de la evaluación aquı́ presentada es
analizar el desempeño de rs-DACS tomando como base
de comparación rs. Se analizan dos aspectos: reducción
de espacio ocupado por el ı́ndice y tiempos de resolución de las operaciones count y locate .
Para realizar esta evaluación hemos tomado tres tipos
de texto:
DNA que contiene secuencias de ADN.
Representación de Paréntesis
( ( ) ( ( ) ( ( ) ( ) ) ) ( ( ) ( ) ) ( ( ( ) ( ) ) ( ) ) )
Rótulos
0
1
2
3
4
5
6
7
8
9
10
11
12
13
$
a
$
b
a
c
b
a
c
c
a
$
b
c
Saltos
0
1
2
3
4
5
0
1
3
2
1
2
Grado
0
1
2
3
4
5
4
2
2
2
2
2
Arreglo de Sufijos
0
1
2
3
4
5
6
7
8
9
8
5
1
6
2
7
4
3
Figure 4: Representación secuencial del trie de sufijos de la Figura 2.
texto. En el caso de DNA, se logra reducir el tamaño del
ı́ndice en un 40% aproximadamente, en todos los casos.
SOURCE que contiene códigos fuente de progra- Para SOURCE se logra reducir en un 38% y por último
mas escritos en Java y C.
para PROTEINS las reducciones de espacio están entre
el 35% y el 37% aproximadamente
Estos textos han sido tomados del sitio
Se observa que a medida que el tamaño del texto auhttp://pizzachili.dcc.uchile.cl. Este sitio ofrece una
menta la reducción de espacio también aumenta. Esto
amplia colección de ı́ndices comprimidos y de textos,
se observa en los tres tipos de texto evaluados. .
que son los habitualmente usados por la comunidad
que trabaja con ı́ndices sobre bases de datos textuales.
Para cada tipo de texto se han tomado partes de tamaño 5.2 Tiempos de Búsqueda
4, 6, 8 y 10 MB a fin de poder evaluar la incidencia
Presentamos ahora la evaluación experimental de los
del tamaño del texto sobre los resultados obtenidos.
tiempos de búsquedas. Los resultados aquı́ mostrados
Los tamaños han sido establecidos tomando en cuenta
fueron obtenidos realizando búsquedas con patrones de
que si paginamos el ı́ndice las búsquedas se realizarán
longitud 3, 5, 7, 10, 15 y 20. Utilizamos estas longisobre parte pequeñas del mismo.
tudes ya que prácticas anteriores han demostraron ser
Para ambas representaciones hemos evaluado el
representativas. Para cada longitud de patrón y tipo de
tamaño del ı́ndice y los tiempos de las operaciones
texto, se generaron lotes de 500 patrones.
count y locate . Presentamos a continuaciónlos resultados obtenidos, mostrando las gráficas que hemos con- Tiempo medio de count
siderado más relevantes.
La Figura 6 muestra los resultados obtenidos para
ambas representaciones y para los distintos tipos de
texto de tamaño 4MB. Sobre el eje x se han represen5.1 Tamaño del Índice
tado las distintas longitudes de patrones y sobre el eje y
La figura 5 muestra los resultados con los distintos tipos está representado el tiempo medio, expresado en milisede texto bajo ambas representaciones. Sobre el eje x se gundos, de realizar la operación count sobre un patrón.
han representado los distintos tamaños de texto y sobre
En el caso de DNA rs mejora el tiempo de rs-DACS
el eje y está representado el tamaño del ı́ndice obtenido. en un 1% aproximadamente según el tamaño del texto
Como puede observarse, la representación rs-DACS utilizado, excepto en patrones de longitud 15 donde rsresulta ser la mejor elección para todos los tamaños de DACS mejora a rs en un 1% aproximadamente. Para
PROTEINS que contiene secuencias de proteı́nas.
Tamaño del Texto (MB)
Tamaño del Texto (MB)
Tamaño del Texto (MB)
Figure 5: Comparación de tamaño de los ı́ndices respecto del tipo y tamaño del texto.
SOURCE rs mejora a rs-DACS en un 3% a un 5%
aproximadamente según el tamaño del texto utilizado,
excepto en patrones de longitud 5 donde rs-DACS
mejora a rs en un 3%. Para PROTEINS rs mejora a
rs-DACS en un 1% a un 2, 5% aproximadamente según
el tamaño del texto utilizado, excepto en patrones de
longitud 5 donde rs-DACS mejora a rs en un 1.5%.
Estos resultados se mantienen cuando el tamaño del
texto crece.
Para entender el por qué de estos resultados debemos
tener en cuenta que para navegar sobre rs-DACS debemos realizar operaciones rank adicionales necesarias
para obtener los datos que estan comprimidos, mientras
que en rs estas operaciones no son necesarias.
bas representaciones y para los distintos tipos de texto
de tamaño 4MB. Sobre el eje x se han representado las
distintas longitudes de patrones y sobre el eje y está representado el tiempo medio de obtener una ocurrencia,
expresado en milisegundos.
Como podemos observar tanto para texto
DNA, SOURCE y PROTEINS los resultados son
prácticamente iguales para ambas representaciones rs y
rs-DACS.
Realizar la operación locate implica realizar la
misma búsqueda que la operación count pero debemos
retornar las posiciones de todas las ocurrencias en vez
de la cantidad de éstas. Por esta razón las conclusiones
obtenidas para count se mantienen para locate, por lo
tanto sólo analizaremos los detalles que las diferencian.
Tiempo medio de locate
Devolver todas las posiciones de ocurrencia de un
La figura 7 muestra los resultados obtenidos para am- patrón en rs implica indicar el rango correspondiente a
Longitud del Patrón
Longitud del Patrón
Longitud del Patrón
Figure 6: Tiempo medio de count para textos de tamaño 4MB
las respuestas en el arreglo que mantiene los ı́ndices de
los sufijos. Como en rs-DACS sólo se aplica la técnica
de compresión DAC a los saltos y grados de rs, la operación de devolver todas las posiciones de ocurrencia
de un patrón son idénticas en ambas representaciones.
En base a esto la diferencia que existe entre las representaciones está dada por lo que ocurre con la operación
count. Como pudimos observar ateriormente la mejora
en tiempo de rs sobre rs-DACS en la operación count
no es muy significa y como la cantidad de ocurrencias
es generalmente grande las diferencias obtenidas para
locate son prácticamente nulas.
Ese mismo comportamiento se pudo observar para
texto de mayor tamaño.
6
Conclusiones y Trabajo Futuro
En este trabajo hemos abordado el estudio del trie de sufijos, centrándonos en buscar una representación com-
pacta del mismo.
Las representación propuesta rs-DACS logra mejorar
en espacio a rs , logrando reducciones de alrededor del
40% en todos los textos analizados. Cabe señalar que
rs-DACS mantiene la eficiencia en cuanto a los tiempos
de resolución de count y locate .
Con respecto al trabajo futuro, nos proponemos integrar esta nueva representación con la técnica de paginado propuesta en [18], a fin de lograr un ı́ndice comprimido en memoria secundaria.
References
[1] N. Brisaboa, S. Ladra, and G. Navarro. Directly addressable variable-length codes. In Proc.
Longitud del Patrón
Longitud del Patrón
Longitud del Patrón
Figure 7: Tiempo medio de locate para textos de 4MB.
16th International Symposium on String Processing and Information Retrieval (SPIRE), LNCS
5721, pages 122–130. Springer, 2009.
[6] G. H. Gonnet, R. Baeza-Yates, and T. Snider. New
indices for text: PAT trees and PAT arrays, pages
66–82. Prentice Hall, New Jersey, 1992.
[2] E. F. Codd. A relational model of data for large
shared data banks. Commun. ACM, 13(6):377–
387, June 1970.
[7] R. González and G. Navarro. A compressed
text index on secondary memory. In Proc. 18th
International Workshop on Combinatorial Algorithms (IWOCA), pages 80–91. College Publications, UK, 2007.
[3] P. Ferragina and G. Manzini. Indexing compressed text. J. ACM, 52(4):552–581, 2005.
[4] P. Ferragina, G. Manzini, V. Mäkinen, and G.
Navarro.
Compressed representations of sequences and full-text indexes. ACM Trans. Algorithms, 3(2):20, 2007.
[5] G. H. Gonnet and R. Baeza-Yates. Handbook of
Algorithms and Data Structures. Addison-Wesley,
1991.
[8] R. González and G. Navarro. Compressed text
indexes with fast locate. In Proc. 18th Annual
Symposium on Combinatorial Pattern Matching
(CPM), LNCS 4580, pages 216–227, 2007.
[9] N. Herrera and G. Navarro. Árboles de sufijos
comprimidos en memoria secundaria. In Proc.
XXXV Latin American Conference on Informatics
(CLEI), Pelotas, Brazil, 2009.
[10] A. Thomo M. Barsky *, U. Stege. A survey of [16] G. Navarro and V. Mäkinen. Compressed full-text
indexes. ACM Computing Surveys, 39(1):article 2,
practical algorithms for suffix tree construction in
2007.
external memory. In Software: Practice and Experience, 2010.
[17] G. Navarro and K. Sadakane. Compressed Tree
Representations. Springer, 2nd edition, 2015.
[11] V. Mäkinen and G. Navarro. Compressed Text Indexing, pages 176–178. Springer, 2008.
[18] D. Ruano and N. Herrera. Representación secuencial de un trie de sufijos. In XX Congreso Ar[12] U. Manber and G. Myers. Suffix arrays: A new
gentino de Ciencias de la Computación, Buenos
method for on-line string searches. SIAM Journal
Aires, Argentina, 2014.
of Computing, 22(5):935–948, 1993.
[13] E. Moura, G. Navarro, N. Ziviani, and R. Baeza- [19] K. Sadakane. New text indexing functionalities
of the compressed suffix arrays. J. Algorithms,
Yates. Fast and flexible word searching on compressed text. ACM Transactions on Information
48(2):294–313, 2003.
Systems (TOIS), 18(2):113–139, 2000.
[20] J. Vitter. External memory algorithms and data
[14] J. Ian Munro and Venkatesh Raman. Succinct
structures: Dealing with massive data. ACM Computing Surveys, 33(2):209–271, 2001.
representation of balanced parentheses and static
trees. SIAM J. Comput., 31(3):762–776, 2001.
[21] P. Weiner. Linear pattern matching algorithm.
In Proc. 14th IEEE Symposium Switching Theory
[15] G. Navarro. Indexing text using the ziv-lempel
and Automata Theory, pages 1–11, 1973.
trie.
Journal of Discrete Algorithms (JDA),
2(1):87–114, 2004.