ESTRUCTURAS COMPRIMIDAS PARA RANK, SELECT Y NEXT BASADAS EN GAP ENCODING

Abstract

Las estructuras de datos sucintas (o compactas) son representaciones de estructurasde datos clásicas, que fueron propuestas y estudiadas por Jacobson [11]. Estas estructurasofrecen funcionalidad y acceso a los datos utilizando poco espacio. Una de lasestructuras de datos sucintas más estudiadas son los vectores de bits, cuya representaciónsólo posee 0s y 1s. Esta representación permite mejorar estructuras de datossucintas ya existentes. Sobre estas estructuras de datos es posible realizar las operacionesSelect, Rank y Next. En la presente memoria se proponen estructuras de datosprácticas basadas en codificación por gaps, para representar vectores de bits y soportarlas operaciones Rank ,Select y Next de forma eficiente en cuanto a tiempo se refiere.Las estructuras propuestas también son eficientes en cuanto a espacio utilizado. Laevaluación experimental realizada, muestra que las estructuras propuestas son competitivascon las mejores alternativas del estado del arte. A modo de conclusión, se realizaráun análisis comparativo para determinar qué técnica es recomendada utilizar para lasdistintas situaciones.

Succint data structures, are representations of classic data structures, which wereproposed and studied by Jacobson [11]. These structures oer functionality and accessto data using little space. One of the most studied succint data structures are bitvectors, whose representation has only 0s and 1s. This representation improves existingsuccint data structures. On these data structures, one can perform the operationsSelect, Rank and Next. In this thesis, we will propose a practical data structures basedon gap encoding to represent bits vectors and support the operations Rank ,Select andNext eciently. The proposed structures are also ecient in terms of the space used.The experimental evaluation shows that the proposed structures are competitive comparedwith the best alternatives of the state of art. To conclude, a comparative analysis willbe performed to determine wich technique is recommended use for dierent situations.