REIMPLEMENTACIÓN DE ESTRUCTURAS COMPRIMIDAS PARA RANK Y SELECT BASADAS EN GAP ENCODING

Abstract

Dada la creciente cantidad de datos que son generados en la actualidad, es importante el estudio de las estructuras de datos sucintas las cuales permiten almacenar estos datos de forma estructurada y ocupando el menor espacio posible con el objetivo de accederlos en tiempos rápidos. Uno de los elementos básicos de estas estructuras son los vectores de bits (o bitvector en inglés) específicamente aquellos que se implementan de forma comprimida y con soporte de operaciones rank y select. En el presente documento, se muestra la propuesta e implementación de un método de compresión para vectores de bits con soporte para las operaciones mencionadas anteriormente usando las técnicas de gap encoding y generación de palabras S9. Además se muestra que es eficiente en espacio y tiempo al realizar comparaciones con las otras técnicas similares del estado del arte que implementa la librería sds1. Como conclusión, se destaca que al utilizar algunos vectores de bits de baja densidad, la implementación logra un mejor rendimiento de espacio y tiempo que las previamente implementadas.

Given the growing quantities of data that is generated every day, it is important to study succinct data structures which allow storing this information in a structured way while accessing them in quick times. One of the basic elements of these structures are bit vectors (or bit sequences), specifically those that are implemented in a compressed way and support rank and select operations. In this document we present a proposal and implementation of a bit vector compression method with support for the aforementioned operations using the techniques of gap encoding and Simple 9 word generation. We also show that it is efficient in space and time when compared against other similar techniques of the state of the art implemented by the sdsl library. As conclusion, we show situations in which the implementation achieves stand out performance in terms of space and time.