Estructuras de Datos Compactas Gonzalo Navarro www.dcc.uchile.cl/gnavarro
[email protected] ´ (DCC) Departamento de Ciencias de la Computacion 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 ´ de los Circuitos: Ley de Moore (1965) Evolucion “El numero de transistores que consigue el menor costo por ´ transistor en un circuito integrado se duplica cada 24 meses”
´ Este grafico 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 I
Las memorias, a igual costo, son cada vez mayores.
I I
(Incluso a menor costo son mayores!) ´ potentes. Las CPUs, igualmente, son mas
I
Se cree que valdra´ al menos hasta el 2020.
G. Navarro
Estructuras de Datos Compactas
La Jerarqu´ıa de Memoria ¿Todo sigue la Ley de Moore? I
No!
I
Discos (tiempos de seek, por ejemplo).
I
Velocidad de acceso a la RAM.
G. Navarro
Estructuras de Datos Compactas
La Jerarqu´ıa de Memoria ´ Actual Situacion I
I
I
Es posible, en general, tener tanta memoria como se quiera. ´ ´ lenta en comparacion ´ con la Pero esta es cada vez mas CPU. Aparecen nuevas memorias (caches) I I I
I
´ rapidas ´ Mas (por tecnolog´ıa y distancia a la CPU). ´ caras (por tecnolog´ıa). Mas ´ pequenas ˜ (por distancia a la CPU y precio). Mas
Por el compromiso velocidad/distancia, aparecen multiples ´ niveles de cache.
G. Navarro
Estructuras de Datos Compactas
La Jerarqu´ıa de Memoria ´ Actual Situacion I
Numeros gruesos y (relativamente) actuales: ´ I I I I I
I
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 ´ unos 500 nanosegundos por palabra latencia, mas transferida.
´ relevante que nunca! La jerarqu´ıa de memoria es mas “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 ´ a la China para ir a buscarlo y regresar.” tomarme un avion
G. Navarro
Estructuras de Datos Compactas
La Jerarqu´ıa de Memoria
¿Y el Futuro? I
´ Un poco de ciencia ficcion: I I I
Vivimos en un universo tridimensional. ˜ Si empaqueto n objetos de cierto tamano... ´ lejano es Ω(n1/3 ). ... la distancia del centro al mas
I
´ pequenas ˜ y rapidas... ´ Siempre habra´ memorias mas ´ grandes y lentas. ... versus mas
I
´ Incluso sin considerar razones economicas!
I
G. Navarro
Estructuras de Datos Compactas
Parte I: Secuencias
G. Navarro
Estructuras de Datos Compactas
Estructuras de Datos Compactas
Son estructuras de datos... I
Modificadas para ocupar poco espacio.
I
´ Y eso no es compresion?
I
No: deben retener su funcionalidad y acceso directo.
I
´ si la memoria es tan barata? Para que,
I
Mejoran el rendimiento debido a la jerarqu´ıa de memoria.
I
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... I
El genoma humano, recientemente decodificado.
I
Contiene 3 mil millones de bases.
I
Cada base necesita 2 bits (letras A, C, G, T).
I
Cabe holgadamente en una RAM de 1 GB.
I
´ ´ Pero los biologos necesitan hacer busquedas complejas en el! ´
I
Estas operaciones ser´ıan lent´ısimas en forma secuencial... I
I
´ mas ´ larga requiere por ejemplo, obtener la autorrepeticion ´ tiempo cuadratico sin un ´ındice apropiado; ´ con el ´ındice adecuado se hace facilmente en tiempo lineal.
G. Navarro
Estructuras de Datos Compactas
Estructuras de Datos Compactas I
I I I
I
I
I
´ El ´ındice que resuelve todos esos problemas es el arbol de sufijos. ´ Pero este requiere entre 30 GB y 60 GB de memoria! Para peor, no se lleva bien con el disco. ´ ´ puede usarse para secuencias de En la practica, solo juguete, que hasta podr´ıan tratarse secuencialmente. Usando estructuras de datos compactas, cabe en una RAM de 2 GB. ´ lento que el arbol ´ ´ Es mucho mas de sufijos clasico en una misma memoria... ´ rapido ´ pero es infinitamente mas corriendo en RAM que el original en disco.
G. Navarro
Estructuras de Datos Compactas
Estructuras de Datos Compactas Otro ejemplo motivante...
I
El grafo de la Web conten´ıa el 2004 unos 11.5 mil millones de nodos y 150 mil millones de links. ´ o menos segun Crece mas ´ la Ley de Moore.
I
´ la Web estatica ´ Esto considera solo indexada!
I
Necesitar´ıa unos 600 GB de RAM para almacenarse.
I
Gigantes como Google y Yahoo! lo usan para calcular PageRank, encontrar comunidades, etc.
I
Usando estructuras de datos compactas, cabe en unos 100 GB. ´ permite ademas ´ navegar el grafo hacia Y con un poco mas ´ y otras operaciones utiles. atras, ´
I
I
G. Navarro
Estructuras de Datos Compactas
Mapa del Tutorial ´ convencidos... Ahora que estan I
I
I
´ Revisaremos los avances en la ultima decada en diversas ´ estructuras de datos compactas. ´ herramientas teoricas ´ ´ Estas les daran y practicas para ˜ de aprovechar la jerarqu´ıa de memoria en el diseno algoritmos y estructuras de datos. Veremos estructuras compactas para: I I I I I
I
Manipular secuencias de bits Manipular secuencias de s´ımbolos ´ Navegar en arboles Buscar en textos Navegar en grafos
Y aplicaciones a hashing, conjuntos, sumas parciales, ´ geometr´ıa, permutaciones, y mas.
G. Navarro
Estructuras de Datos Compactas
Parte I: Secuencias
G. Navarro
Estructuras de Datos Compactas
Entrop´ıa Emp´ırica I
Entrop´ıa binaria: si hay n0 ceros y n1 unos en una secuencia de bits B (n0 + n1 = n = |B|) n n1 n 1 n log n n0 log + log = log +O H0 (B) = n n0 n n1 n n0 n (utilizaremos logaritmos en base 2 por defecto).
I
Entrop´ıa de orden cero: si hay nc ocurrencias de c en S (secuencia de s´ımbolos sobre un alfabeto Σ), H0 (S) =
X nc c∈Σ
I
n
log
n nc
´ de Σ que asigne Cota inferior a cualquier codificacion ´ siempre el mismo codigo al mismo s´ımbolo (ej. Huffman).
G. Navarro
Estructuras de Datos Compactas
Entrop´ıa Emp´ırica
I
Entrop´ıa de orden k : si SA es la secuencia de los caracteres que siguen a las ocurrencias de A en S, Hk (S) =
1 X |SA |H0 (SA ) n k A∈Σ
I
Cota inferior a codificaciones que consideran los k s´ımbolos precedentes (ej. PPM).
G. Navarro
Estructuras de Datos Compactas
´ ´ Modelo RAM y Analisis Asintotico
I I
Mediremos el espacio en bits. Modelo RAM: I
I
Necesitamos log n bits para direccionar en una memoria de n bits. Si direccionamos n bits, consideraremos que el computador puede manipular O(log n) bits en tiempo constante.
I
O(n) significa limitado superiormente por c · n para alguna constante (positiva) c a partir de un cierto n = n0 .
I
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
I I
Consideremos una secuencia de n bits, B[1, n]. Nos interesan las siguientes operaciones sobre B: I I
I
Algunas propiedades simples: I I I I I
I
´ rankb (B, i): ¿cuantas veces aparece el bit b en B[1, i]? ´ ´ selectb (B, i): ¿donde ocurre el bit b por i-esima vez en B? 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
rank(B,13) = 7 rank(B,20) = 7
00110011101010000000110010011110
select(B,1) = 3 select(B,7) = 13 select(B,8) = 21
G. Navarro
Estructuras de Datos Compactas
Secuencias de Bits Resultado I I
I I
Se puede responder rank y select en tiempo constante. ´ almacenando todas las respuestas en Esto es facil O(n log n) bits, pero solamente se necesitan n · log log n = n + o(n) n+O log n ´ un extra bits de espacio (los n bits para B[1, n] mas sublineal). ´ Las soluciones son practicas (especialmente rank). Veremos algunas de las muchas aplicaciones antes de ´ mostrar como se logra este resultado.
G. Navarro
Estructuras de Datos Compactas
Rank y Select
´ Hashing perfecto Una aplicacion: I
Si el universo tiene n claves (por ejemplo [1, n]),
I
y queremos almacenar t elementos con r bits de datos, hashing perfecto nos ofrece:
I
I I I
O(tr ) bits de espacio, tiempo de acceso constante ´ aleatorizada o muy costosa. construccion
G. Navarro
Estructuras de Datos Compactas
Rank y Select
I
´ usando rank: Consideremos una solucion I I I I I
I
I I
Tendremos un arreglo A[1, t] con los datos, ´ un bitmap B[1, n] que marque las claves que existen. mas Entonces nuestro dato con clave i esta´ en A[rank (B, i)]. Y esta´ en el conjunto si B[i] = 1. Total: tr + n + o(n) bits.
´ es interesante si n/t no es muy grande La solucion comparado con r . ´ es mucho mas ´ simple. Ademas Incluso podr´ıamos lograr tr + O(t log(n/t)) bits (menos de un puntero extra por elemento).
G. Navarro
Estructuras de Datos Compactas
Rank y Select
Hashing perfecto rank(B,7) = 3
B
A
00110011101010000000110010011110
Data (3)
Data (4)
Data (7)
G. Navarro
. . .
Estructuras de Datos Compactas
Rank y Select
´ Sumas parciales Otra aplicacion: I I
Supongamos que tenemos t numeros A[1, t] que suman n, ´ y queremos hacer dos tipos de preguntas sobre el arreglo: I I
I
Pr ´ Sum: Dado r , ¿cuanto es j=1 A[j] ? Pr Search: Dado s, ¿para que´ r ocurre que j=1 A[j] > s ?
´ responderlas en tiempo constante usando Es facil t log n + n log t bits...
G. Navarro
Estructuras de Datos Compactas
Rank y Select
I
Supongamos que los A[i] son no negativos.
I
I
Con rank y select las podemos responder usando n + t + o(n) bits! P Marcar con 1, en B[1, n + t], las posiciones r + rj=1 A[j].
I
Entonces I I
I
Sum: select1 (B, r ) − r . Search: 1 + rank1 (B, select0 (B, s)).
´ se Y si n + t bits parece mucho, mostraremos que tambien n+t puede hacer usando t log t bits!
G. Navarro
Estructuras de Datos Compactas
Rank y Select Sumas parciales
A
2
0
2
0
0
1
1
7
. . .
select(B,6)−6 = 11−6 = 5
B
0 0 1 1 0 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 1 1 1 1 0
1+rank(select0 (B,10)) = 1+rank(B,17) = 8
G. Navarro
Estructuras de Datos Compactas
Rank y Select
´ Predecesor y sucesor Y otra mas: I I
Tenemos t elementos del conjunto [1, n], y queremos hacer dos tipos de preguntas sobre el conjunto: I
I
I
´ es el menor numero Succ: Dado i, ¿cual ≥ i en el ´ conjunto? ´ es el mayor numero Pred: Dado i, ¿cual ≤ i en el conjunto? ´
´ Nuevamente, se responden facilmente en tiempo constante usando O(n log n) bits...
G. Navarro
Estructuras de Datos Compactas
Rank y Select
I
´ Con rank y select se pueden responder usando solo n + o(n) bits: I I
Succ: select(B, rank (B, i − 1) + 1). Pred: select(B, rank (B, i)).
I
´ Podr´ıamos facilmente obtener Succ k y Pred k en tiempo constante.
I
Y con bitmaps comprimidos usar´ıamos t log(n/t) bits!
G. Navarro
Estructuras de Datos Compactas
Rank Rank en Tiempo Constante I
Cortamos B en bloques de b = (log n)/2 bits.
I
Almacenamos un arreglo R[1, n/b] con los valores de rank al comienzo de los bloques.
I
Como necesitamos log n bits para almacenar un valor de rank, el total de bits que ocupa R es n n · log n = · log n = 2n b (log n)/2
I
´ de lo Aceptemos ese precio en espacio por ahora (es mas prometido).
G. Navarro
Estructuras de Datos Compactas
Rank
I
´ ¿Como calculamos rank(B, i) ? I I I
I
Descomponemos i = q · b + r , 0 ≤ r < b. La cantidad de 1’s hasta qb es R[q]. Debemos contar los 1’s en B[qb + 1, qb + r ].
Supongamos que tenemos una tabla T [0, 2b − 1][0, b − 1], tal que T [x, r ] = total de 1’s en x[1, r ] donde vemos x como una tira de b bits.
G. Navarro
Estructuras de Datos Compactas
Rank I
Como cada celda de T puede tomar valores en [0, b − 1], T necesita 2b · b · log b = 2 ≤
log n 2
·
log n · (log log n − 1) 2
1√ n log n log log n = o(n) bits. 2
´ necesita 512 KB. Por ejemplo, si n = 232 , T solo I
Entonces, la respuesta final se obtiene en tiempo constante como: R[q] + T [B[qb + 1..qb + b], r ]
I
Muy bien, pero nos gastamos 3n + o(n) bits... G. Navarro
Estructuras de Datos Compactas
Rank rank(B,13) = 7
B
0 0 1 1 0 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 1 1 1 1 0
R
0
1
2
5
6
7
7
000 001 010 011 100 101 110 111
G. Navarro
8
9
0
1
2
0
0
0
0
0
0
0
0
1
0
0
1
0
1
1
0
1
1
0
1
2
0
1
2
10
13
14
Estructuras de Datos Compactas
Rank Consiguiendo o(n) bits extra I
´ en superbloques de Cortamos B tambien s =
I
I
(log n)2 = b · log n bits. 2
Almacenamos un arreglo S[1, n/s] con los valores de rank al comienzo de los superbloques. ´ desde Ahora los valores de R se almacenan sumando solo el comienzo del superbloque correspondiente: R[q] = rank(B, qb) − S[bq/ log nc] = rank(B, qb) − rank(B, bq/ log nc · log n)
G. Navarro
Estructuras de Datos Compactas
Rank I
Como necesitamos log n bits para almacenar un valor de rank en S, el total de bits que ocupa S es n 2n n · log n = · log n = = o(n) 2 s log n (log n) /2
I
Como los valores de R se almacenan relativos al ´ pueden llegar a valer s = O(log n)2 , y superbloque, solo ´ necesitan 2 log log n bits. Por ello R ocupa por ello solo ahora n · 2 log log n = b =
G. Navarro
n · 2 log log n (log n)/2 4n · log log n = o(n) bits. log n
Estructuras de Datos Compactas
Rank
I
´ ¿Como calculamos rank(B, i) ? I I I
Descomponemos i = q · b + r , 0 ≤ r < b. Descomponemos i = q 0 · s + r 0 , 0 ≤ r 0 < s. Y finalmente sumamos los contenidos de tres tablas: rank (B, i) = S[q 0 ] + R[q] + T [B[qb + 1..qb + b], r ]
G. Navarro
Estructuras de Datos Compactas
Rank rank(B,13) = 7
B
0 0 1 1 0 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 1 1 1 1 0
S
0
R
5
7
10
0 1 2 0 1 2 0 1 2 0 3 4
G. Navarro
T
000 001 010 011 100 101 110 111
Estructuras de Datos Compactas
0
1
2
0
0
0
0
0
0
0
0
1
0
0
1
0
1
1
0
1
1
0
1
2
0
1
2
Rank ´ Practica ´ Implementacion I
´ Evitar divisiones y modulos, usar potencias de 2.
I
Tratar de usar valores alineados a bytes, shorts, o ints. ˜ son parametrizables. Los tamanos
I I I
Aprovechar el cache. Ejemplo 1: I I I
I
Usamos solamente superbloques, de 20 × 32 = 640 bits. 1 = 5%. El espacio extra es 20 Recorremos secuencialmente el superbloque usando popcount de a bytes (a lo sumo 80 operaciones).
Ejemplo 2: I I I
32 = 12.5%). Usamos superbloques de 256 bits (overhead 256 8 Usamos bloques de 32 bits (overhead 32 = 25%). ´ 4 bytes. Popcount de a lo mas
G. Navarro
Estructuras de Datos Compactas
Rank
´ Practica ´ Implementacion 1.1
Classical >66% Two-level 37.5% One-level 5% One-level 10% One-level 25% One-level 33% One-level 50%
1
time(microsec)
0.9 0.8 0.7 0.6
Observar el efecto del cache y el hit ratio.
´ Graficos obtenidos por mi ´ alumno Rodrigo Gonzalez.
0.5 0.4 0.3 0.2 0.1 0 12
14
16
18
20 22 log(n)
G. Navarro
24
26
28
30
Estructuras de Datos Compactas
Select Select en Tiempo Constante I
´ donde o(n) = O(n/ log log n). Describiremos una solucion
I
Notar que necesitamos hacer un sampling regular en los argumentos de select, no regular en B (ambos criterios coincid´ıan para rank).
I
Un corte en bloques y superbloques como para rank no funciona, porque los numeros dentro de un bloque no se ´ reducen.
I
La idea fundamental es: si un bloque tiene pocos 1’s, puedo almacenar todas las respuestas a select en poco espacio. ´ complejo que rank, tanto en la Veremos que select es mas ´ teor´ıa como en la practica.
I
G. Navarro
Estructuras de Datos Compactas
Select
I
Cortamos los argumentos de select en superbloques de s = log2 n argumentos.
I
Estos superbloques tienen largo variable en B, pero tienen exactamente s 1’s.
I
Decimos que un superbloque es esparso si su largo en B es a lo menos s · log n · log log n; sino es denso. ´ fundamental: podemos guardar todas las Observacion respuestas de todos los bloques esparsos y el sobrecosto total es O(n/ log log n).
I
G. Navarro
Estructuras de Datos Compactas
Select I
Almacenamos un bitmap E[1, n/s] indicando que´ superbloques son esparsos.
I
Almacenamos todas las respuestas a select en todos los superbloques esparsos en un arreglo de arreglos R: select(B, i) = R[rank(E, bi/sc)] [1 + (i mod s)] si E[bi/sc] = 1.
I
Para los superbloques densos, solamente almacenamos un arreglo P[1, n/s] con las posiciones de B donde comienzan.
I
Aun ´ no solucionamos el problema de los superbloques ´ densos, pero sabemos donde empiezan, y su largo es a lo ´ s log n log log n = log3 n log log n. mas
G. Navarro
Estructuras de Datos Compactas
Select I
Dividimos los superbloques densos en bloques de b = (log log n)2 argumentos.
I
Aplicamos la misma idea nuevamente dentro de cada superbloque denso.
I
Necesitamos log(log3 n log log n) ≤ 4 log log n bits para ´ dentro de un superbloque denso. almacenar una posicion
I
Diremos que un bloque es esparso si su largo en B es a lo menos 4b(log log n)2 , y es denso sino.
I
Almacenar todas las respuestas (relativas) de los bloques esparsos dentro de superbloques densos cuesta en total O(n/ log log n) bits.
G. Navarro
Estructuras de Datos Compactas
Select I
I
I
Almacenaremos un bitmap E 0 [1, s/b] indicando que´ bloques son esparsos. ´ Para los bloques densos, solamente almacenamos un arreglo P 0 [1, s/b] con las posiciones del superbloque donde comienzan. ´ O(n/ log log n) bits. Este P 0 cuesta tambien
I
No hemos solucionado el problema de los bloques densos, ´ ´ pero sabemos donde empiezan, y su largo es a lo mas 4 4(log log n) = o(log n) (siempre es < 82 log n).
I
Entonces, los bloques densos se pueden procesar en tiempo O(1) usando tablas tipo T .
G. Navarro
Estructuras de Datos Compactas
Select
I
´ Como calculamos select(B, i)? I I I I I
I
I
Descomponemos i = q · s + r . Si E[q] = 1, es un superbloque esparso y retornamos R[...]. Sino, es un superbloque denso que comienza en P[q]. Descomponemos r = q 0 · b + r 0 . Si Eq0 [q 0 ] = 1 es un bloque esparso, retornamos P[q] + R 0 [...]. Sino, es un bloque denso que comienza en p = P[q] + P 0 [q 0 ]. ´ Buscamos el r 0 -esimo 1 en B[p...p + 4(log log n)4 ] usando tablas.
G. Navarro
Estructuras de Datos Compactas
Select E’
110 0
R’
2 3 6 7
P’
8
B
00110011101010000000110010011110
E
010
0
R
13
21 22
P
1
30
25
28
29
T
G. Navarro
000 001 010 011 100 101 110 111
1
2
3
0 3 2 2 1 1 1 1
0 0 0 3 0 3 2 2
0 0 0 0 0 0 0 3
Estructuras de Datos Compactas
Select ´ Practica ´ Implementacion I I
´ Implementado directamente es bastante poco practico. Por ejemplo: I
I I
I
Si aceptamos recorrer 2048 bits (512 bytes) secuencialmente... ...logramos 78% de espacio extra. ´ queremos select0 . Eso debe duplicarse si ademas
´ practica ´ Una solucion aceptable: I I I I I
select es el inverso de rank . Lo resolvemos con busqueda binaria en rank . ´ Primero en S, luego en R, finalmente en los bits. ´ El mismo espacio de rank , y resolvemos select0 tambien. ´ nivel de superbloques. La mejor alternativa es con un solo
G. Navarro
Estructuras de Datos Compactas
Select ´ Practica ´ Implementacion 3
1/log(n) 5% 10% 25% 33% 50%
time(microsec)
2.5 2
Observar el efecto del cache y el hit ratio.
1.5
´ Graficos obtenidos por mi ´ alumno Rodrigo Gonzalez.
1 0.5 0 12
14
16
18
20 22 log(n)
G. Navarro
24
26
28
30
Estructuras de Datos Compactas
Parte I: Secuencias
G. Navarro
Estructuras de Datos Compactas
Rank y Select sobre Secuencias Comprimidas I
En muchas aplicaciones, la secuencia tiene pocos o muchos 1’s.
I
Nos concentraremos en el caso en que hay m H[i − 1], agregamos H[i] − H[i − 1] s´ımbolos ’(’. Si H[i] < H[i − 1], agregamos H[i − 1] − H[i] s´ımbolos ’)’.
I
´ en parentesis ´ El resultado es S[1, 2n], la representacion ´ del arbol cartesiano.
I
El m´ınimo en H corresponde al min[x, y ] en S.
I
Marcamos en otro bitmap P[1, 2n] las posiciones donde ´ de cada valor de H en S. comienza la codificacion
I
Entonces, RMQ(i, j) = A[rank(P, min[select(P, i), select(P, j+1)−1])] S
se resuelve en tiempo constante.
G. Navarro
Estructuras de Datos Compactas
RMQ: M´ınimos en Rangos 1 3
2
7
15
21
6
8
4
9
14
5
12
11
13
10 17
16
20 1
2
3
5
4
4
19
5
6
18
6
5
7
3
8
1
9
2
10
4
12
3
13
4
14
2
15
4
16
5
17
3
18
1
19
3
20
3 2
S
( ( ( ) ( ( ( ) ( ( ) ) ) ) ) ( ) ) ( ( ( ( ) ( ) ) ( ( ( ) ) ) ) ( ( ) ( ) ) )
P
1001100110110101101000111010110101011100
G. Navarro
0
11
H
2
Estructuras de Datos Compactas
21
3
Parte II: Otras Estructuras
G. Navarro
Estructuras de Datos Compactas
´ usando Parentesis ´ Otra Representacion I I
´ usada tiene muchas bondades. La representacion ´ importante: Pero es ineficiente para una operacion ´ hijo(v , i) es el i-esimo hijo de v .
I
Lo podemos hacer en tiempo O(i), pero eso puede ser ´ muy lento en ciertos arboles. ´ alternativa que resuelve esto Veremos una representacion en tiempo constante. ´ puede calcular la cantidad de hijos (aridad) de v Tambien en tiempo constante. ´ permitira´ comprimir el arbol! ´ Y tambien
I
A cambio, no permite conocer la profundidad de v .
I
I
I
G. Navarro
Estructuras de Datos Compactas
´ usando Parentesis ´ Otra Representacion I
´ Usaremos parentesis balanceados, pero con otro significado.
I
Un nodo v con hijos v1 , v2 , . . . , vk se representara´ como R(v )
=
( ( . . . ( ) R(vk ) . . . R(v2 ) R(v1 ) | {z } k
I
´ El nodo v corresponde a su primer parentesis.
I
Una hoja se representa como ’)’. ´ Propiedad importante: Todo arbol termina con ’)’, y su exceso interno es −1.
I
I I
Agregamos un ’(’ a S para que quede balanceada. ´ En total S queda con 2n parentesis balanceados!
G. Navarro
Estructuras de Datos Compactas
´ usando Parentesis ´ Otra Representacion 1
3
4
9
5
6 7
11
10
2
12
13
14 8
15
(((( ) (( )( )())))(((( )) ( ) (( )))))
G. Navarro
Estructuras de Datos Compactas
´ usando Parentesis ´ Otra Representacion
I
Utilizaremos las mismas operaciones open, close y ´ enclose para navegar en esta nueva representacion.
I
La aridad de un nodo es select’)’ (S, rank’)’ (S, v − 1) + 1) − v . ´ El i-esimo hijo de v es close(v + i − 1) + 1
I I I
El padre de v es 1 + select’)’ (S, rank’)’ (S, open(v − 1))). Puedo saber que´ hijo soy de mi padre: open(v − 1) − padre(v ) + 1
G. Navarro
Estructuras de Datos Compactas
´ usando Parentesis ´ Otra Representacion
I
´ Con las operaciones anteriores tengo automaticamente los hermanos.
I I
Los ancestros siguen conteniendo a sus descendientes. ´ tipo preorden. Con rank’)’ (S, v ) tengo numeracion
I
´ tamano ˜ de subarbol. ´ Por lo tanto, tengo tambien
I
Contando ’()’ tengo cantidad de nodos internos.
I
Con ambos, tengo cantidad de hojas. ´ puede resolverse LCA practicamente ´ Tambien del mismo modo.
I
G. Navarro
Estructuras de Datos Compactas
´ usando Parentesis ´ Otra Representacion
Comprimiendo I
´ es la secuencia de las Realmente esta representacion aridades en preorden, escritas en unario.
I
Se podr´ıan representar como numeros y comprimir la ´ secuencia a orden cero.
I
Eso comprime si existe regularidad en las aridades del ´ arbol.
I
´ No veremos el detalle, es demasiado tecnico.
G. Navarro
Estructuras de Datos Compactas
´ de Secuencias Textos: Otra Vision
I
˜ σ... Dado un alfabeto Σ de tamano
I
... un texto T [1, n] es una secuencia sobre Σ.
I
¿Eso no es lo mismo que una secuencia?
I
S´ı, pero nos interesan otras operaciones. ´ P[1, m]: Dado un patron
I
I I
Contar la cantidad de ocurrencias de P en T (occ). Ubicar esas occ ocurrencias en T .
G. Navarro
Estructuras de Datos Compactas
´ de Secuencias Textos: Otra Vision
I
Cuando el texto no es muy largo, o cambia muy frecuentemente, lo mejor es la busqueda secuencial. ´
I
Pero en el mejor caso esto cuesta O(
I
´ queremos Cuando el texto es de lenguaje natural y solo buscar palabras y frases, lo mejor es un ´ındice invertido.
I
Esto es un vocabulario de las palabras distintas, y una lista de ocurrencias de cada una.
I
No es dif´ıcil conseguir poco espacio con bitmaps comprimidos para las listas. ´ Otras variantes se especializan en calculo de relevancia.
I
G. Navarro
n logσ m ). m
Estructuras de Datos Compactas
´ de Secuencias Textos: Otra Vision I
Los ´ındices invertidos funcionan muy bien.
I
Son usados por buscadores como Google y Yahoo!.
I
Uno de sus grandes desaf´ıos es unir e intersectar listas.
I
Y en eso son utiles los resultados que vimos para ´ relaciones binarias.
I
Pero no todo se puede resolver con ´ındices invertidos. ´ “lenguaje natural” implica muchas La expresion suposiciones:
I
I I
I
I
´ El texto se puede cortar automaticamente en “palabras”. ´ querra´ buscar palabras o secuencias de El usuario solo palabras. El conjunto de palabras distintas (vocabulario) crece sublinealmente con n (ley de Heaps). Las frecuencias de las palabras se distribuyen muy desigualmente (leyes de Zipf o Mandelbrot). G. Navarro
Estructuras de Datos Compactas
´ de Secuencias Textos: Otra Vision I
“Lenguaje natural” excluye lenguajes muy naturales como ´ coreano... el chino, japones,
I
´ y ... e incluso occidentales (aglutinantes) como aleman ´ finlandes! Hay secuencias donde no existe el concepto de palabra en absoluto:
I
I I I
I
´ Secuencias biologicas (ADN o prote´ınas). Secuencias musicales (valores de pitch en archivos MIDI). ˜ Senales discretizadas.
Hay otras donde podr´ıan definirse palabras, pero no ´ palabras, o no siguen las leyes: interesa buscar solo I I
´ ´ Codigo fuente en lenguajes de programacion. ´ ´ Secuencias numericas o de codigos de algun ´ tipo.
G. Navarro
Estructuras de Datos Compactas
Arboles y Arreglos de Sufijos
I
´ potente que los Veremos un tipo de ´ındice mucho mas ´ındices invertidos. ´ sobre el texto. No hacen ninguna suposicion
I
Permiten buscar cualquier substring del texto.
I
Modelo general: considerar los n sufijos T [i, n] de T .
I
Todo substring de T es el prefijo de un sufijo de T .
I
Estas estructuras indexan el conjunto de sufijos de T y permiten encontrar todos los que comparten un cierto prefijo.
I
G. Navarro
Estructuras de Datos Compactas
Arboles y Arreglos de Sufijos
Arbol de Sufijos I
´ Es un arbol digital que contiene todos los sufijos de T .
I I
Consideraremos que T termina con un s´ımbolo especial $. ´ Cada hoja del arbol corresponde a un sufijo distinto de T .
I
Y cada nodo interno a un substring repetido de T .
I
Se comprimen caminos unarios para garantizar O(n log n) bits.
I
Se puede construir en tiempo O(n) si σ = O(n) es discreto.
G. Navarro
Estructuras de Datos Compactas
r
$ 21
d
_
r
r
alabar a la alabarda$ _ 1
G. Navarro
_ 4
bar
laba
_ d 3 15
_ 10
_ d 5 17
bar
_ 7
l 20 $_ a l 9 l 11 12 8
18
_ 6
ba r
a
la
19
a
d
d 16
d 13
Estructuras de Datos Compactas
_ 2
d 14
Arboles y Arreglos de Sufijos
I
´ Para buscar P, se intenta bajar en el arbol usando sus caracteres. I
I
I
I I
´ Si agoto P en una arista, el subarbol que desciende agrupa todas las ocurrencias de P. Si no puedo bajar por un cierto P[i], entonces P no aparece en T . Si llego a una hoja, hay a lo sumo una ocurrencia, que debo terminar de verificar en T .
Cuenta en tiempo O(m), ubica en tiempo O(m + occ). ´ complejos. Puede resolver muchos otros problemas mas
G. Navarro
Estructuras de Datos Compactas
Arboles y Arreglos de Sufijos I
´ ´ El arbol de sufijos es una de las estructuras de datos mas elegantes y utiles, pero ocupa much´ısimo espacio. ´
I
I
Puede requerir de 10n a 20n bytes, por ejemplo 30-60 GB para el genoma humano. ´ bastante exitosa para reducir su espacio es Una solucion el arreglo de sufijos. ´ Este es el arreglo de las hojas del arbol de sufijos.
I
´ ´ Con las tecnicas para representar arboles...
I
´ ... podemos representar el arbol de sufijos como
I
I I I
I
El arreglo de sufijos. ´ ´ 2n parentesis para la estructura de arbol. ´ que se desee. El espacio extra para la navegacion
´ comprimir el arreglo de sufijos. Por lo tanto, tiene interes
G. Navarro
Estructuras de Datos Compactas
r
$ 21
r
19
laba
_ 4
r
_ d 3 15
_ 1
_ _ 10 d 16
18 6
bar
_d 5 17
bar
_ 7
a
l 20 $_ a l 9 11 l 12 8
d
la
bar
a
d
_
_ 2
d 14
d 13
(()((()())())(()(()())(()())(()())(()()))(()())()(()(()()))(()())) alabar a la alabarda$
bar
21 7 12 9 20 11 8 3 15 1 13 5 17 4 16 19 10 2 14 6 18
G. Navarro
Estructuras de Datos Compactas
Arboles y Arreglos de Sufijos Arreglo de Sufijos I
´ puede funcionar sin el arbol. ´ Un arreglo de sufijos tambien I I I
´ No puede hacer todo lo que un arbol de sufijos. Pero s´ı puede buscar patrones, en tiempo O(m log n + occ), ... y varias otras cosas.
I
´ Todo subarbol del arbol de sufijos corresponde a un intervalo del arreglo de sufijos.
I
Se puede hacer una busqueda binaria de los sufijos que ´ empiezan con P.
I
El rango resultante contiene todas las respuestas... ´ ... y corresponde al subarbol que habr´ıamos encontrado ´ en el arbol de sufijos.
I
G. Navarro
Estructuras de Datos Compactas
bar 21 7 12 9 20 11 8 3 15 1 13 5 17 4 16 19 10 2 14 6 18
al abar
a
G. Navarro
l a
al abar da$
Estructuras de Datos Compactas
Arboles y Arreglos de Sufijos
I
Aun ´ solo, el arreglo de sufijos presenta problemas de espacio.
I I
Ocupa unos 4n bytes (12GB para el genoma humano). ´ comprimirlo. Nuevamente, es de interes
I
´ Pero... ¿se puede comprimir una permutacion?.
G. Navarro
Estructuras de Datos Compactas
Parte II: Otras Estructuras
G. Navarro
Estructuras de Datos Compactas
El Arreglo de Sufijos Comprimido I I
´ Un arreglo de sufijos no es cualquier permutacion. n ´ σ arreglos de Hay n! permutaciones posibles pero solo sufijos posibles.
I
´ ¿Como se refleja la compresibilidad de un texto en su arreglo de sufijos?
I
¿De que´ tipo de compresibilidad de textos estamos hablando?
I
´ Concentremosnos en una que es importante en la ´ practica: entrop´ıa de orden k. I
I
˜ de alfabeto y sesgo en la Orden cero captura tamano frecuencia de los s´ımbolos. Ordenes mayores capturan la predictibilidad del texto que sigue en base a lo que lo precede.
G. Navarro
Estructuras de Datos Compactas
El Arreglo de Sufijos Comprimido ´ Ψ La funcion I I
I
Llamemos A[1, n] al arreglo de sufijos de T [1, n]. ´ y A−1 como Podemos pensar en A como una permutacion su inversa. ´ Ψ(1..n) como Definiremos una funcion Ψ(i) = A−1 [A[i] + 1] (con el caso especial Ψ(i) = A−1 [1] si A[i] = n).
I
Dicho de otro modo, A[Ψ(i)] = A[i] + 1.
I
Dada una celda A[i] que apunta al sufijo T [A[i] . . .], Ψ dice ´ donde esta´ en A el puntero al siguiente sufijo.
G. Navarro
Estructuras de Datos Compactas
Ψ
10 7 11 17 1 3 4 14 15 18 19 20 21 12 13 5 6 8 9 2 16 1
2
3
4
5
6
7
8
9
10
11 12
13
14
15
16
17
18
19
20
21
A 21 7 12 9 20 11 8 3 15 1 13 5 17 4 16 19 10 2 14 6 18 D
1 1 0 0 1 0 0 0
S
$ _ a b d l r
0 0 0 0 0 1 0 1 1 0 0 1 0
al abar
G. Navarro
a
l a
al abar da$
Estructuras de Datos Compactas
El Arreglo de Sufijos Comprimido I
´ C(1..σ) como Definamos la funcion C(c) = cantidad de ocurrencias de s´ımbolos < c en T
I
Implementemos C con I
I
I I
Un bitmap D[1, n], con D[1] = 1 y D[C(c) + 1] = 1 para todo c ∈ Σ. Una lista S[1, σ] de los distintos caracteres que aparecen ´ en T , en orden alfabetico.
D y S se pueden representar con O(σ log n) bits. ´ que realmente me interesara´ es La operacion c = S[rank(D, i)] es decir, con que´ caracter comienza T [A[i]].
G. Navarro
Estructuras de Datos Compactas
El Arreglo de Sufijos Comprimido
I I
´ Veamos como extraer T [A[i] . . .] sin A ni T ... ... sino con D, S y Ψ. I I I I
T [A[i]] es S[rank (D, i)]. T [A[i] + 1] = T [A[Ψ(i)] es S[rank(D, Ψ(i))]. T [A[i] + 2] = T [A[Ψ2 (i)] es S[rank (D, Ψ2 (i))]. ...
I
Podemos implementar la busqueda binaria en el mismo ´ tiempo.
I
Podemos contar en tiempo O(m log n).
I
Pero... Ψ es tan grande como A!
G. Navarro
Estructuras de Datos Compactas
El Arreglo de Sufijos Comprimido I
Ψ es compresible cuando T es compresible.
I
En la zona de A donde los sufijos comienzan con la misma letra, Ψ es creciente.
I
Por lo tanto Ψ consiste de σ listas crecientes.
I
Con bitmaps comprimidos se pueden representar usando X c∈Σ
I I
nc log
n + O(n) + o(σn) = nH0 (T ) + O(n) + o(σn) bits nc
Con D tenemos acceso en tiempo constante a Ψ. ´ debemos sumar los O(σ log n) bits de D y S, pero Ademas eso normalmente puede ignorarse.
G. Navarro
Estructuras de Datos Compactas
El Arreglo de Sufijos Comprimido
I
El problema es el espacio extra o(σn).
I
Lo podemos convertir en O(n log log σ) usando ´ delta. codificacion ´ gama de un numero Comencemos con la codificacion x: ´
I
I I I
Codificamos |x| en unario. Luego codificamos x en binario Por ejemplo x = 20 = 10100 se codifica como 10000 10100
I
´ El codigo necesita 2dlog(x + 1)e bits.
G. Navarro
Estructuras de Datos Compactas
El Arreglo de Sufijos Comprimido
I
´ El codigo delta funciona as´ı: I I I
I
´ Codificamos |x| con codigo gama. Luego codificamos x en binario Por ejemplo x = 20 = 10100 (|x| = 5 = 101) se codifica como 100 101 10100 ´ El codigo necesita dlog(x + 1)e + 2dlog(dlog(x + 1)e + 1)e bits.
G. Navarro
Estructuras de Datos Compactas
El Arreglo de Sufijos Comprimido I
Si codificamos Ψ(i) − Ψ(i − 1) en las zonas crecientes ´ usando codigos delta, obtenemos nH0 (T ) + O(n log log σ) bits.
I
Agregamos valores absolutos cada O(log n) bits (agrega O(n) bits).
I
Y con eso podemos decodificar cualquier Ψ(i) en tiempo constante. Notar que:
I
I I
I
No necesitamos A ni T . Aun ´ podemos contar en tiempo O(m log n).
´ aun... Pero Ψ se puede comprimir mas ´
G. Navarro
Estructuras de Datos Compactas
El Arreglo de Sufijos Comprimido
I
Si una cadena abcd se repite frecuentemente en T ... habra´ una zona en A con los punteros que apuntan a las a y otra con los punteros que apuntan a las b... ´ los mismos de las a desplazados en 1. ... que seran
I
Estas seudo-copias en A se llaman runs.
I
Un run se ve en Ψ como una secuencia de valores consecutivos.
I
Codificando los runs en forma especial, nos acercamos a la entrop´ıa de orden superior. Todo esta´ muy bien, pero
I I
I
I I
¿Podemos ubicar las ocurrencias, si no tenemos A? ¿Podemos mostrar una parte del texto, si no tenemos T ?
G. Navarro
Estructuras de Datos Compactas
Ψ
10 7 11 17 1 3 4 14 15 18 19 20 21 12 13 5 6 8 9 2 16 1
2
3
4
5
6
7
8
9
10
11 12
13
14
15
16
17
18
19
20
21
A 21 7 12 9 20 11 8 3 15 1 13 5 17 4 16 19 10 2 14 6 18
al abar
a
G. Navarro
l a
al abar da$
Estructuras de Datos Compactas
El Arreglo de Sufijos Comprimido
I
Haremos un sampling de celdas de A y las almacenaremos.
I
Tomaremos los A[i] que apuntan a posiciones de T multiplos de b. ´
I
Los almacenaremos en orden creciente de i en forma contigua, en un arreglo A0 [1, n/b].
I
... y tendremos un bitmap B[1, n] marcando los i sampleados. ´ O( bn log n) bits. Las posiciones y el bitmap ocuparan
I
G. Navarro
Estructuras de Datos Compactas
El Arreglo de Sufijos Comprimido
I
Supongamos que queremos conocer A[i] (pero no tenemos A). I I
I I
Si B[i] = 1, A[i] = A0 [rank (B, i)]. Sino, si B[Ψ(i)] = 1, A[Ψ(i)] = A0 [rank (B, Ψ(i))], A[i] = A[Ψ(i)] − 1. Sino, ... Si B[Ψt (i)] = 1, A[i] = A0 [rank (B, Ψt (i))] − t.
I
Esto debe terminar en a lo sumo b pasos.
I
Por lo tanto podemos conocer A[i] en tiempo O(b).
I
Por ejemplo, en tiempo O(log n), gastando O(n) bits extra.
I
Ahora s´ı hemos reemplazado al suffix array!
G. Navarro
Estructuras de Datos Compactas
Ψ
10 7 11 17 1 3 4 14 15 18 19 20 21 12 13 5 6 8 9 2 16 1
2
3
4
5
6
7
8
9
10
11 12
13
14
15
16
17
18
19
20
21
A 21 7 12 9 20 11 8 3 15 1 13 5 17 4 16 19 10 2 14 6 18 B
1 0 0 0 0 1 0 0
0 1 0 0 0 0 1 0 0 0 0 1 0
A’ 21 11 1 16 6 E 10 20 6 15 1
al abar
G. Navarro
a
l a
al abar da$
Estructuras de Datos Compactas
El Arreglo de Sufijos Comprimido I
Ahora almacenaremos el mismo sampling de otra forma.
I
Almacenaremos los valores i en orden creciente de T , en E[1, n/b]. Supongamos que queremos conocer T [l, r ] (pero no tenemos T ).
I
I I I I I I
´ sampleada es l 0 = 1 + bl/bc · b. La ultima posicion ´ Y es apuntada desde A[i] = A[E[1 + bl/bc]]. Sabemos que T [l 0 ] = S[rank(D, i)]. Sabemos que T [l 0 + 1] = S[rank (D, Ψ(i))]. ... 0 Sabemos que T [r ] = S[rank (D, Ψr −l +1 (i))].
I
El costo total es O(b + r − l).
I
Por ejemplo, en tiempo O(r − l + log n), gastando O(n) bits extra.
I
Ahora s´ı hemos reemplazado al texto! G. Navarro
Estructuras de Datos Compactas
El Arreglo de Sufijos Comprimido I
Todas las estructuras suman nH0 (T ) + O(n log log σ) bits.
I
Se puede probar que realmente suman nHk (T ) + O(n log log σ) bits para k moderado.
I
Permiten contar en tiempo O(m log n).
I
Permiten ubicar cada ocurrencia en tiempo O(log n).
I
Permiten mostrar T [l, r ] en tiempo O(r − l + log n).
I
´ Estas estructuras reemplazan el suffix array pero tambien reemplazan el texto! Cuando logramos esto, tenemos un auto-´ındice comprimido.
I
I I I
Representa el texto. Permite busqueda indexada. ´ Ocupa espacio cercano al del texto comprimido.
G. Navarro
Estructuras de Datos Compactas
Parte II: Otras Estructuras
G. Navarro
Estructuras de Datos Compactas
´ de Burrows-Wheeler (BWT) La Transformacion
I
´ reversible de T . Es una permutacion
I
´ Se usa como paso previo a algoritmos de compresion como bzip2.
I
Pone juntos caracteres que tienen el mismo contexto.
I
Basta comprimir esos “caracteres juntos” a orden cero para obtener nHk (T ). ´ deriva en un ´ındice comprimido para Veremos que ademas texto.
I
G. Navarro
Estructuras de Datos Compactas
´ de Burrows-Wheeler (BWT) La Transformacion I I I I I
Tomamos todos los shifts c´ıclicos de T . Es decir, ti ti+1 . . . tn−1 $t1 t2 . . . ti−1 . El resultado es una matriz M de n × n caracteres. ´ Ordenamos las filas lexicograficamente. M es esencialmente la lista de los sufijos de T en orden: M[i] = T [A[i] . . . n] · T [1 . . . A[i] − 1]
I
I I
La primera columna, F , tiene los primeros caracteres de los sufijos: F [i] = S[rank(D, i)]. La ultima columna, L, es la BWT de T , T bwt = L. ´ Es la secuencia de los caracteres que preceden a los sufijos T [A[i]..]. L[i] = T bwt [i] = T [A[i] − 1] (excepto si A[i] = 1, donde T bwt = T [n] = $). G. Navarro
Estructuras de Datos Compactas
A 21 7 12 9 20 11 8 3 15 1 13 5 17 4 16 19 10 2 14 6 18
alabar a la alabarda$ labar a la alabarda$a abar a la alabarda$al bar a la alabarda$ala ar a la alabarda$alab r a la alabarda$alaba a la alabarda$alabar a la alabarda$alabar la alabarda$alabar a la alabarda$alabar a a alabarda$alabar a l alabarda$alabar a la alabarda$alabar a la labarda$alabar a la a abarda$alabar a la al barda$alabar a la ala arda$alabar a la alab rda$alabar a la alaba da$alabar a la alabar a$alabar a la alabard $alabar a la alabarda
$alabar a la alabarda a la alabarda$alabar alabarda$alabar a la la alabarda$alabar a a$alabar a la alabard a alabarda$alabar a l a la alabarda$alabar abar a la alabarda$al abarda$alabar a la al alabar a la alabarda$ alabarda$alabar a la ar a la alabarda$alab arda$alabar a la alab bar a la alabarda$ala barda$alabar a la ala da$alabar a la alabar la alabarda$alabar a labar a la alabarda$a labarda$alabar a la a r a la alabarda$alaba rda$alabar a la alaba
G. Navarro
1era "a"
T
alabar a la alabarda$
1era "d"
T
bwt
araadl ll$ bbaar aaaa
2nda "r"
9na "a"
Estructuras de Datos Compactas
´ de Burrows-Wheeler (BWT) La Transformacion I
´ ¿Como invertir la BWT?
I
Para todo i, T = . . . L[i]F [i] . . ..
I
Sabemos que L[1] = T [n − 1], pues F [1] = $ = T [n]. ´ ¿Donde esta´ c = L[1] en F ? Todas las ocurrencias de c aparecen en el mismo orden en F y L:
I I
I
Es el orden dado por el sufijo que sigue a c en T .
I
Sea entonces j = rankc (L, i). Ese c esta´ en F [C(c) + j].
I
Se llama LF-mapping, pues lleva de la columna L a la F :
I
LF (i) = C(L[i]) + rankL[i] (L, i) I
Entonces T [n − 2] = F [LF (1)] = S[rank(D, LF (1))].
I
Y T [n − 3] = F [LF (LF (1))], etc. G. Navarro
Estructuras de Datos Compactas
El FM-Index I
Usaremos el paralelo entre el arreglo de sufijos y la BWT.
I
Reemplazaremos la busqueda binaria por la busqueda ´ ´ ´ ´ hacia atras, mas eficiente.
I
Para buscar P[1, m] comenzaremos por pm .
I
El segmento de A que le corresponde es A[C(pm ) + 1, C(pm + 1)].
I
En general, sabremos que las ocurrencias de P[i + 1, m] comienzan en A[spi+1 , epi+1 ]...
I
... y usaremos algo similar al LF-mapping para obtener la zona A[spi , epi ] correspondiente a P[i, m].
I
Terminaremos con sp1 y ep1 .
G. Navarro
Estructuras de Datos Compactas
El FM-Index I
I
Supongamos que conocemos el segmento A[spi+1 , epi+1 ] de las ocurrencias de P[i + 1, m]. ´ ¿Como lo actualizamos a las ocurrencias de P[i, m]? I I
I
I
Para un spi+1 ≤ j ≤ epi+1 , M[j][1..m − i] = P[i + 1, m]. Las ocurrencias de P[i, m] en T aparecen como L[j] = pi ´ en esa area, pues T = . . . L[j] · M[j][1..m − i] . . . Por lo tanto la respuesta es el rango de los LF (j) donde L[j] = pi .
Eso se calcula simplemente como spi
= C(pi ) + rankpi (L, spi+1 − 1) + 1
epi
= C(pi ) + rankpi (L, epi+1 )
G. Navarro
Estructuras de Datos Compactas
araadl ll$ bbaar aaaa
C(_)=1 C(a)=4 C(b)=13 C(d)=15 C(l)=16 C(r)=19
G. Navarro
$ _ _ _ a a a a a a a a a b b d l l l r r
a r a a d l _ l l $ _ b b a a r _ a a a a
3 15 1 13 5 17 4 16 19 10 2 14 6 18
C($)=0
L
21 7 12 9 20 11 8
bwt
T
A
T alabar a la alabarda$
F
b
Estructuras de Datos Compactas
a
r
El FM-Index
I
Luego de m iteraciones, tenemos el intervalo de P[1, m].
I
El costo son 2m invocaciones de rankc . Usando un wavelet tree sobre T bwt = L,
I
I I
I
Obtenemos espacio nH0 (T ) + o(n log σ). Contamos en tiempo O(m(1 + logloglogσ n )).
El espacio nH0 (T ) se puede mejorar a nHk (T ): I
I I
Particionando L en bloques que comparten el mismo prefijo M[j][1, k ]. ´ Particionando L en forma optima (vale para todo k ). Usando bitmaps comprimidos en el wavelet tree, lo que da ´ nHk (T ) automaticamente para todo k .
G. Navarro
Estructuras de Datos Compactas
a = 0, rank0(16) = 10
ar aadl _ l l $_bbaar_ aaaa 010011011000000100000 $_ab
dlr
a = 1, rank1(10) = 7
aaa_$_bbaa_aaaa 111000111101111 ab
$_
r
dl
a = 0, rank0(7) = 5
_$__ 1011 $
r dl l l r 100001
aaabbaaaaaa 00011000000 _
a
b
dl l l 0111 d
l
rank = 5
G. Navarro
Estructuras de Datos Compactas
El FM-Index
I
I
Para obtener A[i] y T [l, r ] usamos el mismo mecanismo de sampling. Para conservar o(n log σ) espacio extra, I I I
I I
Sampleamos cada b = logσ n log log n. Ubicamos cada ocurrencia en tiempo O(log n log log n). Mostramos texto en O((b + r − l)(1 + logloglogσ n )).
Es uno de los mejores ´ındices en la teor´ıa. ´ ´ pero el suffix array comprimido es En la practica tambien, ´ muy competitivo tambien.
G. Navarro
Estructuras de Datos Compactas
Parte II: Otras Estructuras
G. Navarro
Estructuras de Datos Compactas
Indices tipo Lempel-Ziv
I
I
I I I
´ basado en sustituir Lempel-Ziv es un tipo de compresion cadenas de T por punteros a sus apariciones previas. ´ repetitivo es un texto, mas ´ se puede Cuanto mas reemplazar y mejor se comprime. Los compresores zip, gzip, pkzip, arj, etc. son de este tipo. Nos interesara´ un tipo particular llamado LZ78. Veremos que tiene propiedades que permiten indexar el texto comprimido.
G. Navarro
Estructuras de Datos Compactas
Indices tipo Lempel-Ziv ´ LZ78 Compresion I
Cortamos el texto en frases.
I
´ larga posible y Cada frase consiste en la frase previa mas una letra adicional.
I
Todas las frases son distintas.
I
´ Se almacenan todas las frases en un arbol digital, donde cada nodo es una frase.
I
En el peor caso se forman n0 ≤ n/ logσ n frases en T .
I
Representando cada frase con log n bits el total queda nHk (T ) + o(n log σ) para k = o(logσ n).
G. Navarro
Estructuras de Datos Compactas
a.l.ab.ar. .a .la. a.lab.ard.a$ 0 _ 5
1 $
a 8
l
a
11
_
2 b
6
r
a
3
4 d 10
G. Navarro
7 b 9
Estructuras de Datos Compactas
Indices tipo Lempel-Ziv El LZ-Index I
El LZ-Index almacena varias componentes: I
I
I I I
I
I
´ ´ ´ los LZTrie: el arbol de las frases, como 2n0 parentesis mas numeros de frases en preorden (Ids). ´ ´ RevTrie: el arbol de las frases reversas, como 4n0 ´ ´ los numeros parentesis mas de frase en preorden (RIds). ´ Node: el mapeo de numero de frase a nodos de LZTrie. ´ RNode: el mapeo de numero de frase a nodos de RevTrie. ´ Range: puntos en dos dimensiones: (preordenRev (j), preordenLZ (j + 1)) para cada frase j.
Con esas estructuras puede ubicar las ocurrencias en tiempo O(m2 log m + (m + occ) log n). ´ En la practica el conteo es muy lento, pero ubicar las ´ ocurrencias es rapido.
G. Navarro
Estructuras de Datos Compactas
a.l.ab.ar. .a .la. a.lab.ard.a$ LZTrie
RevTrie 0
0 _
a
5
1 $
a 8
11
_ 6
3
a 4 d 10
a
5
2 b r
r
$ _
l
7 b 9
G. Navarro
a 11
6
d
l
1
2
_ l
a
b
8
a 7
a
r
3 l 9
4 a 10
Estructuras de Datos Compactas
$a _ _a a a_ al ba bal dra l ra
a.l.ab.ar. .a .la. a.lab.ard.a$
_ _a a a$ a_ ab ar ard l la lab
4 7 10 5 2 3 9 1 6 8
G. Navarro
Estructuras de Datos Compactas
Indices tipo Lempel-Ziv
I
Tres tipos de ocurrencias a encontrar: I I I
Tipo 1: P esta´ totalmente contenido en una frase. Tipo 2: P traslapa con dos frases consecutivas. ´ Tipo 3: P abarca tres frases o mas.
frases LZ78 1
2
P dentro de una frase
3
P traslapa 2 frases
G. Navarro
4
5 6
7
P abarca 4 frases
Estructuras de Datos Compactas
Indices tipo Lempel-Ziv Ocurrencias tipo 1 I
Si una frase B contiene P pero no termina en P... ´ ... y dado que B = B 0 · c para otra frase B 0 y caracter c...
I
´ ... se deduce que P esta´ contenido en B 0 tambien.
I
Buscamos P R en RevTrie para hallar todas las frases que terminan con P.
I
Para cada una de esas posiciones en preorden j de ´ en el LZTrie. RevTrie, Node(Rids(j)) es la posicion
I I
Todos los descendientes de ese nodo son ocurrencias. ´ Recorremos el subarbol de LZTrie reportando los Ids.
I
´ O(1) por cada ocurrencia. Tardamos O(m) mas
I
G. Navarro
Estructuras de Datos Compactas
Indices tipo Lempel-Ziv Ocurrencias tipo 2 I
Si P comienza en la frase Bj y termina en Bj+1 ...
I
... entonces Bj termina con P[1, i] y Bj+1 empieza con P[i + 1, m] para algun ´ i.
I
Buscamos cada P[i + 1, m] en LZTrie, obteniendo el rango ´ de preordenes [xi , xi0 ].
I
Buscamos cada P[1, i]R en RevTrie, obteniendo el rango ´ de preordenes [yi , yi0 ].
I
Reportamos todos los puntos de Range en [xi , xi0 ] × [yi , yi0 ]. ´ O(log n) por ocurrencia. El tiempo es O(m2 + m log n) mas
I
G. Navarro
Estructuras de Datos Compactas
Indices tipo Lempel-Ziv
Ocurrencias tipo 3 I
´ de 2 frases, entonces contiene Si P abarca mas completamente una frase.
I
Como todas las frases del parsing LZ78 son distintas...
I
... existen a lo sumo O(m2 ) ocurrencias que verificar en T .
I
Se pueden verificar en tiempo O(m2 log m) usando Node y RNode.
G. Navarro
Estructuras de Datos Compactas
Indices tipo Lempel-Ziv I
Ids y Node son permutaciones inversas.
I
RIds y RNode son permutaciones inversas.
I
Por lo tanto, cada par ocupa (1 + )n log n bits.
I
La estructura de Range ocupa n log n bits.
I
En total el espacio es (3 + )nHk (T ) + o(n log σ), para cualquier constante .
I
Se puede eliminar Range para reducir el espacio a (2 + )nHk (T ) + o(n log σ)... ´ ... y los tiempos son mejores en la practica.
I I
Para eliminar Range se verifican todos los candidatos de ´ LZTrie en RevTrie (usando Ids y RNode) o al reves (usando RIds y Node).
I
El espacio se puede reducir incluso a (1 + )nHk (T ) + o(n log σ). G. Navarro
Estructuras de Datos Compactas
Comparando Indices para Texto Lenguaje Natural
time (microsecs per occurrence)
english 30 25 Arreglo de Sufijos Comprimido FM-Index con Wavelet Tree FM-Index particionado LZ-Index
20 15 10 5 0 0
0.5 1 1.5 2 Space usage (fraction of text)
2.5
´ Datos obtenidos por Rodrigo Gonzalez y Rossano Venturini con los archivos del sitio http://pizzachili.dcc.uchile.cl
G. Navarro
Estructuras de Datos Compactas
Comparando Indices para Texto ´ Codigo Fuente
time (microsecs per occurrence)
sources 30 25 Arreglo de Sufijos Comprimido FM-Index con Wavelet Tree FM-Index particionado LZ-Index
20 15 10 5 0 0
0.5 1 1.5 2 Space usage (fraction of text)
2.5
´ Datos obtenidos por Rodrigo Gonzalez y Rossano Venturini con los archivos del sitio http://pizzachili.dcc.uchile.cl
G. Navarro
Estructuras de Datos Compactas
Comparando Indices para Texto Texto Semiestructurado
time (microsecs per occurrence)
xml 30 25 Arreglo de Sufijos Comprimido FM-Index con Wavelet Tree FM-Index particionado LZ-Index
20 15 10 5 0 0
0.5 1 1.5 2 Space usage (fraction of text)
2.5
´ Datos obtenidos por Rodrigo Gonzalez y Rossano Venturini con los archivos del sitio http://pizzachili.dcc.uchile.cl
G. Navarro
Estructuras de Datos Compactas
Comparando Indices para Texto ADN
time (microsecs per occurrence)
dna 30 25 Arreglo de Sufijos Comprimido FM-Index con Wavelet Tree FM-Index particionado LZ-Index
20 15 10 5 0 0
0.5 1 1.5 2 Space usage (fraction of text)
2.5
´ Datos obtenidos por Rodrigo Gonzalez y Rossano Venturini con los archivos del sitio http://pizzachili.dcc.uchile.cl
G. Navarro
Estructuras de Datos Compactas
Parte II: Otras Estructuras
G. Navarro
Estructuras de Datos Compactas
Grafos I
Un conjunto de n nodos y e aristas.
I
Las aristas son flechas que van de un nodo a otro.
I
´ por Los vecinos de un nodo son los alcanzables desde el una flecha. ´ por una Los vecinos reversos son los que llegan a el flecha.
I
I
I
Nos interesa navegar de un nodo a sus vecinos o vecinos reversos. Y otras preguntas como I I I
¿Existe una arista de un cierto nodo a cierto otro nodo? ´ Grado interior: ¿cuantas aristas llegan a un nodo? ´ Grado exterior: ¿cuantas aristas salen de un nodo?
G. Navarro
Estructuras de Datos Compactas
Grafos
I I
Nos interesaremos especialmente en los grafos de la Web. Se necesita correr algoritmos sobre grandes subconjuntos de la Web. I I I I
I I
Para calcular PageRank (Google). Para descubrir comunidades (Yahoo!). ´ Para analisis de redes sociales. Y muchas otras aplicaciones.
Esos algoritmos no corren bien en memoria secundaria. ´ compacta navegable permitira´ Una representacion ´ grandes en RAM. analizar grafos mas
G. Navarro
Estructuras de Datos Compactas
´ Clasica ´ Representacion de Grafos Matriz de Incidencia a b
b
c d
e
a b
a
c d e
c
d e
G. Navarro
Estructuras de Datos Compactas
´ Clasica ´ Representacion de Grafos
Matriz de Incidencia I
Con n nodos y e aristas, ocupa n2 bits.
I
Responde existencia en tiempo O(1).
I
Encuentra todos los vecinos directos/reversos en O(n).
I
Calcula grado interior/exterior en O(n).
G. Navarro
Estructuras de Datos Compactas
´ Clasica ´ Representacion de Grafos
Lista de Adyacencia b
a: d,c,b
a: b
b: d,c,a
b: a
c: d
c: a,b,e
d:
d: a,b,c,e
e: d,c
e:
a
c
d e
G. Navarro
Estructuras de Datos Compactas
´ Clasica ´ Representacion de Grafos
Lista de Adyacencia I
Con n nodos y e aristas, ocupa n log e + e log n bits.
I
Encuentra cada vecino en tiempo O(1).
I
Calcula grado exterior en tiempo O(1).
I
Responde existencia en tiempo O(n).
I
Necesita otro tanto para los reversos.
G. Navarro
Estructuras de Datos Compactas
´ de Grafos Compresion
I
´ ´ binaria entre nodos... Viendolo como una relacion
I
... se puede conseguir e log(n2 /e) (1 + o(1)) bits...
I
... y responder todo en tiempo O(log log n).
I
Obtiene lo mejor de los dos mundos...
I
... pero aun ´ no es demasiado bueno para la Web.
G. Navarro
Estructuras de Datos Compactas
´ de Grafos Representacion
Algunos ejemplos sobre grafos Web Medidos en bpe (bits por arista). Grafo UK EU Arabic Indochina
n 18.5M 860K 23M 7M
e 298M 19M 640M 194M
G. Navarro
Matriz 1.15M 39K 827K 253K
Lista 25.89 20.81 25.51 23.73
2 x Lista 51.78 41.62 51.02 47.46
Estructuras de Datos Compactas
Rel. Bin 20.13 15.25 19.66 17.95
´ de Grafos Compresion
Grafos Planares y Variantes I I
Con n nodos, tienen O(n) aristas. ´ Distintas tecnicas para comprimirlos a O(n) bits.
I
´ La mayor´ıa consiste en dividirlos en varios arboles y ´ ´ representar estos arboles como parentesis.
I
Algunas permiten acceso directo.
I
Hay algunos resultados para tipos especiales de grafos.
I
Es improbable que tengan algun ´ impacto en grafos Web.
G. Navarro
Estructuras de Datos Compactas
´ de Grafos Compresion
Separadores de Grafos I
Encontrar zonas que se pueden desconectar cortando unas pocas aristas.
I I
Renumerar los nodos y comprimirlos separadamente. ´ rapidos ´ Pueden obtener 13–16 bpe y ser mas que la ´ descomprimida (por efectos de cache). ´ version
I
Para vecinos reversos necesitan el grafo traspuesto.
G. Navarro
Estructuras de Datos Compactas
´ de Grafos Web Compresion
I
´ sesgada de grados interior/exterior (power Distribucion laws). I
I
Localidad de referencia: la mayor´ıa de los links apuntan al mismo site. I I
I
Una lista de adyacencia tiene baja entrop´ıa.
´ Listar los nodos en orden lexicografico de URL. ´ ´ de gaps para comprimir las Usar tecnicas de codificacion listas.
Modelo de copia: los links que salen se parecen a los de ´ alguna otra pagina. I
´ Encontrar una pagina similar y codificar diferencialmente.
G. Navarro
Estructuras de Datos Compactas
´ de Grafos Web Compresion
Un muy buen exponente: WebGraph I
´ pura. 3 bpe para compresion
I
6 bpe para recuperar cada vecino directo o reverso dentro del microsegundo.
I
Esto considera el grafo y su traspuesto.
G. Navarro
Estructuras de Datos Compactas
Parte II: Otras Estructuras
G. Navarro
Estructuras de Datos Compactas
Comprimiendo Grafos como Texto
I
Concatenar las listas de adyacencia en un texto.
I
Construir un auto´ındice comprimido sobre ese texto.
I
Mostrar: vecinos de un nodo
I
Ubicar: vecinos reversos de un nodo
I
Contar: grado interior de un nodo
I
La entrop´ıa de orden k de este texto captura el modelo de copia. ´ sesgada La entrop´ıa de orden cero captura la distribucion de grado interior.
I
G. Navarro
Estructuras de Datos Compactas
´ Experimental Comparacion
I
Usando el Arreglo de Sufijos Comprimido como auto´ındice.
I
Contra los resultados de WebGraph.
I
Sobre el mismo crawl UK, 18.5 Mnodos, 292 Mlinks.
I
Vecinos: resultados comparables.
I
Reversos: WebGraph el 10 veces mejor.
G. Navarro
Estructuras de Datos Compactas
Retrieving neighbors
time per neighbor (ms)
2
CSA WG WG (fwd)
1.8 1.6 1.4 1.2 1 0.8 0.6 2
4
6
8 10 space (bpe)
G. Navarro
12
14
16
Estructuras de Datos Compactas
Retrieving reverse neighbors
time per neighbor (ms)
30
CSA WG
25 20 15 10 5 0 6
7
8
9
10 11 12 space (bpe)
G. Navarro
13
14
15
Estructuras de Datos Compactas
Parte II: Otras Estructuras
G. Navarro
Estructuras de Datos Compactas
Comprimiendo con Re-Pair
I I
Hay una forma elegante y efectiva de comprimir T ? ´ repetido en T y Re-Pair: encontrar el par mas reemplazarlo por un nuevo s´ımbolo, hasta que todos los pares sean unicos. ´
G. Navarro
Estructuras de Datos Compactas
Re-Pair
aaabcaabaaabcabdabd a a b c b d
a b c a d a
4 5 2 2 2 1
A
ab
a a Ac a Aa a Ac Ad Ad
G. Navarro
Estructuras de Datos Compactas
Re-Pair
a a Ac a Aa a Ac Ad Ad aa aA Ac ca Ad cA dA
2 3 2 1 2 1 1
A B
ab aA
a Bc Ba Bc Ad Ad
G. Navarro
Estructuras de Datos Compactas
Re-Pair
a Bc Ba Bc Ad Ad aB Bc cB Ba cA Ad dA
2 2 1 1 1 2 1
A B C
ab aA Ad
a Bc Ba Bc CC
G. Navarro
Estructuras de Datos Compactas
Re-Pair
a Bc Ba Bc CC aB Bc cB Ba cC CC
2 2 1 1 1 1
A B C D
ab aA Ad Bc
a DB a DC C
G. Navarro
Estructuras de Datos Compactas
Re-Pair
a DB a DC C aD DB Ba DC CC
2 1 1 1 1
EBECC
A B C D E
ab aA Ad Bc aD diccionario secuencia comprimida
G. Navarro
Estructuras de Datos Compactas
Re-Pair
I
´ Comprime bien, descomprime rapido.
I
Aprovecha la propiedad de copia.
I
Comprime mejor si se codifica T diferencialmente. Se comporta bien en memoria secundaria
I
I
I
Siempre que el diccionario quepa en RAM.
Se puede mejorar Re-Pair mismo: I
I I
Representar el diccionario con estructuras de datos compactas. Ganamos hasta un 50% en el espacio del diccionario. Esto es importante sobre todo en memoria secundaria.
G. Navarro
Estructuras de Datos Compactas
Mejorando Re-Pair
´ Figuras hechas por mi alumno Rodrigo Gonzalez.
G. Navarro
Estructuras de Datos Compactas
Mejorando Re-Pair
´ Figuras hechas por mi alumno Rodrigo Gonzalez.
G. Navarro
Estructuras de Datos Compactas
Mejorando Re-Pair
´ Figuras hechas por mi alumno Rodrigo Gonzalez.
G. Navarro
Estructuras de Datos Compactas
Resultados Experimentales UK: 18.5M nodos, 298M aristas UK Re-Pair Re-Pair (diffs) Plain Compact
0.0005
0.0004
time (mseg/edge)
time (mseg/edge)
0.0005
0.0003 0.0002 0.0001 0
UK
Re-Pair Re-Pair (diffs) WG WG-Memory
0.0004 0.0003 0.0002 0.0001
0
2
4
6 8 space (bits/edge)
10
12
0
0
5
10
15 20 25 space (bits/edge)
30
35
Resultados obtenidos por mi alumno Francisco Claude.
G. Navarro
Estructuras de Datos Compactas
Resultados Experimentales EU: 860K nodos, 19M aristas EU Re-Pair Re-Pair (diffs) Plain Compact
0.0005
0.0004
time (mseg/edge)
time (mseg/edge)
0.0005
0.0003 0.0002 0.0001 0
EU
Re-Pair Re-Pair (diffs) WG WG-Memory
0.0004 0.0003 0.0002 0.0001
0
2
4
6 8 10 space (bits/edge)
12
14
0
0
5
10
15 20 25 space (bits/edge)
30
35
Resultados obtenidos por mi alumno Francisco Claude.
G. Navarro
Estructuras de Datos Compactas
Resultados Experimentales Arabic: 23M nodos, 640M aristas Arabic Re-Pair Re-Pair (diffs) Plain Compact
0.0005
0.0004
time (mseg/edge)
time (mseg/edge)
0.0005
0.0003 0.0002 0.0001 0
Arabic
Re-Pair Re-Pair (diffs) WG WG-Memory
0.0004 0.0003 0.0002 0.0001
0
2
4 6 space (bits/edge)
8
10
0
0
5
10
15 20 25 space (bits/edge)
30
35
Resultados obtenidos por mi alumno Francisco Claude.
G. Navarro
Estructuras de Datos Compactas
Resultados Experimentales Indochina: 7M nodos, 194M aristas Indochina Re-Pair Re-Pair (diffs) Plain Compact
0.0005
0.0004
time (mseg/edge)
time (mseg/edge)
0.0005
0.0003 0.0002 0.0001 0
Indochina
Re-Pair Re-Pair (diffs) WG WG-Memory
0.0004 0.0003 0.0002 0.0001
0
2
4 6 space (bits/edge)
8
10
0
0
5
10
15 20 25 space (bits/edge)
30
35
Resultados obtenidos por mi alumno Francisco Claude.
G. Navarro
Estructuras de Datos Compactas
Desaf´ıo Actual I
Re-Pair obtiene 5–7 bpe y mejor compromiso tiempo/espacio que WebGraph.
I
Podr´ıamos tener operaciones reversas eficientes con 10–14 bpe. ´ ´ binaria sobre Re-Pair? Y si en vez tuvieramos la relacion
I
I I
I I
I
I
Cada s´ımbolo aparece de muchas formas distintas. Hay que partir por encontrar que´ s´ımbolos me representan en el diccionario (rank y select sobre S!). Vecinos y vecinos reversos: ok (O(1) por vecino). Grado exterior/interior eficientes con 1 bpe extra cada uno. (pero son compresibles a 0.17–0.25 bpe c/u). Existe: Muy caro.
´ abierto. Tema de investigacion
G. Navarro
Estructuras de Datos Compactas
Ep´ılogo I
I
I
I I
Las estructuras de datos compactas son un tema de ´ practico ´ interes para obtener implementaciones eficientes en los computadores modernos. ´ Son relevantes por las grandes cantidades de informacion a manejar y por la jerarqu´ıa de memoria. Combinan conceptos de algoritmos y estructuras de datos ´ y teor´ıa de la informacion. ´ con conceptos de compresion ´ Son un campo sumamente activo de investigacion. ´ esperando la contribucion ´ de jovenes ´ Y estan entusiastas y con talento!
⇒ G. Navarro
Estructuras de Datos Compactas
Copyright
´ se distribuye bajo la licencia Attribute — Esta presentacion Non-Commercial — No Derivs de Creative Commons http://creativecommons.org/licenses/by-nc-nd/3.0 Esto significa que usted puede distribuir y comunicar publicamente la obra, siempre que ´ I
´ De´ credito al autor de la obra.
I
No la use para fines comerciales.
I
No la altere, transforme, o genere una obra derivada. ´ El logo usado en esta presentacion es cortes´ıa de Jeremy Barbay, www.cs.uwaterloo.ca/∼jbarbay.
G. Navarro
Estructuras de Datos Compactas