New Compression Codes for Text Databases

Abstract

[Abstract] Text databases are growing in the last years due to the widespread use of digital libraries, document databases and mainly because of the continuous growing of the Web. Compression comes up as an ideal solution that permits to reduce both storage requirements and input/output operations. Therefore, it is useful when transmitting data through a network. Even though compression appeared in the first half of the 20th century, in the last decade, new Huffman-based compression techniques appeared. Those techniques use words as the symbols to be compressed. They do not only improve the compression ratio obtained by other well-known methods (e.g. Ziv-Lempel), but also allow to efficiently perform searches inside the compressed text avoiding the need for decompression before the search. As a result, those searches are much faster than searches inside plain text. Following the idea of word-based compression, in this thesis, we developed four new compression techniques that make up a new family of compressors. They are based in the utilization of dense codes. Among these four techniques, the first two ones are semi-static techniques and the others are dynamic methods. They are called: End-Tagged Dense Code, (s, c)-Dense Code, Dynamic End-Tagged Dense Code, and Dynamic (s, c)-Dense Code. Moreover, in this thesis, we have implemented a first prototype of a word-based byte-oriented dynamic Huffman compressor. This technique was developed with the aim of having a competitive technique to compare against our two dynamic methods. Our empirical results, obtained from the systematic empirical validation of our compressors in real corpora, show that our techniques become a fundamental contribution in the area of compression. Since these techniques compress more, and more efficiently than other widely used compressors (e.g. gzip, compress, etc.), they can be applied to both Text R.etrieval systems and to systems oriented to data transmission. It is remarkable that the research done in this thesis introduces a new family of compressors that is based on the use of dense codes. Even though we have only explored the beginning of this new family, the obtained results are so good that we hope that future works permit us to develop more compressors from this family.

[Resumo] As bases de datos textuais están a medrar nos últimos anos debido á proliferación de bibliotecas dixitais, bases de datos documentais, e sobre todo polo grande crecemento continuado que a Web está a manter. A compresión xurde como a solución ideal que permite reducir espazo de armacenamento e operacións de entrada/saída, co conseguinte beneficio para a transmisión de información a través dunha rede. Se ben a compresión nace na primeira parte do século XX, na pasada década aparecen novas técnicas de compresión baseadas en Huffman que usan as palabras como os símbolos a comprimir. Estas novas técnicas non só melloran a capacidade de compresión doutros métodos moi coñecidos (p.ex: Ziv-Lempel), senón que ademais permiten realizar buscas dentro do texto comprimido, sen necesidade de descomprimilo, dun xeito moito máis rápido que cando ditas buscas se fan sobre o texto plano. Seguindo coa idea da compresión baseada en palabras, nesta tese desenvolvéronse catro novas técnicas de compresión que inician unha nova familia de compresores baseados na utilización de códigos densos. Destas catro técnicas, dúas son semiestáticas e dúas son dinámicas. Os seus nomes son: End-Tagged Dense Code, (s, c)-Dense Code, Dynamic End-Tagged Dense Code e Dynamic (s, c)-Dense Code. Ademais, nesta tese implementouse por primeira vez un compresor dinámico orientado a bytes e baseado en palabras que usa Huffman como esquema de codificación. Nós desenvolvemos este compresor para termos unha técnica competitiva e baseada en Huffman coa que comparar as nosas dúas técnicas dinámicas. Os resultados empíricos obtidos da validación experimental sistemática dos nosos compresores contra corpus reais demostran que estes supoñen unha aportación fundamental no campo da compresión tanto para sistemas orientados a Text R.etrieval como para sistemas orientados á transmisión de datos, xa que os nosos compresores comprimen máis e máis eficientemente que moitos dos actuais compresores en uso (gzip, compress, etc.). Hai que salientar que a investigación realizada nesta tese inicia unha nova familia de compresores baseados en códigos densos cuxas posibilidades están apenas a ser albiscadas, polo que esperamos que traballos futuros nos permitan desenvolver novos compresores desta familia.