Tutorial de Estructuras de Datos Compactas
Slides
Gonzalo Navarro
Dictado en el ENC 2007,
Morelia, México
Motivación
La brecha entre los tiempos de CPU y los de I/O se ha mantenido creciente
durante las últimas décadas. Asimismo han aparecido nuevos niveles en la
jerarquía de memoria (caches de tamaño cada vez más considerable). Por ello,
se ha hecho cada vez más atractivo el uso de estructuras de datos que ocupen
poco espacio, incluso a veces comprimiendo la información sobre la que actúan.
Si bien trabajar sobre esta información compacta es más laborioso, el hecho de
poder mantenerla en una memoria órdenes de magnitud más rápida la convierte en
una alternativa muy conveniente a las implementaciones clásicas. El tutorial
ofrece un puente entre las estructuras de datos y la compresión, pues estudia
no sólo la forma de comprimir datos, sino de poder manipularlos en forma
comprimida sin necesidad de descomprimirlos. Esta es una rama muy activa y
reciente en investigación en algoritmos, y a la vez ofrece herramientas
sumamente útiles para desarrollos de alto valor agregado.
Objetivos
El objetivo del tutorial es entregar a los asistentes una visión de los
avances en estructuras de datos compactas y comprimidas, considerando los
aspectos teóricos así como su utilidad práctica. Se darán herramientas para
poder utilizar estructuras de datos de bajo coste de memoria para resolver
diversos problemas clásicos, conociendo su complejidad teórica y su
aplicabilidad.
Requisitos
Se requiere formación en algoritmos y estructuras de datos clásicas.
Temario
- Introducción y motivación
- La jerarquía de memoria, velocidades, precio y evolución.
- Los volúmenes de información a manejar y su evolución.
- Algunas aplicaciones de ejemplo: Genoma, Yahoo!
- Compresibilidad y entropía empírica.
- Rank y select sobre secuencias de bits.
- Rank y select en tiempo constante usando n+o(n) bits.
- Rank y select sobre la secuencia comprimida.
- Aplicaciones a hashing perfecto, sumas parciales y manejo de conjuntos.
- Secuencias dinámicas (inserción y borrado).
- Rank y select sobre secuencias de símbolos, y geometría.
- El wavelet tree.
- Soluciones para alfabetos mayores.
- Consultas sobre rangos bidimensionales.
- Arboles
- Representación usando 2n bits.
- Operaciones de navegación en tiempo constante.
- Otras representaciones.
- Mínimos en rangos y ancestros.
- Permutaciones
- Permutación directa e inversa.
- Textos y autoíndices
- El arreglo de sufijos.
- La transformación Burrows-Wheeler.
- Búsqueda hacia atrás y el FM-index.
- La función Psi y su compresión. El Compressed Suffix Array.
- Compresión Lempel-Ziv y el LZ-index.
- Grafos
- Fuentes de compresibilidad en grafos de la Web.
- Vecinos directos y navegación.
- Autoíndices y vecinos reversos.