REDISEÑO DE AUTOÍNDICES COMPRIMIDOS PARA TEXTOS BASADOS EN LEMPEL ZIV

ARAYA COHEN, MATÍAS ANDRÉS (2018)

Catalogado desde la version PDF de la tesis.

Tesis Pregrado

El problema de búsqueda en textos es cada vez más utilizado dada la cantidad de literaturae investigación que se realizan en formato digital. Para resolver este problema se encuentranvarios métodos, pero el mayor problema que tienen es la cantidad de espacio que utilizan, yaque deben almacenar el texto y las estructuras de datos necesarias para la búsqueda, quedandomuchas veces tamaños inmanejables en memoria principal. Las soluciones más eficientesconsisten en crear índices del texto, que a su vez se comprimen, lo que facilita la búsqueday ocupan el menor espacio posible. En este trabajo se crea un rediseño de un auto índicecomprimido basado en el algoritmo de compresión Lempel-Ziv (LZ-index abreviado). Sedice que es un rediseño ya que toma la solución creada por Navarro, la que se actualiza atecnologías y métodos de desarrollo modernos.

The problem of searching in texts is increasingly used given the amount of literature andresearch that is done in digital format. To solve this problem are several methods, but thebiggest problem they have is the amount of space they use, since they must store the text anddata structures necessary for the search, often leaving unmanageable sizes in main memory.The most efficient solutions consist of creating indexes of the text that are compressed, whichfacilitates the search and use the least possible space. In this work, a redesign of a compressedself-index based on the Lempel-Ziv compression algorithm (abbreviated LZ-index) is created.It is said to be a redesign as it takes the solution created by Navarro, which is updated tomodern technologies and development methods.