Tesis Doctorado
Autoíndices comprimidos para texto basados en lempel-ziv
Autor
Navarro-Badino, Gonzalo
Universidad de Chile
Institución
Resumen
Debido a las grandes colecciones de texto disponibles hoy en día, el problema de búsqueda en
texto es común en diversas aplicaciones, las que necesitan proveer acceso eficiente a esas
colecciones. Los índices clásicos para texto requieren demasiado espacio (además de almacenar
el texto), y entonces podrían no caber en memoria principal, aún para textos de tamaño moderado
que sí caben. La tendencia actual en búsqueda en texto indexado es la de los autoindices
comprimidos, los cuales reemplazan el texto con una representación que requiere espacio
proporcional al del texto comprimido y proveen acceso indexado al texto.
Los autoíndices comprimidos basados en arreglos de sufijos son los más conocidos en la
literatura. Existen, sin embargo, otros tipos de autoíndices que han recibido menos atención, a
pesar de su eficiencia. En esta tesis realizamos un estudio de los autoíndices comprimidos
basados en el algoritmo de compresión Lempel-Ziv (LZ-índices para abreviar), contribuyendo
con nuevos desarrollos. Basamos nuestros estudios en el LZ-índice de Navarro (o simplemente
LZ-índice). Previo a nuestro trabajo, los LZ-índices eran una alternativa atractiva, aunque con
algunas deficiencias: eran usualmente más grandes que otros esquemas existentes, no permitían
compromisos entre espacio y tiempo de búsqueda (para ajustarse a la memoria disponible),
requerían demasiado espacio de construcción, y no funcionaban eficientemente en memoria
secundaria (para textos muy grandes). Contribuimos a aliviar todas esas deficiencias.
Nuestra primera contribución es un enfoque práctico para reducir el espacio del LZ-índice,
alcanzando hasta dos tercios de su espacio, y manteniendo sus buenas cualidades. Aunque
nuestros índices sólo garantizan buen tiempo promedio de búsqueda, son las alternativas más
eficientes para las operaciones claves de extraer subcadenas del texto y mostrar los contextos de
las ocurrencias, suponiendo que disponemos del espacio que requieren nuestros índices.
Luego estudiamos maneras de reducir el espacio que requiere el LZ-índice, esta vez con garantías
de peor caso en tiempo de búsqueda, obteniendo los LZ-indices más pequeños que existen, a la
vez que mejoramos el costo de búsqueda original. Exploramos diversas maneras para lograr
nuestro objetivo, y obtenemos una familia completa de LZ-índíces, con diferentes requerimientos
de espacio y tiempos de búsqueda. De esta manera, somos capaces de competir en casos en los
que el LZ-índice original no podía hacerlo, debido a limitaciones de espacio.
Estudiamos luego la construcción con poco espacio de nuestra familia de LZ-índices. Concluimos
que nuestros LZ-índices pueden ser construidos sin espacio extra sobre el del índice final, lo que
mejora su aplicabilidad ya que si disponemos del espacio para almacenar el índice final, seremos
capaces de construirlo sin acceder a la memoria secundaria. En la práctica, nuestros LZ-índices
son los autoíndices más rápidos en construirse con espacio proporcional al del texto comprimido.
Finalmente, estudiamos cómo adaptar el LZ-índice en memoria secundaria. Obtenemos el índice
para texto en memoria secundaria más pequeño que existe, siendo a la vez muy competitivos en
cantidad de accesos a disco.