PDF de programación - Estructuras de Datos Compactas

Estructuras de Datos

Compactas

Gonzalo Navarro

www.dcc.uchile.cl/gnavarro

[email protected]

Departamento de Ciencias de la Computación (DCC)

Universidad de Chile

Sponsors:

Parte I: Secuencias

G. Navarro

Estructuras de Datos Compactas

Parte II: Otras Estructuras

G. Navarro

Estructuras de Datos Compactas

Parte I: Secuencias

G. Navarro

Estructuras de Datos Compactas

La Jerarquía de Memoria

Evolución de los Circuitos: Ley de Moore (1965)

“El número de transistores que consigue el menor costo por
transistor en un circuito integrado se duplica cada 24 meses”

Este gráfico y los siguientes sobre este
tema se han extraído de Wikipedia.

G. Navarro

Estructuras de Datos Compactas

La Jerarquía de Memoria

Consecuencias de la Ley de Moore

Las memorias, a igual costo, son cada vez mayores.
(Incluso a menor costo son mayores!)
Las CPUs, igualmente, son más potentes.
Se cree que valdrá al menos hasta el 2020.

G. Navarro

Estructuras de Datos Compactas

La Jerarquía de Memoria

¿Todo sigue la Ley de Moore?

No!
Discos (tiempos de seek, por ejemplo).

Velocidad de acceso a la RAM.

G. Navarro

Estructuras de Datos Compactas

La Jerarquía de Memoria

Situación Actual

Es posible, en general, tener tanta memoria como se

quiera.

Pero ésta es cada vez más lenta en comparación con la

CPU.

Aparecen nuevas memorias (caches)

Más rápidas (por tecnología y distancia a la CPU).
Más caras (por tecnología).
Más pequeñas (por distancia a la CPU y precio).

Por el compromiso velocidad/distancia, aparecen múltiples

niveles de cache.

G. Navarro

Estructuras de Datos Compactas

La Jerarquía de Memoria

Situación Actual

Números gruesos y (relativamente) actuales:

Unos pocos registros de CPU, menos de 1 nanosegundo.
Unos pocos KBs de cache L1, unos 10 nanosegundos.
Unos pocos MBs de cache L2, unos 30 nanosegundos.
Unos pocos GBs de RAM, unos 60 nanosegundos.
Unos pocos TBs de disco, unos 10 milisegundos de
latencia, más unos 500 nanosegundos por palabra
transferida.

La jerarquía de memoria es más relevante que nunca!
“La diferencia de tiempo entre tener un dato en RAM
versus traerlo de disco es comparable a la de tomar el
sacapuntas del escritorio donde estoy sentado versus
tomarme un avión a la China para ir a buscarlo y regresar.”

G. Navarro

Estructuras de Datos Compactas

La Jerarquía de Memoria

¿Y el Futuro?

Un poco de ciencia ficción:

Vivimos en un universo tridimensional.
Si empaqueto n objetos de cierto tamaño...
... la distancia del centro al más lejano es Ω(n1/3).

Siempre habrá memorias más pequeñas y rápidas...
... versus más grandes y lentas.
Incluso sin considerar razones económicas!

G. Navarro

Estructuras de Datos Compactas

Parte I: Secuencias

G. Navarro

Estructuras de Datos Compactas

Estructuras de Datos Compactas

Son estructuras de datos...

Modificadas para ocupar poco espacio.
Y eso no es compresión?
No: deben retener su funcionalidad y acceso directo.
Para qué, si la memoria es tan barata?
Mejoran el rendimiento debido a la jerarquía de memoria.
Especialmente si logramos operar en RAM algo que

necesitaría del disco!

G. Navarro

Estructuras de Datos Compactas

Estructuras de Datos Compactas

Un ejemplo motivante...

El genoma humano, recientemente decodificado.
Contiene 3 mil millones de bases.
Cada base necesita 2 bits (letras A, C, G, T).
Cabe holgadamente en una RAM de 1 GB.
Pero los biólogos necesitan hacer búsquedas complejas en él!
Estas operaciones serían lentísimas en forma secuencial...

por ejemplo, obtener la autorrepetición más larga requiere

tiempo cuadrático sin un índice apropiado;

con el índice adecuado se hace fácilmente en tiempo lineal.

G. Navarro

Estructuras de Datos Compactas

Estructuras de Datos Compactas

El índice que resuelve todos esos problemas es el árbol de

sufijos.

Pero éste requiere entre 30 GB y 60 GB de memoria!
Para peor, no se lleva bien con el disco.
En la práctica, sólo puede usarse para secuencias de
juguete, que hasta podrían tratarse secuencialmente.
Usando estructuras de datos compactas, cabe en una

RAM de 2 GB.

Es mucho más lento que el árbol de sufijos clásico en una

misma memoria...

pero es infinitamente más rápido corriendo en RAM que el

original en disco.

G. Navarro

Estructuras de Datos Compactas

Estructuras de Datos Compactas

Otro ejemplo motivante...

El grafo de la Web contenía el 2004 unos 11.5 mil millones

de nodos y 150 mil millones de links.

Crece más o menos según la Ley de Moore.
Esto considera sólo la Web estática indexada!
Necesitaría unos 600 GB de RAM para almacenarse.
Gigantes como Google y Yahoo! lo usan para calcular

PageRank, encontrar comunidades, etc.

Usando estructuras de datos compactas, cabe en unos

100 GB.

Y con un poco más permite además navegar el grafo hacia

atrás, y otras operaciones útiles.

G. Navarro

Estructuras de Datos Compactas

Mapa del Tutorial

Ahora que están convencidos...

Revisaremos los avances en la última década en diversas

estructuras de datos compactas.

Estas les darán herramientas teóricas y prácticas para

aprovechar la jerarquía de memoria en el diseño de
algoritmos y estructuras de datos.

Veremos estructuras compactas para:

Manipular secuencias de bits
Manipular secuencias de símbolos
Navegar en árboles
Buscar en textos
Navegar en grafos

Y aplicaciones a hashing, conjuntos, sumas parciales,

geometría, permutaciones, y más.

G. Navarro

Estructuras de Datos Compactas

Parte I: Secuencias

G. Navarro

Estructuras de Datos Compactas

Entropía Empírica

Entropía binaria: si hay n0 ceros y n1 unos en una

secuencia de bits B (n0 + n1 = n = |B|)
1
n

H0(B) =

n1
n

n0
n

log

+

log

n
n0

n
n1

n



n0

log n



n

=

log

+O

(utilizaremos logaritmos en base 2 por defecto).

Entropía de orden cero: si hay nc ocurrencias de c en S

(secuencia de símbolos sobre un alfabeto Σ),



c∈Σ

nc
n

log

n
nc

H0(S) =

Cota inferior a cualquier codificación de Σ que asigne

siempre el mismo código al mismo símbolo (ej. Huffman).

G. Navarro

Estructuras de Datos Compactas

Entropía Empírica

Entropía de orden k: si SA es la secuencia de los

caracteres que siguen a las ocurrencias de A en S,



A∈Σk

Hk (S) =

1
n

|SA|H0(SA)

Cota inferior a codificaciones que consideran los k

símbolos precedentes (ej. PPM).

G. Navarro

Estructuras de Datos Compactas

Modelo RAM y Análisis Asintótico

Mediremos el espacio en bits.
Modelo RAM:

Necesitamos log n bits para direccionar en una memoria de

n bits.

Si direccionamos n bits, consideraremos que el computador
O(n) significa limitado superiormente por c · n para alguna

puede manipular O(log n) bits en tiempo constante.

constante (positiva) c a partir de un cierto n = n0.

o(n) significa que, dividido por n, tiende a cero cuando n

tiende a infinito.

G. Navarro

Estructuras de Datos Compactas

Parte I: Secuencias

G. Navarro

Estructuras de Datos Compactas

Secuencias de Bits

Consideremos una secuencia de n bits, B[1, n].
Nos interesan las siguientes operaciones sobre B:

rankb(B, i): ¿cuántas veces aparece el bit b en B[1, i]?
selectb(B, i): ¿dónde ocurre el bit b por i-ésima vez en B?

Algunas propiedades simples:
rank0(B, i) = i − rank1(B, i).
B[i] = rank1(B, i) − rank1(B, i − 1) (sup. rankb(B, 0) = 0).
rankb(B, selectb(B, i)) = i.
Si B[i] = b, selectb(B, rankb(B, i)) = i.
En general, selectb(B, rankb(B, i)) ≤ i.

Cuando no mencionemos b supondremos b = 1.

G. Navarro

Estructuras de Datos Compactas

Secuencias de Bits

G. Navarro

Estructuras de Datos Compactas

10011101010000000110010011110100select(B,8) = 21select(B,7) = 13select(B,1) = 3rank(B,13) = 7rank(B,20) = 7Secuencias de Bits

Resultado

Se puede responder rank y select en tiempo constante.
Esto es fácil almacenando todas las respuestas en

O(n log n) bits, pero solamente se necesitan

n · log log n



log n

n + O

= n + o(n)

bits de espacio (los n bits para B[1, n] más un extra
sublineal).

Las soluciones son prácticas (especialmente rank).
Veremos algunas de las muchas aplicaciones antes de

mostrar cómo se logra este resultado.

G. Navarro

Estructuras de Datos Compactas

Rank y Select

Una aplicación: Hashing perfecto

Si el universo tiene n claves (por ejemplo [1, n]),
y queremos almacenar t elementos con r bits de datos,
hashing perfecto nos ofrece:

O(tr ) bits de espacio,
tiempo de acceso constante
construcción aleatorizada o muy costosa.

G. Navarro

Estructuras de Datos Compactas

Rank y Select

Consideremos una solución usando rank:

Tendremos un arreglo A[1, t] con los datos,
más un bitmap B[1, n] que marque las claves que existen.
Entonces nuestro dato con clave i está en A[rank(B, i)].
Y está en el conjunto si B[i] = 1.
Total: tr + n + o(n) bits.

La solución es interesante si n/t no es muy grande

comparado con r.

Además es mucho más simple.
Incluso podríamos lograr tr + O(t log(n/t)) bits (menos de

un puntero e