Statistical and repetition-based compressed data structures
Alberto Ordóñez Pereira · Dialnet (Universidad de la Rioja) · 2015
En esta tesis presentamos varias estructuras de datos comprimidas de naturaleza practica, centradas en problemas abiertos relacionados con bases de datos estadisticamente compresibles y bases de datos cuyo contenido es altamente repetitivo. En la primera parte, nos centramos en las estructuras de datos comprimidas para bases de datos estadisticamente compresibles, mas concretamente, en problemas relativos al manejo de alfabetos grandes. Este tipo de problemas aparecen cuando usamos tecnicas clasicas de compresion estadistica en estructuras de datos comprimidas para secuencias, y estas a su vez se aplican a problemas tales como la representacion de grillas de puntos o grafos. Concretamente, (a) presentamos soluciones muy eficientes en terminos de espacio para representar codigos libres de prefijo cuando el alfabeto el grande; (b) y tambien presentamos una nueva estructura de datos comprimida basada en wavelet trees para resolver consultas rank y select que obtiene compresion de orden cero y mejora las implementaciones previas de wavelet trees en alfabetos grandes. En la segunda parte de esta tesis, nos centramos en las bases de datos altamente repetitivas. Presentamos (c) una estructura de datos comprimida basada en gramaticas para resolver consultas rank y select en este tipo de contextos y que usa muy poco espacio; (d) la primera estructura de datos comprimida que obtiene espacio proporcional al de un compresor LZ77 y resuelve consultas rank y select en tiempo O(1), siendo en la practica casi tan rapido como las estructuras de datos basadas en compresion estadistica; (e) la primera estructura de datos practica que utiliza gramaticas para comprimir topologias de arboles, obteniendo resultados sin precedentes para la representacion de arboles repetitivos. Adicionalmente, mostramos varias aplicaciones en las que las estructuras de datos que proponemos a lo largo de la tesis resultan de utilidad. Desde representaciones de grillas de puntos, indices invertidos, auto-indices, sistemas XPath, hasta arboles de sufijos comprimidos para colecciones altamente repetitivas, mostrando diferentes resultados de interes tanto en terminos de tiempo como de espacio.