IMPLEMENTACIÓN DE UNA ESTRUCTURA DE DATOS SUCINTA PARA VECTORES DE BITS UTILIZANDO COMPRESIÓN HÍBRIDA S18

Abstract

Los avances en la tecnología le han permitido al ser humano generar en la última década más datos de los que había generado en toda la historia. Procesar estos datos se ha vuelto un reto incluso en hardware moderno. Por suerte, las estructuras de datos sucintas permiten procesar estos datos y proveen de las mismas operaciones que sus contrapartes clásicas pero usando menos espacio. En este documento se estudia una nueva estructura de datos sucinta para vectores de bits. Se bosquejan las ideas claves y se presenta una implementación concreta de la misma. Finalmente se muestra que ésta es competitiva en la teoría y en la práctica, contra estructuras descritas en el estado del arte.

The advances in technology have allowed humankind to generate, in just the last decade, more data than the generated in all history until then. Processing this huge datasets has become a challenge even in modern hardware. Fortunately, succinct data structures allow processing data using a compact representation while providing the same operations as their classic counterparts. In this document a new succinct data structure for bit vectors is studied. The key ideasare outlined, and a concrete implementation is presented. Finally, it is shown that this structure is competitive in theory and practice against other state-of-the-art succinctstructures.