New compression codes for text databases

Abstract

Las bases de datos textuales están creciendo en los últimos años debido a la proliferación de las biliotecas digitales, bases de datos documentales, y sobre todo por el gran crecimiento continuado que la Web está manteniendo, La comresión surge como una solución ideal que permite reducir espacio de almacenamiento y las operaciones de E/S, con el consiguiente beneficio para la transmisión de información a través de una red. Si bien la compresión nace en la primera parte del siglo XX, en la pasada décda aparecen nuevas técnicas de compresión basadas en Huffman, que usan las palabrad con los símbolos a comprimir. Estas nuevas técnicas no sólo mejoran la capacidad de compresión de otros métodos muy conocidos (p.ej: Ziv-Lempel), sino que además permiten realizar búsquedas dentro del texto comprimido, sin necesidad de descomprimirlo, de forma mucho más rápida que cuando dichas búsquedas se realizan sobre el texto plano. Siguiendo con la idea de la compresión basada en palabras, en esta tesis se desarrollan cuatro nuevas técnicas de compresión que dan comienzo a una nueva familia de compresores basados en la utilización de códigos densos. De estas cuatro técnicas, dos son semiestáticas y dos son dinámicas. Sus nombres son: End-Tagged Dense Code, (s,c)-Dense Code, Dynamic End-Tagged Dense Code y Dynamic (s,c)-Dense Code. Además también se ha desarrollado, por primera vez, un compresor dinámico orientado a bytes y basado en palabras, que usa Huffman como esquema de codificación. Los resultados experimentales obtenidos al comparar nuestros compresores contra corpus reales han demostrado que estos suponen una aportación relevante en el campo de la compresión, tanto para los sistemas orientados a Text Retrieval, como en sistemas orientados a la transmisión de datos, ya que nuestros compresores comprimen más y más eficientemente que muchos de los compresores actualmente en uso (gzip, compress, etc).