Estructuras de Datos

Compactas
Gonzalo Navarro
[Link]/gnavarro
gnavarro@[Link]
(DCC)
Departamento de Ciencias de la Computacion
Universidad de Chile

Sponsors:

Mapa

Parte I: Secuencias
y Motivacion

Introduccion
La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos
Secuencias de Bits
Rank y Select, aplicaciones a Hashing, Sumas, Pred/Succ
Rank y Select sobre Secuencias Comprimidas

Secuencias Dinamicas,
aplicaciones a Sumas Parciales
Secuencias de Smbolos
Recurriendo a Secuencias de Bits
El Wavelet Tree, aplicaciones a Geometra y Relaciones
Revisitando las Secuencias de Bits
G. Navarro

Estructuras de Datos Compactas

Mapa

Parte I: Secuencias
y Motivacion

Introduccion
La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos
Secuencias de Bits
Rank y Select, aplicaciones a Hashing, Sumas, Pred/Succ
Rank y Select sobre Secuencias Comprimidas

Secuencias Dinamicas,
aplicaciones a Sumas Parciales
Secuencias de Smbolos
Recurriendo a Secuencias de Bits
El Wavelet Tree, aplicaciones a Geometra y Relaciones
Revisitando las Secuencias de Bits
G. Navarro

Estructuras de Datos Compactas

Mapa

Parte I: Secuencias
y Motivacion

Introduccion
La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos
Secuencias de Bits
Rank y Select, aplicaciones a Hashing, Sumas, Pred/Succ
Rank y Select sobre Secuencias Comprimidas

Secuencias Dinamicas,
aplicaciones a Sumas Parciales
Secuencias de Smbolos
Recurriendo a Secuencias de Bits
El Wavelet Tree, aplicaciones a Geometra y Relaciones
Revisitando las Secuencias de Bits
G. Navarro

Estructuras de Datos Compactas

Mapa

Parte II: Otras Estructuras

Arboles
con Parentesis

Representacion

a Mnimos en Rangos
Navegando en Parentesis,
aplicacion
de Arboles
Otra Representacion
Textos
El Arreglo de Sufijos Comprimido
de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair
G. Navarro

Estructuras de Datos Compactas

Mapa

Parte II: Otras Estructuras

Arboles
con Parentesis

Representacion

a Mnimos en Rangos
Navegando en Parentesis,
aplicacion
de Arboles
Otra Representacion
Textos
El Arreglo de Sufijos Comprimido
de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair
G. Navarro

Estructuras de Datos Compactas

Mapa

Parte II: Otras Estructuras

Arboles
con Parentesis

Representacion

a Mnimos en Rangos
Navegando en Parentesis,
aplicacion
de Arboles
Otra Representacion
Textos
El Arreglo de Sufijos Comprimido
de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos

Parte I: Secuencias
y Motivacion

Introduccion
La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos
Secuencias de Bits
Rank y Select, aplicaciones a Hashing, Sumas, Pred/Succ
Rank y Select sobre Secuencias Comprimidas

Secuencias Dinamicas,
aplicaciones a Sumas Parciales
Secuencias de Smbolos
Recurriendo a Secuencias de Bits
El Wavelet Tree, aplicaciones a Geometra y Relaciones
Revisitando las Secuencias de Bits
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos

La Jerarqua 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 extrado de Wikipedia.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos

La Jerarqua 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

Se cree que valdra al menos hasta el 2020.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos

La Jerarqua de Memoria
Todo sigue la Ley de Moore?
I

No!

Discos (tiempos de seek, por ejemplo).

Velocidad de acceso a la RAM.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos

La Jerarqua de Memoria
Actual
Situacion
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

rapidas

Mas
(por tecnologa y distancia a la CPU).
caras (por tecnologa).
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

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos

La Jerarqua de Memoria
Actual
Situacion
I

Numeros
gruesos y (relativamente) actuales:

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 jerarqua 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

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos

La Jerarqua 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

pequenas
y rapidas...

Siempre habra memorias mas

grandes y lentas.
... versus mas

Incluso sin considerar razones economicas!

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos

Parte I: Secuencias
y Motivacion

Introduccion
La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos
Secuencias de Bits
Rank y Select, aplicaciones a Hashing, Sumas, Pred/Succ
Rank y Select sobre Secuencias Comprimidas

Secuencias Dinamicas,
aplicaciones a Sumas Parciales
Secuencias de Smbolos
Recurriendo a Secuencias de Bits
El Wavelet Tree, aplicaciones a Geometra y Relaciones
Revisitando las Secuencias de Bits
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos

Estructuras de Datos Compactas

Son estructuras de datos...
I

Modificadas para ocupar poco espacio.

Y eso no es compresion?

No: deben retener su funcionalidad y acceso directo.

si la memoria es tan barata?

Para que,

Mejoran el rendimiento debido a la jerarqua de memoria.

Especialmente si logramos operar en RAM algo que

necesitara del disco!

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos

Estructuras de Datos Compactas

Un ejemplo motivante...
I

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 biologos

necesitan hacer busquedas
complejas en el!

Estas operaciones seran lentsimas en forma secuencial...

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

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos

Estructuras de Datos Compactas

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 podran 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

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos

Estructuras de Datos Compactas

Otro ejemplo motivante...

El grafo de la Web contena el 2004 unos 11.5 mil millones

de nodos y 150 mil millones de links.
o menos segun
Crece mas
la Ley de Moore.

la Web estatica

Esto considera solo

indexada!

Necesitara 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.
permite ademas
navegar el grafo hacia
Y con un poco mas
y otras operaciones utiles.
atras,

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos

Mapa del Tutorial

convencidos...
Ahora que estan
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 jerarqua de memoria en el diseno
algoritmos y estructuras de datos.
Veremos estructuras compactas para:
I
I
I
I
I

Manipular secuencias de bits

Manipular secuencias de smbolos

Navegar en arboles
Buscar en textos
Navegar en grafos

Y aplicaciones a hashing, conjuntos, sumas parciales,

geometra, permutaciones, y mas.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos

Parte I: Secuencias
y Motivacion

Introduccion
La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos
Secuencias de Bits
Rank y Select, aplicaciones a Hashing, Sumas, Pred/Succ
Rank y Select sobre Secuencias Comprimidas

Secuencias Dinamicas,
aplicaciones a Sumas Parciales
Secuencias de Smbolos
Recurriendo a Secuencias de Bits
El Wavelet Tree, aplicaciones a Geometra y Relaciones
Revisitando las Secuencias de Bits
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos

Entropa Emprica
I

Entropa 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).

Entropa de orden cero: si hay nc ocurrencias de c en S

(secuencia de smbolos sobre un alfabeto ),
H0 (S) =

X nc
c

log

n
nc

de que asigne
Cota inferior a cualquier codificacion

siempre el mismo codigo

al mismo smbolo (ej. Huffman).
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos

Entropa Emprica

Entropa 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

Cota inferior a codificaciones que consideran los k

smbolos precedentes (ej. PPM).

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos

Modelo RAM y Analisis

Asintotico
I
I

Mediremos el espacio en bits.

Modelo RAM:
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.

O(n) significa limitado superiormente por c n para alguna

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

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Parte I: Secuencias
y Motivacion

Introduccion
La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos
Secuencias de Bits
Rank y Select, aplicaciones a Hashing, Sumas, Pred/Succ
Rank y Select sobre Secuencias Comprimidas

Secuencias Dinamicas,
aplicaciones a Sumas Parciales
Secuencias de Smbolos
Recurriendo a Secuencias de Bits
El Wavelet Tree, aplicaciones a Geometra y Relaciones
Revisitando las Secuencias de Bits
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Secuencias de Bits
I
I

Consideremos una secuencia de n bits, B[1, n].

Nos interesan las siguientes operaciones sobre B:
I
I

Algunas propiedades simples:

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

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

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

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

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

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Rank y Select

Hashing perfecto
Una aplicacion:
I

Si el universo tiene n claves (por ejemplo [1, n]),

y queremos almacenar t elementos con r bits de datos,

hashing perfecto nos ofrece:

I
I
I

O(tr ) bits de espacio,

tiempo de acceso constante
aleatorizada o muy costosa.
construccion

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Rank y Select
I

usando rank:
Consideremos una solucion
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 podramos lograr tr + O(t log(n/t)) bits (menos de
un puntero extra por elemento).

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Rank y Select
Hashing perfecto
rank(B,7) = 3

00110011101010000000110010011110

Data (3)

Data (4)

Data (7)

G. Navarro

. . .

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

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

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

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Rank y Select
I

Supongamos que los A[i] son no negativos.

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].

Entonces
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

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Rank y Select
Sumas parciales

. . .

select(B,6)6 = 116 = 5

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

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

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

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

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Rank y Select

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)).

Podramos facilmente
obtener Succ k y Pred k en tiempo
constante.

Y con bitmaps comprimidos usaramos t log(n/t) bits!

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Rank
Rank en Tiempo Constante
I

Cortamos B en bloques de b = (log n)/2 bits.

Almacenamos un arreglo R[1, n/b] con los valores de rank

al comienzo de los bloques.

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

de lo
Aceptemos ese precio en espacio por ahora (es mas
prometido).
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Rank

Como
calculamos rank(B, i) ?
I
I
I

Descomponemos i = q b + r , 0 r < b.
La cantidad de 1s hasta qb es R[q].
Debemos contar los 1s 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 1s en x[1, r ]
donde vemos x como una tira de b bits.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

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
Entonces, la respuesta final se obtiene en tiempo
constante como:
R[q] + T [B[qb + 1..qb + b], r ]

Muy bien, pero nos gastamos 3n + o(n) bits...

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Rank
rank(B,13) = 7

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

000
001
010
011
100
101
110
111
G. Navarro

10

13

14

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Rank
Consiguiendo o(n) bits extra
I

en superbloques de
Cortamos B tambien
s =

(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

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Rank
I

Como necesitamos log n bits para almacenar un valor de

rank en S, el total de bits que ocupa S es
n
n
2n
log n =
log n =
= o(n)
2
s
log
n
(log n) /2

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
n
2 log log n =
2 log log n
b
(log n)/2
4n log log n
=
= o(n) bits.
log n
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Rank

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

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Rank
rank(B,13) = 7

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

10

0 1 2 0 1 2 0 1 2 0 3 4

G. Navarro

000
001
010
011
100
101
110
111

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Rank
Practica

Implementacion
I

Evitar divisiones y modulos,

usar potencias de 2.

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

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
Usamos superbloques de 256 bits (overhead 256
= 12.5%).
8
Usamos bloques de 32 bits (overhead 32 = 25%).
4 bytes.
Popcount de a lo mas
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

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%

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

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Select
Select en Tiempo Constante
I

donde o(n) = O(n/ log log n).

Describiremos una solucion

Notar que necesitamos hacer un sampling regular en los

argumentos de select, no regular en B (ambos criterios
coincidan para rank).

Un corte en bloques y superbloques como para rank no

funciona, porque los numeros
dentro de un bloque no se

reducen.

La idea fundamental es: si un bloque tiene pocos 1s,

puedo almacenar todas las respuestas a select en poco
espacio.
complejo que rank, tanto en la
Veremos que select es mas

teora como en la practica.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Select
I

Cortamos los argumentos de select en superbloques de

s = log2 n argumentos.

Estos superbloques tienen largo variable en B, pero tienen

exactamente s 1s.

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).

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Select
I

Almacenamos un bitmap E[1, n/s] indicando que

superbloques son esparsos.

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.

Para los superbloques densos, solamente almacenamos

un arreglo P[1, n/s] con las posiciones de B donde
comienzan.

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

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Select
I

Dividimos los superbloques densos en bloques de

b = (log log n)2 argumentos.

Aplicamos la misma idea nuevamente dentro de cada

superbloque denso.

Necesitamos log(log3 n log log n) 4 log log n bits para

dentro de un superbloque denso.
almacenar una posicion

Diremos que un bloque es esparso si su largo en B es a lo

menos 4b(log log n)2 , y es denso sino.

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

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Select
I

Almacenaremos un bitmap E 0 [1, s/b] indicando que

bloques son esparsos.

Para los bloques densos, solamente

almacenamos un
0
arreglo P [1, s/b] con las posiciones del superbloque
donde comienzan.
O(n/ log log n) bits.
Este P 0 cuesta tambien

No hemos solucionado el problema de los bloques densos,

pero sabemos donde

empiezan, y su largo es a lo mas
4(log log n)4 = o(log n) (siempre es < 82 log n).

Entonces, los bloques densos se pueden procesar en

tiempo O(1) usando tablas tipo T .

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Select
I

Como
calculamos select(B, 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

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Select
E

110 0

2 3 6 7

00110011101010000000110010011110

010

13

21 22

30

25

28

29

G. Navarro

000
001
010
011
100
101
110
111

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

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Select
Practica

Implementacion
I
I

Implementado directamente es bastante poco practico.

Por ejemplo:
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

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

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

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Parte I: Secuencias
y Motivacion

Introduccion
La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos
Secuencias de Bits
Rank y Select, aplicaciones a Hashing, Sumas, Pred/Succ
Rank y Select sobre Secuencias Comprimidas

Secuencias Dinamicas,
aplicaciones a Sumas Parciales
Secuencias de Smbolos
Recurriendo a Secuencias de Bits
El Wavelet Tree, aplicaciones a Geometra y Relaciones
Revisitando las Secuencias de Bits
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Rank y Select sobre Secuencias Comprimidas

I

I
I

I
I

En muchas aplicaciones, la secuencia tiene pocos o

muchos 1s.
Nos concentraremos en el caso en que hay m << n 1s.
Por ejemplo, podramos responder select en tiempo
constante usando m log n bits (almacenar todas las
respuestas).
Hay una forma de generalizar esta idea simple?
Veremos que podemos conseguir rank y select en tiempo
constante utilizando
n
nH0 (B) + o(n) = m log + O(m) + o(n) bits.
m
es teorica

La solucion
pero veremos alternativas practicas.
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Comprimida
Representacion
I

Dividiremos la secuencia en bloques de b = (log n)/2 bits.

Sea ci la cantidad de 1s en un cierto bloque Bi .

La cantidad de bloques distintos de largo b con ci 1s es

 
b
ci
y por lo tanto trataremos de representar Bi usando

 
b
log
bits.
ci

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Comprimida
Representacion
I

de Bi sera (ci , oi ), donde

La representacion
I
I

La clase, ci , necesita dlog(b
+ 1)e bits.

El offset, oi , necesita dlog cbi e bits.

Los ci s son de largo fijo, y ocupan en total



n log log n
n
dlog(b + 1)e = O
b
log n

Los oi s son de largo variable. Los concatenaremos todos.

veremos como

Despues
decodificarlos.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Comprimida
Representacion
I

de los oi s ocupa
La concatenacion
 
 
n/b 
n/b
X
X
b
b
log

log
ci
ci
i=1

+ n/b

i=1

= log

n/b  
Y
b
i=1

ci

+ O(n/ log n)



(n/b) b
log Pn/b
+ O(n/ log n)
i=1 ci
 
n
= log
+ O(n/ log n)
m
nH0 (B) + O(n/ log n) bits.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Comprimida
Representacion
I
I

Hemos representado B usando nH0 (B) + o(n) bits!

Pero, como
podemos extraer algun
bloque Bi en tiempo
constante?

Primer problema: donde

esta oi ?
I
I
I
I
I

I
I

Podemos almacenar las posiciones en P[1, n/b]...

... pero eso requerira (n/b) log n = 2n bits extra.
Definimos superbloques de s = b log n bits...
para superbloques.
... y almacenamos P[1, n/s] solo
Ahora tendremos un P 0 [1, n/b] con punteros relativos al
superbloque (como en rank ).
Como |oi | = O(log n), cada P 0 [i] requiere O(log log n) bits.
Total: O(n log log n/ log n) bits.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Comprimida
Representacion
I

Segundo problema: que bloque representa (ci , oi )?

I

Tendremos una tabla W [0, 2b 1] donde se almacenen

todos los bitmaps de largo b agrupados por clase.
Las posiciones donde empieza cada clase en W se
en un arreglo
precalcularan
C[c] = 1 +

c1  
X
b
i=0

I
I

W esta ordenada de modo que oi es el ndice

correspondiente dentro de la zona de la clase ci .
Entonces, (ci , oi ) representa
W [C[ci ] + oi ].

Estas tablas ocupan O( n log n) bits.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Comprimida
Representacion

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 1 3 1 1 0 1 1 1 3 1

0 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0

P
P

W
+10

15

0 2 4 0 2 4 0 2 4 0 0

G. Navarro

000
001
010
100
011
101
110
111

Estructuras de Datos Compactas

0
1 C
2
3

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Rank y Select
I

Las estructuras para rank y select ocupan o(n) bits

de B.
ademas

Necesitan acceso en tiempo constante a bloques de B.

Eso ya lo hemos conseguido con la representacion

comprimida!

Por lo tanto, hemos obtenido rank y select en tiempo

comprimida (a H0 ).
constante sobre la representacion
precisamente, usamos nH0 (B) + O(n log log n/ log n)
Mas
bits.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Comprimiendo a Orden k
I
I

de B que permita
Notar que cualquier representacion
obtener los bloques en tiempo constante sirve.
Consideremos el siguiente esquema:
I
I
I

Contamos cuantas
veces aparece cada bloque en B.
a menos frecuente.
Ordenamos los bloques de mas

Les asignamos codigos

de largo creciente:
, 0, 1, 00, 01, 10, 11, 000 . . .

Usamos los codigos

en vez de los pares (ci , oi ) del
esquema anterior.

Se puede probar que esto comprime a orden k:

nHk (B) + o(n),

G. Navarro

para todo k = o(log n)

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Comprimiendo a Orden k

Como
extraemos un bloque?
I

Almacenamos una tabla W con los bloques ordenados por

frecuencia.

Entonces al codigo
de valor numerico
i y de largo t le
corresponde el bloque numero

i +1+

t1
X

2j = i + 2t de la tabla.

j=0

Conseguimos rank y select en tiempo constante y espacio

nHk (B) + o(n) bits!

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Comprimiendo a Orden k

O
P
P

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

0 1 0 1 0 0 0 1

0 1 1 0 2 2 0 1 1 0 1

G. Navarro

(cod)

(frec)

100
001

""
0

5
2

111

000

00

010

01

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Comprimiendo a Orden k

Se puede generalizar a secuencias S[1, n] sobre un

.
alfabeto de tamano

Se obtiene acceso a O(log n) bits, es decir O(log n)

smbolos, en tiempo constante.

El espacio es
nHk (S) + o(n log ),

G. Navarro

para todo k = o(log n)

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Rank y Select
Practica

Implementacion
I

No funcionan tan bien como uno querra, especialmente si

la entropa es muy baja.

Las estructuras extra (ci , P 0 , R, etc.) pasan a dominar el

uso de espacio.

Veremos una alternativa practica

llamada sparse array,
para el caso de m << n.

Esencialmente, almacenamos todos los valores

S[i] = select(B, i), para 1 i m, y resolvemos rank con
busqueda
binaria.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Rank y Select
I

Los valores S[i] se separan en la parte baja li y la parte

alta hi .

La parte baja son los t bits menos significativos, de modo

que S[i] = hi 2t + li .


n
.
Elegimos t = log m

I
I

La secuencia L[i] de partes bajas se almacena en forma

n
+ O(m) bits.
normal, usando t m = m log m

La secuencia de partes altas se marcan en un bitmap

H[1, 2m], donde se prenden los bits H[hi + i].

Alcanzan 2m bits pues hm + m n/2t + m 2m.

n
El espacio total es m log m
+ O(m) = nH0 (B) + O(m).

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Rank y Select
I

resolver select en tiempo constante:

Es facil
select(B, i) = (select(H, i) i) 2t + L[i]

(hay que preprocesar H para consultas de select).

Para rank(B, i) se usa una busqueda
binaria mejorada.

I
I
I
I

El problema es encontrar donde

esta i en H.
t
Descomponemos i = h 2 + l, 0 l < 2t .
Cada 0 en H avanza 2t posiciones en B.
De modo que la respuesta esta entre los bloques
x = 1 + rank (H, select0 (H, h)) e
y = rank (H, select0 (H, h + 1)) de B.
Podemos hacer busqueda
binaria de l en L[x, y],

respondiendo rank en tiempo O(t) = O(log mn ).

En la practica
se prefiere la busqueda
secuencial.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Rank y Select

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

11

13

21

22

3 0 3 0 1 3 1 1 2 1 0 1 2 3

1 0 1 1 0 1 1 1 0 1 0 0 1 1 0 1 0 1 1 1 1

G. Navarro

25

28

29

Estructuras de Datos Compactas

30

31

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Rank y Select
Arreglos crecientes
I

con L y H es general?
Han notado que la solucion

Se puede aplicar a cualquier arreglo A[1, m] de valores

crecientes en [1, n].
n
permite representarlo usando m log m
+ O(m)
La solucion
bits...

... y acceder a las celdas en tiempo constante.

Incluso no es difcil modificar los valores de A.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Practica:

Implementacion
Espacio
Size of the data structures
6
vc
Kim
sa
Kim2
da
Navarro
rec
esp
entropy

Size (bpc)

Graficos
obtenidos por
Sadakane y su alumno
Okanohara

0
0

10

20

30

40
50
Ratio of 1

G. Navarro

60

70

80

90

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Practica:

Implementacion
Select
Time for 100,000,000 random select operations
120
esp
Kim
Kim2
rec
Navarro
vc
da
sa

100

Time (s)

80

60

Graficos
obtenidos por
Sadakane y su alumno
Okanohara

40

20

0
0

10

20

30

40

50
Ratio of 1

60

G. Navarro

70

80

90

100

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Practica:

Implementacion
Rank
Time for 100,000,000 random rank operations
120
vc
esp
Kim
rec
sa
da
Kim2
Navarro

100

Time (s)

80

60

Graficos
obtenidos por
Sadakane y su alumno
Okanohara

40

20

0
0

10

20

30

40

50
Ratio of 1

60

G. Navarro

70

80

90

100

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Parte I: Secuencias
y Motivacion

Introduccion
La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos
Secuencias de Bits
Rank y Select, aplicaciones a Hashing, Sumas, Pred/Succ
Rank y Select sobre Secuencias Comprimidas

Secuencias Dinamicas,
aplicaciones a Sumas Parciales
Secuencias de Smbolos
Recurriendo a Secuencias de Bits
El Wavelet Tree, aplicaciones a Geometra y Relaciones
Revisitando las Secuencias de Bits
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Secuencias Dinamicas
I

I
I
I

Hasta ahora hemos considerado secuencias de bits que

no cambian.
Que ocurre si queremos insertar y eliminar bits?
funcionan muy mal (recalcular todo).
Tal como estan,

En cambio, consideremos esta estructura de arbol

binario
balanceado:
I
I

Cada hoja maneja un bit.

Cada nodo interno conoce el total de bits y total de 1s en

su subarbol.

Todo se puede resolver en tiempo O(log n).

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Secuencias Dinamicas

Para encontrar el i-esimo

bit de B:
I

Si el subarbol
izquierdo contiene l i bits,

Sino,

busco el i-esimo
bit en el subarbol
izquierdo.

busco el (i l)-esimo
bit en el subarbol
derecho.

i, la busco e inserto o
Para insertar y borrar en la posicion
borro una hoja,
I
I

y recalculo cantidad de bits y de 1s,

y rebalanceo de ser necesario.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Secuencias Dinamicas
I

Para calcular rank(i)

I

Si el subarbol
izquierdo contiene l i bits,
I

calculo rank(i) en el subarbol

izquierdo.

Sino,

calculo rank(i l) en el subarbol

derecho y le sumo la

cantidad de 1s del subarbol

izquierdo.

Para calcular select(i)

I

Si el subarbol
izquierdo contiene s i 1s,

Sino,

calculo select(i) en el subarbol

izquierdo.

calculo select(i s) en el subarbol

derecho y le sumo la

cantidad de bits del subarbol

izquierdo.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Secuencias Dinamicas
I
I

Pero estamos ocupando O(n log n) bits!

Usaremos el truco estandar

para dinamizar estructuras
compactas:
I
I
I

Se construye la estructura dinamica

para bloques de datos.

Esos bloques se almacenan en forma estatica

y compacta.

Muchas veces se manejan brutalmente (reconstruccion

total, recorrido secuencial, etc.).
para no alterar los tiempos
Son suficientemente pequenos

de la estructura dinamica.
Son suficientemente grandes para que la estructura

dinamica
sea pequena.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Secuencias Dinamicas
I

Agrupamos s = log2 n bits en las hojas.

Formamos el arbol
sobre esas hojas.

Las operaciones en el arbol

cuestan tiempo O(log n)...

... y otro O(log n) en las hojas, usando tablas.

Como hay O(n/ log2 n) nodos, el arbol

ocupa O(n/ log n)
bits.
Se necesita cierto cuidado para no gastarse O(n) bits
extra en las hojas

No pueden estar llenas a medias, por ejemplo.

a una
Este esquema puede adaptarse tambien
comprimida de la secuencia.
representacion

Podemos permitir insertar, borrar, rank y select en tiempo

O(log n) y nH0 (B) + o(n) bits de espacio.
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Secuencias Dinamicas
rank(18)
16
33

rank(18)
18<=21

9
21

18>12
7+rank(1812)
7

12

12
6>3

3
6

4
6

4
6

3
6

7+1+rank(63)
1 0 0 1 0 1

1 1 1 0 0 1

0 0 1

1 0 0 0 0 0

0 1 0 1 1 1

0 1 0 1 0 1

9
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Secuencias Dinamicas
select(6)
16
33

select(6)
6<=9

9
21

6<=7
select(6)
7

12

12

6>3
3
6

4
6

4
6

3
6

6+select(63)
1 0 0 1 0 1

1 1 1 0 0 1

0 0 1

1 0 0 0 0 0

0 1 0 1 1 1

0 1 0 1 0 1

9
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Rank y Select
Secuencias Comprimidas

Secuencias Dinamicas

Sumas Parciales Dinamicas

Tenemos n numeros
de k bits.

de sum y search, permitiremos insertar y borrar

Ademas
numeros.

extender la tecnica

Es muy facil
de los bitmaps dinamicos.

En total necesitamos kn + o(kn) bits...

... y realizamos todas las operaciones en tiempo O(log n).

Con bitmaps comprimidos, se puede lograr espacio igual a

la suma total de bits necesarios para representar todos los
numeros.

I
I

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Parte I: Secuencias
y Motivacion

Introduccion
La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos
Secuencias de Bits
Rank y Select, aplicaciones a Hashing, Sumas, Pred/Succ
Rank y Select sobre Secuencias Comprimidas

Secuencias Dinamicas,
aplicaciones a Sumas Parciales
Secuencias de Smbolos
Recurriendo a Secuencias de Bits
El Wavelet Tree, aplicaciones a Geometra y Relaciones
Revisitando las Secuencias de Bits
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Secuencias de Smbolos

I
I

Consideremos ahora que manejamos una secuencia

.
S = s1 s2 . . . sn sobre un alfabeto de tamano
plana de S necesita n log bits.
Una representacion
Queremos hacer rank y select sobre esta secuencia:
I
I

rankc (S, i) = numero

de ocurrencias de c en S[1, i].

de la i-esima

selectc (S, i) = posicion

ocurrencia de c en S.

Como
podemos extender nuestros resultados sobre bits?

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Secuencias de Smbolos
I

Supongamos que almacenamos bitmaps Bc [1, n], c :

Bc [i] = 1 sii S[i] = c

Entonces
I
I

rankc (S, i) = rank1 (Bc , i).

selectc (S, i) = select1 (Bc , i).

Conseguimos tiempo constante... pero el precio es alto:

I
I
I

S ocupa n log bits.

Los bitmaps solos

ocupan n bits!
conocer S[i] sin almacenarlo cuesta tiempo O().
Ademas

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Secuencias Dinamicas
a l abar

la

a l aba rda

B_
Ba

00000010100100000000

Bb
Bd
Bl
Br

00010000000000010000

10101001001010101001
00000000000000000010
01000000010001000000
00000100000000000100
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Secuencias de Smbolos
I

Y si usaramos
bitmaps comprimidos?
I
I
I

Los nH0 (Bc ) suman nH0 (S).

Los espacios extras aun
suman mucho, o(n).

Si usaramos
la tecnica
practica
vista, el total sera
razonable: nH0 (S) + O(n).
El tiempo de rank sera cercano a O(log ), y el select
sera constante.
Pero aun
no podemos obtener S[i]!

tengamos S.
Estas ideas necesitan que ademas

Se puede hacer mejor?

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Parte I: Secuencias
y Motivacion

Introduccion
La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos
Secuencias de Bits
Rank y Select, aplicaciones a Hashing, Sumas, Pred/Succ
Rank y Select sobre Secuencias Comprimidas

Secuencias Dinamicas,
aplicaciones a Sumas Parciales
Secuencias de Smbolos
Recurriendo a Secuencias de Bits
El Wavelet Tree, aplicaciones a Geometra y Relaciones
Revisitando las Secuencias de Bits
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

El Wavelet Tree

elegante que permite almacenar S[1, n]:

Es una solucion
I
I
I

Usando n log + o(n log ) bits.

Resolviendo rank y select en tiempo O(log ).
Obteniendo S[i] en tiempo O(log ).

Se puede mejorar a espacio nH0 (S) + o(n log ).

Tiene muchas otras aplicaciones (veremos algunas).

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

El Wavelet Tree
I

I
I

Supongamos que partimos el alfabeto en dos

(o casi).
subconjuntos del mismo tamano
Creamos un bitmap indicando a que subconjunto pertence
cada letra de S.
Guardamos ese bitmap en la raz del wavelet tree.

Para el subarbol
izquierdo/derecho elegimos las letras de
S de cada subconjunto.

Continuamos recursivamente hasta que cada subconjunto

letra.
tenga una sola

ver que todos los bitmaps suman n log bits.

Es facil

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

El Wavelet Tree
a l abar a l a a l aba rda
01000100010001000110
_ab

dlr

aaba a a aabaa
00100000000100
_a

aaa a a aaaa
111010101111
_

l r l l rd
010010
dl

G. Navarro

r r

l l ld
1110

bb

aaaaaaaaa

l l l

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

El Wavelet Tree
I

Como
recuperamos una letra S[i]?
I
I

Miramos B[i] en la raz.

Si B[i] = 0,
I
I

Si B[i] = 1,
I
I

Nos vamos al subarbol

izquierdo.
es i 0 = rank0 (B, i).
La nueva posicion

Nos vamos al subarbol

derecho.
es i 0 = rank1 (B, i).
La nueva posicion

Cuando llegamos a una hoja, la letra correspondiente es

S[i].

Tiempo: log evaluaciones de rank.

Necesitamos preprocesar los bitmaps para rank.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

El Wavelet Tree
a l abar a l a a l aba rda
01000100010001000110
rank 0

_ab

dlr

aaba a a aabaa
00100000000100
_a

aaa a a aaaa
111010101111
_

l r l l rd
010010
dl

G. Navarro

r r

l l ld
1110

bb

aaaaaaaaa

l l l

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

El Wavelet Tree
I

Como
calculamos rankc (S, i)?
I
I

Sea B el bitmap de la raz.

Si c pertenece al subarbol
izquierdo,
I
I

Si c pertenece al subarbol
derecho,
I
I

Nos vamos al subarbol

izquierdo.
es i 0 = rank0 (B, i).
La nueva posicion

Nos vamos al subarbol

derecho.
es i 0 = rank1 (B, i).
La nueva posicion

Cuando llegamos a una hoja, la respuesta es i.

Tiempo: log evaluaciones de rank.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

El Wavelet Tree
rank l (S,11)

a l abar a l a a l aba rda

01000100010001000110
rank 1

_ab

dlr

aaba a a aabaa
00100000000100
_a

aaa a a aaaa
111010101111
_

l r l l rd
010010
dl

G. Navarro

r r

l l ld
1110

bb

aaaaaaaaa

l l l

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

El Wavelet Tree
I

Como
calculamos selectc (S, i)?
I
I
I

Nos vamos a la hoja correspondiente a c.

Sea B el bitmap de su padre.
Si la hoja es hijo izquierdo de su padre,
I
I

Si la hoja es hijo derecho de su padre,

I
I

Nos vamos al padre.

es i 0 = select0 (B, i).
La nueva posicion
Nos vamos al padre.
es i 0 = select1 (B, i).
La nueva posicion

Cuando llegamos a la raz, la respuesta es i.

Tiempo: log evaluaciones de select.

Necesitamos preprocesar los bitmaps para select.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

El Wavelet Tree
select b(S,2)

a l abar a l a a l aba rda

01000100010001000110
_ab

dlr

aaba a a aabaa
00100000000100
select 1

_a

aaa a a aaaa
111010101111
_

l r l l rd
010010
dl

G. Navarro

r r

l l ld
1110

bb

aaaaaaaaa

l l l

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Extensiones
I
I
I
I
I
I
I

Si representamos los bitmaps como secuencias

comprimidas, obtenemos nH0 (S) + o(n log ) bits.

Si utilizamos bitmaps dinamicos,

podemos insertar y
eliminar letras en tiempo O(log n log ).
cuestan
En ese caso las otras operaciones tambien
O(log n log ).
Podramos mejorar los tiempos con wavelet trees
multiarios.
Para ello necesitaramos manejar secuencias de smbolos
en cada nivel del wavelet tree, en tiempo constante.

Esto se puede hacer con la tecnica

de los pares (c, o),

para alfabetos pequenos,

o(log n/ log log n).
En total, todos los tiempos O(log ) se pueden mejorar a
O(1 + logloglog n ).
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Huffman Wavelet Trees

I

I
I
I
I

I
I

Veremos una alternativa practica

para obtener casi
nH0 (S) + o(n log ) bits.
En vez de utilizar bitmaps comprimidos, usaremos los
explcitos.

Pero le daremos forma de arbol

de Huffman al wavelet
tree.
No es difcil ver que el largo total de las tiras de bits...
... es exactamente el largo de S comprimida con Huffman.
Este largo es < n(H0 (S) + 1).
si los caracteres se acceden con la misma
Ademas,
frecuencia que tienen en S...
el tiempo promedio de acceso baja a O(H0 (S)).
Se puede limitar la altura a O(log ) para el peor caso.
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Huffman Wavelet Trees

a l abar a l a a l aba rda
01010110110101010110
a

_bdlr

aaaaaaaaa

lb r
l l br d
110001011 00
bl

_dr

lb l lb
10110
b

r
r d
100011
l

bb

dr

l l l

r rd
110
d

d
G. Navarro

Estructuras de Datos Compactas

r r

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Un Problema Geometrico
I

Tenemos una grilla discreta de [1, n] [1, n] (para

simplificar, pero podra ser rectangular tambien).

de un punto
Almacenamos t puntos en esa grilla (no mas
por celda, para simplificar).
Queremos responder consultas de rangos:
I
I

Cuantos
puntos hay en [x1 , x2 ] [y1 , y2 ]?
Que puntos hay en [x1 , x2 ] [y1 , y2 ]?

Un wavelet tree puede resolver este problema:

I
I
I

Usando (n + t log n)(1 + o(1)) bits de espacio.

Calculando la cantidad de puntos en tiempo O(log n).
Reportando cada punto en tiempo O(log n).

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Un Problema Geometrico
I

I
I
I

I
I

Comencemos con un caso simplificado: Hay exactamente

un punto por valor en coordenada x.
Entonces las coordenadas y de los puntos, ordenados por
coordenada x, forman una secuencia S[1, n].
Construimos el wavelet tree sobre S.
Los segmentos en S corresponden a rangos en el eje x.
Las particiones en mitades que hace el wavelet tree
corresponden al eje y.
Dado un punto p = (x, y), vale que S[x] = y .

Si seguimos a p por el arbol,

usando rank, llegamos a la

y-esima
hoja.
Si seguimos un valor y desde una hoja, usando select,
x correspondiente en la raz.
llegamos a la posicion
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Un Problema Geometrico
21 7 12 9 20 11 8 3 15 1 13 5 17 4 16 19 10 2 14 6 18
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Un Problema Geometrico
21 7 12 9 20 11 8 3 15 1 13 5 17 4 16 19 10 2 14 6 18
1
2
3
4
5
6
7
8
9
10
11
7

11 8 3

10 2

12
13
14
15
16
17
18
19
20
21
21

12

20

15
G. Navarro

13

17

16 19

14

18

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Un Problema Geometrico
21 7 12 9 20 11 8 3 15 1 13 5 17 4 16 19 10 2 14 6 18
1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 1 0 0 1 0 1

7 9 11 8 3 1 5 4 10 2 6
1
2
3
4
5
6
7
8
9
10
11

21 12 20 15 13 17 16 19 14 18
12
13
14
15
16
17
18
19
20
21

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Un Problema Geometrico
21 7 12 9 20 11 8 3 15 1 13 5 17 4 16 19 10 2 14 6 18
1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 1 0 0 1 0 1

7 9 11 8 3 1 5 4 10 2 6
1 1 1 1 0 0 0 0 1 0 0

3 1 5 4 2 6
0 0 1 1 0 1

3 1 2
1 0 0

1 2
0 1
1

7 9 11 8 10
0 0 1 0 1

5 4 6
1 1 0

5 4
1 0
4

21 12 20 15 13 17 16 19 14 18
1 0 1 0 0 1 0 1 0 1

12 15 13 16 14
0 1 0 1 0

21 20 17 19 18
1 1 0 0 0

7 9 8
0 1 0

11 10
1 0

12 13 14
0 0 1

7 8
0 1

10 11

12 13 14 15 16 17 18 19 20 21
0 1
0 1

12
G. Navarro

13

15 16
0 1

17 19 18
0 1 0

17

21 20
1 0

18

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Un Problema Geometrico

en general, necesitaremos proyectar un rango de

Mas
valores x:
I
I
I

Si en un nodo v , correspondiente al rango [y, y 0 ],

tenemos un rango B[x, x 0 ] en el bitmap de v ,
entonces [1 + rank0 (B, x 1), rank0 (B, x 0 )] es el rango de
los puntos esos que caen en la primera mitad de [y, y 0 ],
y [1 + rank1 (B, x 1), rank1 (B, x 0 )] es el rango de los
puntos esos que caen en la segunda mitad de [y, y 0 ].

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Un Problema Geometrico
I

Para contar cuantos

puntos hay en [x1 , x2 ] [y1 , y2 ]:
I
I
I

Partimos en la raz con el rango [x, x 0 ] = [x1 , x2 ].

Proyectamos el rango en ambos subarboles.

Continuamos recursivamente, deteniendonos

cuando:
I

I
I

El intervalo [x, x 0 ] esta vaco (no hay puntos del rango

original [x1 , x2 ] que caen en el rango [y , y 0 ] de este nodo).
El intervalo [y , y 0 ] es disjunto con el original ([y1 , y2 ]).
El intervalo [y , y 0 ] esta contenido en el original ([y1 , y2 ]):
Sumar x 0 x + 1 al total

Todo subintervalo de [y1 , y2 ] se cubre con O(log n) nodos

[y , y 0 ] del wavelet tree.
El algoritmo hace O(log n) operaciones.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Un Problema Geometrico

Para encontrar esos puntos.

I
I

Partir de cada nodo en el que contamos resultados.

Seguir cada punto de [x, x 0 ] hacia abajo hasta descubrir su
coordenada y.
Y/o seguir cada punto de [x, x 0 ] hacia arriba hasta
descubrir su coordenada x.

Esto claramente cuesta O(log n) por cada punto.

Debemos concatenar los bitmaps de cada nivel para no

tener demasiados punteros en el arbol.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Un Problema Geometrico
I
I

de un punto por coordenada.

Eliminemos la simplificacion
por cada punto
El wavelet tree ahora maneja una posicion
almacenado (t puntos).

En la raz los puntos se ordenan columna a columna (y por

fila dentro de cada columna).

Un bitmap X [1, n + t] tiene un 1 por cada cambio de

columna y un 0 por cada nuevo punto.

El arbol
va subdividiendo los puntos segun
coordenada y .

I
I

En las hojas los puntos se encuentran ledos fila a fila (y

por columna dentro de cada fila).

No necesito un equivalente a Y para leer por filas, pues se

en que hoja del wavelet tree estoy.
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Permutaciones
I

se
La variante simplificada de puntos en n n tambien

puede ver como una permutacion.

se puede almacenar en n log n bits y,
Una permutacion
dado i, calcular (i) en tiempo constante.
la permutacion
inversa 1 (i),
Si quisiera tambien
necesitara otros n log n bits.
Con un wavelet tree sobre S represento implcitamente
ambas permutaciones con n log n + o(n log n) bits y
calculo:


log n
log log n

(i) = S[i] en tiempo O

1 (i) = selecti (S, 1) en tiempo O

G. Navarro

log n
log log n

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Permutaciones
I
I

Se puede hacer mejor? S.

es una secuencia
Un ciclo de una permutacion
i, (i), ((i)), (((i))), . . . , 1 (i), i

I
I

de [1, n] se descompone en ciclos.

Toda permutacion
1
Para calcular (i), basta seguir el ciclo desde i hasta
que volvamos a i
I

I
I

El ultimo
valor visitado antes de volver a i es 1 (i).

Pero el ciclo puede ser muy largo!

Cada t valores de un ciclo largo, introduciremos punteros
reversos que retrocedan t valores en el ciclo.
Si parto de i, puedo tomar el primer puntero reverso que
t + 1 pasos.
encuentre, y llegare a i de vuelta en a lo mas
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Permutaciones

21 7 12 9 20 11 8
19

10

11

12

13

14

15

16

17

18

19

20

21

3 15 1 13 5 17 4 16 19 10 2 14 6 18
4
15

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Permutaciones
I

Como
almaceno eficientemente los punteros reversos?
I

Marco en un bitmap R[1, n] que posiciones tienen punteros

reversos.
Almaceno sus valores en forma compacta en P[1, s],
s n/t.
Si R[i] = 1, hay un puntero reverso en i, y su valor esta en
P[rank (R, i)].

En total ocupo n log n + (n/t) log n + n + o(n) bits.

Resuelvo (i) en O(1) y 1 (i) en O(t).

Por ejemplo:

Con (1 + )n log n + O(n) bits, para  constante, resuelvo

en tiempo O(1) y 1 en tiempo O(1/) = O(1).
Con n log n + O(n log log n) bits, resuelvo en tiempo O(1)
y 1 en tiempo O(log n/ log log n) (mejor que con wavelet
trees).
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Permutaciones

Y si quisiera resolver k y k ?
I
I
I

I
I

Imaginemos que escribimos los ciclos explcitamente en S.

(i) sigue a i en S; 1 precede a i.

Marcamos en un bitmap C[1, n] donde

comienzan los
ciclos.
0 que me lleva de la
Almacenamos una permutacion
donde se mapeo en S.
secuencia original a la posicion

Represento 0 con la tecnica

anterior.
Eso basta para calcular cualquier k y k en tiempo O(t).

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Permutaciones
I

Para calcular k (i) (k positivo o negativo):

I
I

Con i 0 = 0 (i) ubico i en S.

Calculo los lmites del ciclo:
I
I

l = select(C, rank (C, l))

r = select(C, rank(C, l) + 1)

que corresponde a k (i) es

La posicion
j 0 = l + (i 0 + k l mod (r l))

Finalmente vuelvo: k (i) = 01 (j 0 )

Se puede extender a mapeos (no lo veremos).

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Permutaciones

21 7 12 9 20 11 8

21 18 2

10

11

12

13

14

15

16

17

18

19

20

21

3 15 1 13 5 17 4 16 19 10 2 14 6 18

3 12 5 20 6 11 13 17 10 1

9 15 16 19 14 4

10

11

G. Navarro

12

13

14

15

16

17

18

19

Estructuras de Datos Compactas

20

21

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Parte I: Secuencias
y Motivacion

Introduccion
La Jerarqua de Memoria
Estructuras de Datos Compactas

Conceptos Basicos
Secuencias de Bits
Rank y Select, aplicaciones a Hashing, Sumas, Pred/Succ
Rank y Select sobre Secuencias Comprimidas

Secuencias Dinamicas,
aplicaciones a Sumas Parciales
Secuencias de Smbolos
Recurriendo a Secuencias de Bits
El Wavelet Tree, aplicaciones a Geometra y Relaciones
Revisitando las Secuencias de Bits
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Revisitando las Secuencias de Bits

de secuencias de bits, que

Volvamos a la solucion
promete mejores tiempos.

Conseguiremos tiempos de la forma O(log log ) ...

... y espacio n log + n o(log ).

Cortaremos las secuencias de bits en bloques de largo .

Resolveremos separadamente dos subproblemas:

I
I

Determinar la respuesta a nivel de bloque.

Refinar la respuesta dentro del bloque.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Revisitando las Secuencias de Bits

Nivel de bloques
I
I

Consideremos una secuencia de bits particular Bc .

La representaremos con otra secuencia de bits Lc , donde
I
I
I

Comenzare poniendo un 0.
Ire agregando los 1s que aparecen en Bc .
Ire agregando un 0 cuando cambie de bloque.

Sumando sobre todas las Lc , tengo n 1s y n 0s.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Revisitando las Secuencias de Bits

a l abar

la

a l aba rda

B_
Ba
Bb
Bd
Bl
Br

00000010100100000000

L_
La

00111000

Lb
Ld
Ll
Lr

0100100

10101001001010101001
00010000000000010000
00000000000000000010
01000000010001000000
00000100000000000100
01110110111010
000010
0101010
0100100

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Revisitando las Secuencias de Bits

I

Para calcular rankc (S, i) = rank(Bc , i):

I
I
I
I
I

Calculo b = 1 + bi/c.
Calculo r = rank1 (Lc , select0 (Lc , b)).
b es el bloque donde debo completar la respuesta.
r es la cantidad de ocurrencias de c antes del bloque b.
Dentro del bloque b debo calcular rankc (1 + (i mod )).

Para calcular S[i]:

I
I
I

Calculo b = 1 + bi/c.
b es el bloque donde debo buscar la respuesta.

Dentro del bloque b debo obtener el smbolo en la posicion

1 + (i mod ).

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Revisitando las Secuencias de Bits

Para calcular select(S, i) = select(Bc , i):

I
I
I
I

Calculo j = select1 (Lc , i).

Calculo b = rank0 (Lc , j).
b es el bloque donde debo completar la respuesta.
Dentro del bloque b debo calcular
selectc (j select0 (Lc , b)).
debo sumarle b .
A esa posicion

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Revisitando las Secuencias de Bits

Resolviendo dentro de un bloque
I

Almacenamos las posiciones donde ocurre "a" en orden,

luego donde ocurre "b" en orden, etc.
de [1, ].
El resultado es una permutacion

almaceno un bitmap P[1, 2] con un 1 por cada

Ademas
ocurrencia almacenada en de cada smbolo, insertando
un 0 al principio y cada vez que se cambia de smbolo.

Entonces selectc (i) = (select0 (P, c) c + i 1).

Asimismo, S[i] = rank0 (P, select1 (P, 1 (i))).

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Revisitando las Secuencias de Bits

a l abar

B_
Ba
Bb
Bd
Bl
Br

la

a l aba rda

00000010100100000000
10101001001010101001
00010000000000010000
00000000000000000010
01000000010001000000
00000100000000000100

135426
P 0011101001010
G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Revisitando las Secuencias de Bits

I

difcil es rankc (S, i):

Lo mas
I

I
I

La zona de las ocurrencias de c en es

[l, r ] = [select0 (P, c) c + 1 . . . select0 (P, c + 1) (c + 1)].
Si hago busqueda
binaria consigo tiempo O(log ).

Para conseguir O(log log ):

I
I
I

I
I

Anoto los valores [i log ] en una lista.

en [1, ].
Esta lista tiene log numeros

La separo en las sublistas (crecientes) que corresponden a

cada c.
Necesito calcular el predecesor y sucesor de i en una de
esas sublistas.
Lo hago en tiempo constante con bitmaps comprimidos.
Completo la busqueda
binaria en el tramo de log valores.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Revisitando las Secuencias de Bits

I

Los bitmaps Lc ocupan 2n + o(n) bits.

Las permutaciones ocupan n log bits.

Para obtener 1 en tiempo O(log log ) necesitamos

punteros reversos que ocupen O(n logloglog ) = n o(log ).

Los bitmaps P ocupan 2n + o(n) bits (son los Lc

reordenados).

Los bitmaps para predecesor y sucesor ocupan

log log

O( n log log / log

) = O(n log ) bits.

Total n log + O(n

S[i] y rankc se calculan en tiempo O(log log ).

selectc se calcula en tiempo constante.

log
log log )

G. Navarro

bits.

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Relaciones Binarias

se puede extender a relaciones binarias R

La solucion
entre dos conjuntos A y B.

Si |A| = n y |B| = m, el punto (i, j) existe sii ai R bj .

Queremos resolver las siguientes operaciones
eficientemente:

I
I
I

Dados ai y bj , determinar si ai R bj .
Dado ai , contar/listar los bj tal que ai R bj .
Dado bj , contar/listar los ai tal que ai R bj .

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Relaciones Binarias
I

binaria como t 1s
Si |R| = t, podemos ver la relacion
distribuidos en n bitmaps de largo m.

Imaginemos que leemos esos 1s columna a columna, y

escribimos las filas donde aparecen en una secuencia S.
agregamos a un bitmap L un 1 por cada fila
Ademas
uno final).
anotada y un 0 por cada nueva columna (mas

Preprocesamos S y L para rank y select.

El espacio total es t log n + t + m bits.

O t log m + t + n, lo que sea menor.

Las operaciones cuestan O(log log t) por respuesta.

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Relaciones Binarias

1 2 3 4 5 6 7 8 9 10

a
b
c
d
e
f

0000101000

bd

c ab e f

f ab

ce

1000101000
0001000001

0 11 0 0 0 1 0 1111 0 1 0 11 0 0 0 1 1 0

1000000000
0000100001
0000110000

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Relaciones Binarias
I

Determinar si un par (ai , bj ) esta relacionado:

ranki (S, select0 (L, j + 1) (j + 1)) ranki (S, select0 (L, j) j)

Contar con cuantos

pares esta relacionado bj :
select0 (L, j + 1) select0 (L, j) 1

Contar con cuantos

pares esta relacionado ai :
ranki (S, t)

Listar con quienes

se relaciona bj
S[k + (select0 (L, j) j)],

k = 1, 2, . . .

Listar con quienes

se relaciona ai
rank0 (L, select1 (L, selectk (S, i)))],
G. Navarro

k = 1, 2, . . .

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Relaciones Binarias

sofisticadas...
Con tecnicas
un poco mas
I
I

Ocupamos t log mn
t bits (orden cero).
Resolvemos todas las consultas en tiempo O(log log mn
t ).

se
Se particiona horizontalmente y luego cada particion
re-particiona verticalmente.

Eso garantiza una cantidad conveniente de 1s en cada

bloque.
detalles.
No veremos mas

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Relaciones Binarias

inmediata 1: Grafos G = (V , E)
Aplicacion
I
I

I
I
I
I

A = B = V son los nodos, E = R son las aristas.

El espacio es basicamente
e log n, como una lista de
adyacencia.
Permite saber si una arista esta presente en el grafo.
Permite listar los vecinos directos y reversos.
Permite contarlos eficientemente.
Cada respuesta en tiempo O(log log n).

G. Navarro

Estructuras de Datos Compactas

 y Motivacion

Introduccion
Secuencias de Bits
Secuencias de Smbolos

Recurriendo a Secuencias de Bits

El Wavelet Tree
Revisitando las Secuencias de Bits

Relaciones Binarias
I

inmediata 2: Indices Invertidos

Aplicacion
I

I
I
I

I
I

y B las p
A son los d documentos de una coleccion
palabras distintas (vocabulario).

El espacio es basicamente
t log p bits, menos que una
plana de la coleccion.

representacion
O bien t log d bits, igual que un ndice invertido tradicional.
Podemos saber si una palabra aparece en un documento.
Podemos listar los documentos donde aparece una
palabra, y las palabras que aparecen en un documento.

Podemos saber en cuantos

documentos distintos aparece
una palabra (llamado df y muy importante para calcular
relevancia).
cuantas

Y tambien
palabras distintas tiene un documento.
El tiempo es O(log log p) o O(log log d).

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Parte II: Otras Estructuras

Arboles
con Parentesis

Representacion

a Mnimos en Rangos
Navegando en Parentesis,
aplicacion
de Arboles
Otra Representacion
Textos
El Arreglo de Sufijos Comprimido
de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair
G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Arboles Generales
I

I
I

I
I

Una estructura clasica

de punteros ocupa O(n log n) bits

para un arbol
de n nodos.

Permite navegar en el arbol

en tiempo constante.

22n / n arboles
distintos con n
Pero realmente hay solo
nodos.
Se debera poder almacenar con 2n o(n) bits.

En realidad no es difcil representar un arbol

en ese
espacio...

... el verdadero desafo es poderlo navegar sin

descompactarlo.

Veremos la forma de lograrlo en tiempo constante por

usando 2n + o(n) bits.
operacion,
G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

con Parentesis

Representacion
I

I
I

muy conocida de arboles

Una representacion
generales

utiliza parentesis
balanceados.

Recorremos el arbol
en preorden.
Es decir, al llegar a un nodo:
I
I
I

Escribimos un (.
Recorremos sus hijos en orden.
Escribimos un ).

R(v ) de
O, expresado de otra manera, la representacion
un nodo v con hijos v1 , v2 . . . vk es
R(v )

( R(v1 ) R(v2 ) . . . R(vk ) )

El resultado es una secuencia balanceada de 2n

parentesis.
G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

con Parentesis

Representacion

( 1)
(2)

( 10 )

(3 )( 4) ( 5 )( 9)

( 11 )
( 12 )

( 13 )

(6)

( 14 )

(7) (8)

( 15 )
G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

con Parentesis

Representacion
I

Una secuencia balanceada de parentesis

cumple:
I
I
I

Es una secuencia sobre los smbolos ( y ).

En total hay tantos ( como ).
En cualquier punto i de la secuencia, la cantidad de ( en
S[1, i] es a la cantidad de ) en S[1, i].

Esto ultimo
tiene nombre: se llama exceso en i:

exceso(S, i) = rank( (S, i) rank) (S, i)

y la propiedad establece simplemente que
exceso(S, i) 0 para todo i, y que exceso(S, 2n) = 0.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

con Parentesis

Representacion
I

Llamaremos pareja de un ( al ) que lo cierra, y

pareja de un ) al ( que lo abre.
de su
Si S[v ] =0 (0 , llamaremos close(v ) a la posicion
pareja.
de su
Si S[v ] =0 )0 , llamaremos open(v ) a la posicion
pareja.
Observar:
I

close(v ) es el menor v 0 > v tal que

exceso(v 0 ) = exceso(v ) 1.
open(v 0 ) es el mayor v < v 0 tal que
exceso(v ) = exceso(v 0 ) + 1.

G. Navarro

Estructuras de Datos Compactas

 con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Arboles
Textos
Grafos

con Parentesis

Representacion
1

11

10

12

6
7

13

14
8

15

((( )( )(( ( )( )))( ))( )(( )((( )))))

parejas (open/close)
exceso = 3
preorden = 13
rank() = 7

G. Navarro

exceso = 2
preorden = 15
rank() = 8

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

con Parentesis

Representacion
Varias propiedades interesantes
I

Identificaremos a un nodo v con su ( correspondiente.

Una hoja se ve as: ().

u es ancestro de v , sii [u, close(u)] contiene estrictamente

a [v , close(v )].

La profundidad de v en el arbol
es exceso(v ).
de v en una enumeracion
en preorden del
La posicion

arbol
es rank( (S, v ).

I
I

asociada a los
Esto es util
para almacenar informacion
nodos.
Se puede igualmente precalcular un rank() (S, v ) para
asociada a las hojas.
almacenar informacion

tamano
de subarbol.

Con eso tenemos tambien

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

con Parentesis

Representacion

Navegacion
I

El siguiente hermano de v es close(v ) + 1

I

El hermano previo de v es open(v 1)

I

Pero si S[v 1] = (, v no tiene hermano previo.

El primer hijo de v es v + 1
I

Pero si es un ), v no tiene siguiente hermano.

Pero si es un ), v no tiene hijos.

de calcular.
El padre de v no es tan facil
I
I

enclose(v ).
Se crea la operacion
profundo que contiene a v .
Es el ( del nodo mas

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

con Parentesis

Representacion
I

I
I

Por lo tanto, basta con implementar open, close y

enclose...
en un
... para tener bastantes operaciones de navegacion

arbol
representado con parentesis.
Conseguiremos tiempo constante usando 2n + o(n) bits.
Hay muchas otras operaciones interesantes:
I
I
I

bajo,
i-esimo
padre, ancestro comun
mas

i-esimo
hijo, hijo con rotulo
l,
busqueda
de caminos rotulados, ...

pueden hacerse eficientemente, con tecnicas

Tambien

mas avanzadas.

Asimismo puede comprimirse el arbol.

algunas de estas cosas.

Veremos solo

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Parte II: Otras Estructuras

Arboles
con Parentesis

Representacion

a Mnimos en Rangos
Navegando en Parentesis,
aplicacion
de Arboles
Otra Representacion
Textos
El Arreglo de Sufijos Comprimido
de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair
G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Navegando entre Parentesis

close
Operacion
I

Dividimos la secuencia de parentesis

en bloques de largo
b = log2 n .

Un parentesis
es cercano si su pareja esta en el mismo
bloque, sino es lejano.

Resolver close(v ) para un v cercano es facil:

I
I
I
I
I

Tenemos una tabla T [x, v ], 0 x < 2b , 1 v b.

en el.

x es el bitmap de un bloque y v una posicion

T [x, v ] precalcula close(v ) si este

esta dentro de x.
Sino, indicaque v es lejano.
T requiere n log n log log n = o(n) bits.

Nuestro verdadero problema son los parentesis

lejanos.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Navegando entre Parentesis

Parentesis
lejanos y pioneros
I
I

Distinguiremos algunos parentesis

lejanos como pioneros.

Un parentesis
lejano p (que abre) es pionero si el previo
lejano que abre se cierra en un bloque distinto al del que
cierra p.

Un parentesis
lejano p (que cierra) es pionero si el
siguiente lejano que cierra se abre en un bloque distinto al
del que abre p.
es pionero.
La pareja de un pionero tambien

G. Navarro

Estructuras de Datos Compactas

 con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Arboles
Textos
Grafos

Navegando entre Parentesis

1

6
7

11

10

12

cercanos
lejanos
pioneros (

13

14

15

((( )( )(( ( )( )))( ))( )(( )((( )))))

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Navegando entre Parentesis

Dos propiedades esenciales sobre pioneros
I

Hay a lo sumo 4n/b parentesis

pioneros.
I

Pues cada pionero (por derecho propio) que abre debe

cerrarse en un bloque distinto.
Con los que cierran, y con las parejas de los pioneros,
podemos cuadruplicar la cantidad.

El parentesis
que cierra a v esta en el mismo bloque que
el que cierra al ultimo
pionero que abre en S[1, v ].

Si ese pionero no es v mismo, se cierra en el mismo

(y se cierra despues
de v ).
bloque que v , por definicion
El ultimo
pionero en S[1, v ] debe abrir, pues si cerrara, el

sera pionero.
primero lejano que abre luego de el
Por lo tanto el ultimo
pionero representa un ancestro de v .

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Navegando entre Parentesis

Estrategia general para hallar v 0 = close(v )
I

Buscaremos el ultimo
pionero p que abre en S[1, v ].

Resolveremos p0 = close(p) de alguna manera.

Buscaremos v 0 con tablas en el bloque de p0 .

Resolviendo close para pioneros

I

La secuencia de parentesis
pioneros es una nueva
secuencia balanceada.

Supongamos por un momento que en esa secuencia

puedo responder en tiempo constante open0 , close0 , y
enclose0 .

Luego lo resolveremos usando recursion.

G. Navarro

Estructuras de Datos Compactas

 con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Arboles
Textos
Grafos

Navegando entre Parentesis

Hallando el ultimo
pionero

Marco en una secuencia P con un 1 los parentesis

que
son pioneros.

Representada en forma comprimida, P requiere

O(n

log b
b )

= O(n

log log n
log n )

= o(n) bits.

Encontramos el parentesis
pionero que precede a v
mediante p = select(P, rank(P, v )).
en la secuencia reducida es q = rank(P, p).
Su posicion

Entonces p0 = select(P, close0 (q)).

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Navegando entre Parentesis

Hallando close en el bloque donde cierra el pionero

I

Tenemos ubicado a p0 , en el mismo bloque de v 0 .

Sabemos que
exceso(v 0 ) exceso(p0 ) = exceso(v ) exceso(p).

Con eso, podemos encontrar v 0 a partir de p0 usando una

tabla parecida a T .

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Navegando entre Parentesis

Recursion
I

En la secuencia de pioneros (de largo 4n/b) hacemos

exactamente lo mismo, en forma recursiva (mantenemos
el mismo b).

Al siguiente nivel, ya hay O(n/ log2 n) parentesis,

y todas
las respuestas se pueden almacenar directamente con
O(n/ log n) bits.
2 niveles de recursion,
tiempo total constante.
Son solo

Resolviendo open(v )
I

Es completamente simetrico
a close(v ).

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Navegando entre Parentesis

Resolviendo enclose(v )
I

Es el ultimo
u < v tal que exceso(u) = exceso(v ) 1.

Primero se ve con tablas si esta en el mismo bloque de v o

de close(v ).

Calculamos el primer pionero c 0 en S[v . . .].

Si c 0 cierra, entonces calculamos p0 = open(c 0 ), sino

p0 = enclose(c 0 ) en la secuencia de pioneros.
cercano que encierra a v .
p0 es el pionero mas

I
I

Entonces u = enclose(v ) debe estar en el mismo bloque

de p0 (o puede ser el mismo p0 ).
que p0 , despues

Se busca con tablas u = ultimo

parentesis
que abre en el

bloque de p0 con el exceso correcto.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Navegando entre Parentesis

Espacio total
I

La secuencia de parentesis
S usa 2n bits.

La secuencia P que marca pioneros, comprimida, usa

O(n logloglogn n ) bits.

Las tablas (universales) usan O( n polylog(n)) bits.

El segundo nivel requiere O(n/ log n) bits.

El tercer nivel requiere O(n/ log n) bits.

Total:


log log n
2n + O n
log n

G. Navarro


= 2n + o(n) bits.

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Arboles Binarios
I

Se pueden representar como arboles

generales, pero
requieren 4n bits (marcar hojas explcitamente).

Pero se puede representar con 2n bits.

La idea es usar un mapeo conocido entre arboles

binarios
y generales.

El arbol
general tiene una raz ficticia (que no pondremos

en los parentesis)...

derecho del arbol

... y todo el camino mas

binario son los

hijos de la raz del arbol

general.

Luego se transforma recursivamente.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Arboles Binarios

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Arboles Binarios

((( (( ))) ( )) ()( ))

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Arboles Binarios

Navegacion
I

La raz del arbol

binario es el primer hijo del arbol
general.

Hijo izquierdo de v : primer hijo de v (= v + 1).

Hijo derecho de v : siguiente hermano de v .

Padre de hijo izquierdo v : padre de v (= v 1).

Padre de hijo derecho v : hermano previo de v .

v es hijo izquierdo sii S[v 1] =0 (0 .

v es hoja sii S[v + 1] =0 )0 y S[v + 2] =0 )0 .

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Arboles Binarios

((( (( ))) ( )) ()( ))

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Bajo
LCA: Ancestro Comun
mas
I

profundo que es ancestro de v

LCA(v , v 0 ) es el nodo mas
y de v 0 .

Tiene muchas aplicaciones importantes (veremos una).

Se puede calcular en tiempo constante.

Si v es ancestro de v 0 , entonces LCA(v , v 0 ) = v , y

simetricamente
con v 0 .

Dediquemonos
al caso en que eso no ocurre:

Propiedad: v y v 0 descienden de hijos distintos de

LCA(v , v 0 ).
Propiedad: LCA(v , v 0 ) es el padre del nodo con menor
exceso en [x, y] = [min(v , v 0 ), max(v , v 0 )].
I

pues el 0 (0 del hijo del LCA que es ancestro de max(v , v 0 )

debe estar en el rango, mientras que el del LCA no.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Bajo
LCA: Ancestro Comun
mas

Dividiremos la secuencia de parentesis

en bloques y
superbloques.
Los bloques miden b = log2 n bits y los superbloques
s = 2b log2 n = log3 n bits.
La idea general es encontrar separadamente los menores
excesos en los superbloques, bloques, y posiciones
individuales involucrados en el rango [x, y ].

G. Navarro

Estructuras de Datos Compactas

 con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Arboles
Textos
Grafos

Bajo
LCA: Ancestro Comun
mas
1

6
7

11

10

12

13

14
8

15

((( )( )(( ( )( )))( ))( )(( )((( )))))

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Bajo
LCA: Ancestro Comun
mas
I

Primero calculamos los lmites de bloques y superbloques

involucrados:
sx = bx/sc, sy = by /sc, bx = bx/bc, by = by/bc.

Luego tomamos el mnimo exceso de 5 rangos:

I

Los superbloques contenidos en [x, y ], es decir

[1 + sx s, sy s].
Los bloques contenidos en [x, y ] que preceden a sx , es
decir [1 + bx b, sx s].
Los bloques contenidos en [x, y ] que siguen a sy , es decir
[1 + sy s, by b].
Las posiciones contenidas en [x, y] que preceden a bx , es
decir [x, bx b].
Las posiciones contenidas en [x, y] que siguen a by , es
decir [1 + by b, y].
G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Bajo
LCA: Ancestro Comun
mas
Resolviendo los Superbloques
I

Si almacenaramos
el mnimo exceso dentro de cada par
de superbloques, ocuparamos demasiado espacio.

Utilizaremos la propiedad siguiente: Si a < b < c < d,

entonces min[a, d] = min(min[a, c], min[b, d]).

Almacenaremos una tabla

del mnimo exceso
M[i, j] = posicion
en los superbloques [i, i + 2j 1]

Entonces
min[1 + sx s, sy s] = min(M[sx , j], M[sy 2j + 1, j])
donde j = blog(sy sx + 1)c.
G. Navarro

Estructuras de Datos Compactas

 con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Arboles
Textos
Grafos

Bajo
LCA: Ancestro Comun
mas

((( )( )(( ( )( )))( ))( )(( )((( )))))

1
7
17
19
30
1
17
19
30
1
30
G. Navarro

Estructuras de Datos Compactas

 con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Arboles
Textos
Grafos

Bajo
LCA: Ancestro Comun
mas
Espacio para los Superbloques
I

para rangos
Notar que almacenamos las soluciones solo
cuyo largo es potencia de 2.

Todo rango de largo arbitrario se resuelve superponiendo

dos rangos de largo potencia de dos que lo cubran.

Si hay t superbloques, M tiene t log t celdas.

El total de bits que ocupa es

t log t log n

log3 n

G. Navarro

log n = O

n
log n

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Bajo
LCA: Ancestro Comun
mas
Resolviendo los Bloques
I

Usamos el mismo esquema a nivel de bloques,

internamente a cada superbloque.

Como las posiciones son internas a los superbloques,

caben en 3 log log n bits.

El total de bits que se ocupa es

s
(log log n)2
n s
log 3 log log n = 12 n
(1 + o(1))
s b
b
log n

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Bajo
LCA: Ancestro Comun
mas

Resolviendo dentro de un Bloque

I

del
Usamos una tabla tipo T que almacene la posicion
mnimo exceso dentro de cada bloque posible.

T necesita O( n log log n) bits.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Bajo
LCA: Ancestro Comun
mas
Finalmente...
I

Una vez que tenemos los 5 candidatos p1 . . . p5 a posicion

del mnimo exceso...

... calculamos
m = argminpi exceso(pi )

... y respondemos
LCA(v , v 0 ) = enclose(m)

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

RMQ: Mnimos en Rangos

con arboles.

Un problema en principio sin relacion

Tengo un arreglo de numeros

A[1, n], que puedo

preprocesar.

Luego, dados rangos [i, j], necesito saber min A[i . . . j].

Se puede resolver en tiempo constante usando solamente

4n + o(n) bits extra!

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

RMQ: Mnimos en Rangos

I

El arbol
cartesiano de A[1, n] se define as:
I
I
I
I

del min A[i . . . j].

Sea m la posicion

Entonces el arbol
tiene una raz con hijos T1 y T2 .

T1 es el arbol
cartesiano de A[1, m 1].

T2 es el arbol
cartesiano de A[m + 1, n].

El arbol
tiene n nodos.

Sea H[1, n] la secuencia de las profundidades de los

nodos.
del mnimo en A[i . . . j] es la misma posicion

La posicion
del mnimo en H[i . . . j].

Pues corresponde al LCA(i, j) en el arbol

cartesiano.

G. Navarro

Estructuras de Datos Compactas

 con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Arboles
Textos
Grafos

RMQ: Mnimos en Rangos

1
3
7

2
15

21

14

12

11

13

10
17

16

20
1

18

19
6

10

11

12

13

14

15

16

17

18

19

20

21

3 2 5 4 6 5 3 1 2 0 4 3 4 2 4 5 3 1 3 2 3
1

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
G. Navarro

Estructuras de Datos Compactas

 con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Arboles
Textos
Grafos

RMQ: Mnimos en Rangos

I

Supongamos H[0] = H[n + 1] = 0 y generemos una

secuencia a partir de H:
I
I

Si H[i] > H[i 1], agregamos H[i] H[i 1] smbolos (.

Si H[i] < H[i 1], agregamos H[i 1] H[i] smbolos ).

en parentesis

El resultado es S[1, 2n], la representacion

del arbol
cartesiano.

El mnimo en H corresponde al min[x, y ] en S.

Marcamos en otro bitmap P[1, 2n] las posiciones donde

de cada valor de H en S.
comienza la codificacion

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

 con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Arboles
Textos
Grafos

RMQ: Mnimos en Rangos

1
3

15

21

14

12

11

13

10
17

16

20
1

19

18

10

12

13

14

15

16

17

18

19

20

3 2

( ( ( ) ( ( ( ) ( ( ) ) ) ) ) ( ) ) ( ( ( ( ) ( ) ) ( ( ( ) ) ) ) ( ( ) ( ) ) )

1001100110110101101000111010110101011100

G. Navarro

11

Estructuras de Datos Compactas

21

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Parte II: Otras Estructuras

Arboles
con Parentesis

Representacion

a Mnimos en Rangos
Navegando en Parentesis,
aplicacion
de Arboles
Otra Representacion
Textos
El Arreglo de Sufijos Comprimido
de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair
G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

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 .

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

A cambio, no permite conocer la profundidad de v .

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

usando Parentesis

Otra Representacion
I

Usaremos parentesis
balanceados, pero con otro
significado.

Un nodo v con hijos v1 , v2 , . . . , vk se representara como

R(v )

( ( . . . ( ) R(vk ) . . . R(v2 ) R(v1 )

| {z }
k

El nodo v corresponde a su primer parentesis.

Una hoja se representa como ).

Propiedad importante: Todo arbol

termina con ), y su
exceso interno es 1.

I
I

Agregamos un ( a S para que quede balanceada.

En total S queda con 2n parentesis

balanceados!
G. Navarro

Estructuras de Datos Compactas

 con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

Arboles
Textos
Grafos

usando Parentesis

Otra Representacion
1

6
7

11

10

12

13

14
8

15

(((( ) (( )( )())))(((( )) ( ) (( )))))

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

usando Parentesis

Otra Representacion

Utilizaremos las mismas operaciones open, close y

enclose para navegar en esta nueva representacion.

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

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

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

tamano
de subarbol.

Por lo tanto, tengo tambien

Contando () tengo cantidad de nodos internos.

Con ambos, tengo cantidad de hojas.

puede resolverse LCA practicamente

Tambien
del mismo
modo.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

con Parentesis

Representacion

Navegando entre Parentesis

de Arboles
Otra Representacion

usando Parentesis

Otra Representacion
Comprimiendo
I

es la secuencia de las
Realmente esta representacion
aridades en preorden, escritas en unario.

Se podran representar como numeros

y comprimir la

secuencia a orden cero.

Eso comprime si existe regularidad en las aridades del

arbol.

No veremos el detalle, es demasiado tecnico.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

de Secuencias
Textos: Otra Vision

...
Dado un alfabeto de tamano

... un texto T [1, n] es una secuencia sobre .

Eso no es lo mismo que una secuencia?

S, pero nos interesan otras operaciones.

P[1, m]:
Dado un patron

I
I

Contar la cantidad de ocurrencias de P en T (occ).

Ubicar esas occ ocurrencias en T .

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

de Secuencias
Textos: Otra Vision
I

Cuando el texto no es muy largo, o cambia muy

frecuentemente, lo mejor es la busqueda
secuencial.

Pero en el mejor caso esto cuesta O(

queremos
Cuando el texto es de lenguaje natural y solo
buscar palabras y frases, lo mejor es un ndice invertido.

Esto es un vocabulario de las palabras distintas, y una lista

de ocurrencias de cada una.

No es difcil conseguir poco espacio con

bitmaps comprimidos para las listas.

Otras variantes se especializan en calculo

de relevancia.

G. Navarro

n log m
).
m

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

de Secuencias
Textos: Otra Vision
I
I
I
I

I
I

Los ndices invertidos funcionan muy bien.

Son usados por buscadores como Google y Yahoo!.
Uno de sus grandes desafos es unir e intersectar listas.
Y en eso son utiles
los resultados que vimos para

relaciones binarias.
Pero no todo se puede resolver con ndices invertidos.
lenguaje natural implica muchas
La expresion
suposiciones:
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

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

de Secuencias
Textos: Otra Vision
I

Lenguaje natural excluye lenguajes muy naturales como

coreano...
el chino, japones,

y
... e incluso occidentales (aglutinantes) como aleman

finlandes!
Hay secuencias donde no existe el concepto de palabra en
absoluto:

I
I
I

Secuencias biologicas
(ADN o protenas).
Secuencias musicales (valores de pitch en archivos MIDI).

Senales
discretizadas.

Hay otras donde podran 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
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

Arboles y Arreglos de Sufijos

potente que los

Veremos un tipo de ndice mucho mas
ndices invertidos.
sobre el texto.
No hacen ninguna suposicion

Permiten buscar cualquier substring del texto.

Modelo general: considerar los n sufijos T [i, n] de T .

Todo substring de T es el prefijo de un sufijo de T .

Estas estructuras indexan el conjunto de sufijos de T y

permiten encontrar todos los que comparten un cierto
prefijo.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

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 smbolo especial $.

Cada hoja del arbol

corresponde a un sufijo distinto de T .

Y cada nodo interno a un substring repetido de T .

Se comprimen caminos unarios para garantizar O(n log n)

bits.

Se puede construir en tiempo O(n) si = O(n) es

discreto.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

$
21

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

la

19

d
16

d
13
Estructuras de Datos Compactas

_
2

d
14

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

Arboles y Arreglos de Sufijos

I

Para buscar P, se intenta bajar en el arbol

usando sus
caracteres.
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
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

Arboles y Arreglos de Sufijos

I

El arbol
de sufijos es una de las estructuras de datos mas
elegantes y utiles,
pero ocupa muchsimo espacio.

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.

Con las tecnicas

para representar arboles...

... podemos representar el arbol

de sufijos como

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

Arboles
Textos
Grafos

$
21

a
r

_
4

_
1

_
_
10
d
16

18
6

bar

_d
5 17

_ d
3
15

la

19

laba

l 20 $_
a
l 9
11 l
12
8

bar

_
7

bar

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

_
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
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

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.

Todo subarbol
del arbol de sufijos corresponde a un
intervalo del arreglo de sufijos.

Se puede hacer una busqueda

binaria de los sufijos que

empiezan con P.

El rango resultante contiene todas las respuestas...

... y corresponde al subarbol

que habramos encontrado

en el arbol
de sufijos.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

bar
21 7 12 9 20 11 8 3 15 1 13 5 17 4 16 19 10 2 14 6 18

al abar

G. Navarro

l a

al abar da$

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

Arboles y Arreglos de Sufijos

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

Pero... se puede comprimir una permutacion?.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

Parte II: Otras Estructuras

Arboles
con Parentesis

Representacion

a Mnimos en Rangos
Navegando en Parentesis,
aplicacion
de Arboles
Otra Representacion
Textos
El Arreglo de Sufijos Comprimido
de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair
G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

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.

Como
se refleja la compresibilidad de un texto en su arreglo de
sufijos?

De que tipo de compresibilidad de textos estamos hablando?

Concentremosnos
en una que es importante en la

practica:
entropa de orden k.
I

de alfabeto y sesgo en la
Orden cero captura tamano
frecuencia de los smbolos.
Ordenes mayores capturan la predictibilidad del texto que
sigue en base a lo que lo precede.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

El Arreglo de Sufijos Comprimido

La funcion
I
I

Llamemos A[1, n] al arreglo de sufijos de T [1, n].

y A1 como
Podemos pensar en A como una permutacion
su inversa.
(1..n) como
Definiremos una funcion
(i) = A1 [A[i] + 1]
(con el caso especial (i) = A1 [1] si A[i] = n).

Dicho de otro modo,

A[(i)] = A[i] + 1.

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

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

10 7 11 17 1 3 4 14 15 18 19 20 21 12 13 5 6 8 9 2 16
1

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

$ _ a b d l r

0 0 0 0 0 1 0 1 1 0 0 1 0

al abar

G. Navarro

l a

al abar da$

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

El Arreglo de Sufijos Comprimido

I

C(1..) como
Definamos la funcion
C(c) = cantidad de ocurrencias de smbolos < c en T

Implementemos C con
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

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

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))].
...

Podemos implementar la busqueda

binaria en el mismo

tiempo.

Podemos contar en tiempo O(m log n).

Pero... es tan grande como A!

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

El Arreglo de Sufijos Comprimido

I

es compresible cuando T es compresible.

En la zona de A donde los sufijos comienzan con la misma

letra, es creciente.

Por lo tanto consiste de listas crecientes.

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

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

El Arreglo de Sufijos Comprimido

I

El problema es el espacio extra o(n).

Lo podemos convertir en O(n log log ) usando

delta.
codificacion
gama de un numero
Comencemos con la codificacion
x:

I
I
I

Codificamos |x| en unario.

Luego codificamos x en binario
Por ejemplo x = 20 = 10100 se codifica como
10000 10100

El codigo
necesita 2dlog(x + 1)e bits.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

El Arreglo de Sufijos Comprimido

El codigo
delta funciona as:
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

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

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.

Agregamos valores absolutos cada O(log n) bits (agrega

O(n) bits).

Y con eso podemos decodificar cualquier (i) en tiempo

constante.
Notar que:

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

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

El Arreglo de Sufijos Comprimido

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

Estas seudo-copias en A se llaman runs.

Un run se ve en como una secuencia de valores

consecutivos.

Codificando los runs en forma especial, nos acercamos a

la entropa de orden superior.
Todo esta muy bien, pero

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

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

10 7 11 17 1 3 4 14 15 18 19 20 21 12 13 5 6 8 9 2 16
1

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

G. Navarro

l a

al abar da$

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

El Arreglo de Sufijos Comprimido

I

Haremos un sampling de celdas de A y las

almacenaremos.

Tomaremos los A[i] que apuntan a posiciones de T

multiplos
de b.

Los almacenaremos en orden creciente de i en forma

contigua, en un arreglo A0 [1, n/b].

... y tendremos un bitmap B[1, n] marcando los i

sampleados.
O( bn log n) bits.
Las posiciones y el bitmap ocuparan

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

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.

Esto debe terminar en a lo sumo b pasos.

Por lo tanto podemos conocer A[i] en tiempo O(b).

Por ejemplo, en tiempo O(log n), gastando O(n) bits extra.

Ahora s hemos reemplazado al suffix array!

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

10 7 11 17 1 3 4 14 15 18 19 20 21 12 13 5 6 8 9 2 16
1

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

l a

al abar da$

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

El Arreglo de Sufijos Comprimido

I
I
I

Ahora almacenaremos el mismo sampling de otra forma.

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
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))].

El costo total es O(b + r l).

Por ejemplo, en tiempo O(r l + log n), gastando O(n)
bits extra.
Ahora s hemos reemplazado al texto!
G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

El Arreglo de Sufijos Comprimido

I

Todas las estructuras suman nH0 (T ) + O(n log log ) bits.

Se puede probar que realmente suman

nHk (T ) + O(n log log ) bits para k moderado.

Permiten contar en tiempo O(m log n).

Permiten ubicar cada ocurrencia en tiempo O(log n).

Permiten mostrar T [l, r ] en tiempo O(r l + log n).

Estas estructuras reemplazan el suffix array pero tambien

reemplazan el texto!
Cuando logramos esto, tenemos un auto-ndice
comprimido.

I
I
I

Representa el texto.
Permite busqueda
indexada.

Ocupa espacio cercano al del texto comprimido.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

Parte II: Otras Estructuras

Arboles
con Parentesis

Representacion

a Mnimos en Rangos
Navegando en Parentesis,
aplicacion
de Arboles
Otra Representacion
Textos
El Arreglo de Sufijos Comprimido
de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair
G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

de Burrows-Wheeler (BWT)
La Transformacion

reversible de T .
Es una permutacion

Se usa como paso previo a algoritmos de compresion

como bzip2.

Pone juntos caracteres que tienen el mismo contexto.

Basta comprimir esos caracteres juntos a orden cero

para obtener nHk (T ).
deriva en un ndice comprimido para
Veremos que ademas
texto.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

de Burrows-Wheeler (BWT)
La Transformacion
I
I
I
I
I

Tomamos todos los shifts cclicos de T .

Es decir, ti ti+1 . . . tn1 $t1 t2 . . . ti1 .
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

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

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"

alabar a la alabarda$

1era "d"

bwt

araadl ll$ bbaar aaaa

2nda "r"

9na "a"

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

de Burrows-Wheeler (BWT)
La Transformacion
I
I
I
I
I

Como
invertir la BWT?
Para todo i, T = . . . L[i]F [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
I

Es el orden dado por el sufijo que sigue a c en T .

Sea entonces j = rankc (L, i).

Ese c esta en F [C(c) + j].
Se llama LF-mapping, pues lleva de la columna L a la F :
LF (i) = C(L[i]) + rankL[i] (L, i)

I
I

Entonces T [n 2] = F [LF (1)] = S[rank(D, LF (1))].

Y T [n 3] = F [LF (LF (1))], etc.
G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

El FM-Index
I

Usaremos el paralelo entre el arreglo de sufijos y la BWT.

Reemplazaremos la busqueda
binaria por la busqueda

mas
eficiente.
hacia atras,

Para buscar P[1, m] comenzaremos por pm .

El segmento de A que le corresponde es

A[C(pm ) + 1, C(pm + 1)].

En general, sabremos que las ocurrencias de P[i + 1, m]

comienzan en A[spi+1 , epi+1 ]...

... y usaremos algo similar al LF-mapping para obtener la

zona A[spi , epi ] correspondiente a P[i, m].

Terminaremos con sp1 y ep1 .

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

El FM-Index
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

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

Arboles
Textos
Grafos

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

21 7 12 9 20 11 8

bwt

T alabar a la alabarda$

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

El FM-Index
I

Luego de m iteraciones, tenemos el intervalo de P[1, m].

El costo son 2m invocaciones de rankc .

Usando un wavelet tree sobre T bwt = L,

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

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

a = 0, rank0(16) = 10

ar aadl _ l l $_bbaar_ aaaa

010011011000000100000
$_ab

dlr

a = 1, rank1(10) = 7

aaa_$_bbaa_aaaa
111000111101111
ab

$_

dl

a = 0, rank0(7) = 5

_$__
1011
$

r dl l l r
100001

aaabbaaaaaa
00011000000
_

dl l l
0111
d

rank = 5

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

El FM-Index

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 teora.

pero el suffix array comprimido es

En la practica
tambien,

muy competitivo tambien.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

Parte II: Otras Estructuras

Arboles
con Parentesis

Representacion

a Mnimos en Rangos
Navegando en Parentesis,
aplicacion
de Arboles
Otra Representacion
Textos
El Arreglo de Sufijos Comprimido
de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair
G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

Indices tipo Lempel-Ziv

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

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

Indices tipo Lempel-Ziv

LZ78
Compresion
I

Cortamos el texto en frases.

larga posible y
Cada frase consiste en la frase previa mas
una letra adicional.

Todas las frases son distintas.

Se almacenan todas las frases en un arbol

digital, donde
cada nodo es una frase.

En el peor caso se forman n0 n/ log n frases en T .

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

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

[Link]. .a .la. [Link].a$

0
_
5

1
$

a
8

11

2
b

4
d
10

G. Navarro

7
b
9

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

Indices tipo Lempel-Ziv

El LZ-Index
I

El LZ-Index almacena varias componentes:

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

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

[Link]. .a .la. [Link].a$

LZTrie

RevTrie
0

0
_

1
$

a
8

11

_
6

a
4
d
10

2
b r

$ _

7
b
9

G. Navarro

a
11

_ l

a
7

3
l
9

4
a
10

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

$a
_
_a
a
a_
al
ba
bal
dra
l
ra

[Link]. .a .la. [Link].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

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

Indices tipo Lempel-Ziv

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

P dentro de
una frase

P traslapa
2 frases

G. Navarro

5 6

P abarca
4 frases

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

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...

... se deduce que P esta contenido en B 0 tambien.

Buscamos P R en RevTrie para hallar todas las frases que

terminan con P.

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.

O(1) por cada ocurrencia.

Tardamos O(m) mas

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

Indices tipo Lempel-Ziv

Ocurrencias tipo 2
I

Si P comienza en la frase Bj y termina en Bj+1 ...

... entonces Bj termina con P[1, i] y Bj+1 empieza con

P[i + 1, m] para algun
i.

Buscamos cada P[i + 1, m] en LZTrie, obteniendo el rango

de preordenes
[xi , xi0 ].

Buscamos cada P[1, i]R en RevTrie, obteniendo el rango

de preordenes
[yi , yi0 ].

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

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

Indices tipo Lempel-Ziv

Ocurrencias tipo 3
I

de 2 frases, entonces contiene

Si P abarca mas
completamente una frase.

Como todas las frases del parsing LZ78 son distintas...

... existen a lo sumo O(m2 ) ocurrencias que verificar en T .

Se pueden verificar en tiempo O(m2 log m) usando Node y

RNode.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

Indices tipo Lempel-Ziv

I
I
I
I
I

I
I

Ids y Node son permutaciones inversas.

RIds y RNode son permutaciones inversas.
Por lo tanto, cada par ocupa (1 + )n log n bits.
La estructura de Range ocupa n log n bits.
En total el espacio es (3 + )nHk (T ) + o(n log ), para
cualquier constante .
Se puede eliminar Range para reducir el espacio a
(2 + )nHk (T ) + o(n log )...

... y los tiempos son mejores en la practica.

Para eliminar Range se verifican todos los candidatos de

LZTrie en RevTrie (usando Ids y RNode) o al reves

(usando RIds y Node).
El espacio se puede reducir incluso a
(1 + )nHk (T ) + o(n log ).
G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

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 [Link]
G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

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 [Link]
G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

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 [Link]
G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

El Arreglo de Sufijos Comprimido

de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv

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 [Link]
G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Parte II: Otras Estructuras

Arboles
con Parentesis

Representacion

a Mnimos en Rangos
Navegando en Parentesis,
aplicacion
de Arboles
Otra Representacion
Textos
El Arreglo de Sufijos Comprimido
de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair
G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Grafos
I

Un conjunto de n nodos y e aristas.

Las aristas son flechas que van de un nodo a otro.

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.

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

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

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

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Clasica

Representacion
de Grafos
Matriz de Incidencia
a
b

c d

a
b

c
d
e

d
e

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Clasica

Representacion
de Grafos

Matriz de Incidencia
I

Con n nodos y e aristas, ocupa n2 bits.

Responde existencia en tiempo O(1).

Encuentra todos los vecinos directos/reversos en O(n).

Calcula grado interior/exterior en O(n).

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

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:

d
e

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Clasica

Representacion
de Grafos

Lista de Adyacencia
I

Con n nodos y e aristas, ocupa n log e + e log n bits.

Encuentra cada vecino en tiempo O(1).

Calcula grado exterior en tiempo O(1).

Responde existencia en tiempo O(n).

Necesita otro tanto para los reversos.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

de Grafos
Compresion

binaria entre nodos...

Viendolo
como una relacion

... se puede conseguir e log(n2 /e) (1 + o(1)) bits...

... y responder todo en tiempo O(log log n).

Obtiene lo mejor de los dos mundos...

... pero aun

no es demasiado bueno para la Web.

G. Navarro

Estructuras de Datos Compactas


Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Arboles
Textos
Grafos

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

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

de Grafos
Compresion
Grafos Planares y Variantes
I
I

Con n nodos, tienen O(n) aristas.

Distintas tecnicas
para comprimirlos a O(n) bits.

La mayora consiste en dividirlos en varios arboles

y

representar estos arboles

como parentesis.

Algunas permiten acceso directo.

Hay algunos resultados para tipos especiales de grafos.

Es improbable que tengan algun

impacto en grafos Web.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

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 1316 bpe y ser mas

que la
descomprimida (por efectos de cache).

version

Para vecinos reversos necesitan el grafo traspuesto.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

de Grafos Web
Compresion
I

sesgada de grados interior/exterior (power

Distribucion
laws).
I

Localidad de referencia: la mayora de los links apuntan al

mismo site.
I
I

Una lista de adyacencia tiene baja entropa.

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

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

de Grafos Web
Compresion

Un muy buen exponente: WebGraph

I

pura.
3 bpe para compresion

6 bpe para recuperar cada vecino directo o reverso dentro

del microsegundo.

Esto considera el grafo y su traspuesto.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Parte II: Otras Estructuras

Arboles
con Parentesis

Representacion

a Mnimos en Rangos
Navegando en Parentesis,
aplicacion
de Arboles
Otra Representacion
Textos
El Arreglo de Sufijos Comprimido
de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair
G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Comprimiendo Grafos como Texto

I

Concatenar las listas de adyacencia en un texto.

Construir un autondice comprimido sobre ese texto.

Mostrar: vecinos de un nodo

Ubicar: vecinos reversos de un nodo

Contar: grado interior de un nodo

La entropa de orden k de este texto captura el modelo de

copia.
sesgada
La entropa de orden cero captura la distribucion
de grado interior.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Experimental
Comparacion

Usando el Arreglo de Sufijos Comprimido como

autondice.

Contra los resultados de WebGraph.

Sobre el mismo crawl UK, 18.5 Mnodos, 292 Mlinks.

Vecinos: resultados comparables.

Reversos: WebGraph el 10 veces mejor.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Retrieving neighbors

time per neighbor (ms)

CSA
WG
WG (fwd)

1.8
1.6
1.4
1.2
1
0.8
0.6
2

8
10
space (bpe)

G. Navarro

12

14

16

Estructuras de Datos Compactas

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Retrieving reverse neighbors

time per neighbor (ms)

30

CSA
WG

25
20
15
10
5
0
6

10
11
12
space (bpe)

G. Navarro

13

14

15

Estructuras de Datos Compactas

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Parte II: Otras Estructuras

Arboles
con Parentesis

Representacion

a Mnimos en Rangos
Navegando en Parentesis,
aplicacion
de Arboles
Otra Representacion
Textos
El Arreglo de Sufijos Comprimido
de Burrows-Wheeler y el FM-Index
La Transformacion
Indices tipo Lempel-Ziv
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair
G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

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 smbolo, hasta que todos los
pares sean unicos.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Re-Pair

aaabcaabaaabcabdabd
a
a
b
c
b
d

a
b
c
a
d
a

4
5
2
2
2
1

ab

a a Ac a Aa a Ac Ad Ad
G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

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

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

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

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

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

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

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

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Re-Pair
I

Comprime bien, descomprime rapido.

Aprovecha la propiedad de copia.

Comprime mejor si se codifica T diferencialmente.

Se comporta bien en memoria secundaria

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

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Mejorando Re-Pair

Figuras hechas por mi alumno Rodrigo Gonzalez.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Mejorando Re-Pair

Figuras hechas por mi alumno Rodrigo Gonzalez.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Mejorando Re-Pair

Figuras hechas por mi alumno Rodrigo Gonzalez.

G. Navarro

Estructuras de Datos Compactas


Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Arboles
Textos
Grafos

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

6
8
space (bits/edge)

10

12

10

15
20
25
space (bits/edge)

30

35

Resultados obtenidos por mi alumno Francisco Claude.

G. Navarro

Estructuras de Datos Compactas


Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Arboles
Textos
Grafos

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

6
8
10
space (bits/edge)

12

14

10

15
20
25
space (bits/edge)

30

35

Resultados obtenidos por mi alumno Francisco Claude.

G. Navarro

Estructuras de Datos Compactas


Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Arboles
Textos
Grafos

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

4
6
space (bits/edge)

10

10

15
20
25
space (bits/edge)

30

35

Resultados obtenidos por mi alumno Francisco Claude.

G. Navarro

Estructuras de Datos Compactas


Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Arboles
Textos
Grafos

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

4
6
space (bits/edge)

10

10

15
20
25
space (bits/edge)

30

35

Resultados obtenidos por mi alumno Francisco Claude.

G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Desafo Actual
I

Re-Pair obtiene 57 bpe y mejor compromiso

tiempo/espacio que WebGraph.

Podramos tener operaciones reversas eficientes con

1014 bpe.

binaria sobre Re-Pair?

Y si en vez tuvieramos
la relacion

I
I

I
I

Cada smbolo aparece de muchas formas distintas.

Hay que partir por encontrar que smbolos 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.170.25 bpe c/u).
Existe: Muy caro.

abierto.
Tema de investigacion
G. Navarro

Estructuras de Datos Compactas

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Eplogo
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 jerarqua de memoria.
Combinan conceptos de algoritmos y estructuras de datos
y teora 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

Arboles
Textos
Grafos

Representaciones Clasicas
y Comprimidas Generales
Comprimiendo Grafos como Texto
Comprimiendo con Re-Pair

Copyright
se distribuye bajo la licencia Attribute
Esta presentacion
Non-Commercial No Derivs de Creative Commons
[Link]
Esto significa que usted puede distribuir y comunicar
publicamente
la obra, siempre que

De credito
al autor de la obra.

No la use para fines comerciales.

No la altere, transforme, o genere una obra derivada.

El logo usado en esta presentacion

es cortesa de Jeremy Barbay,
[Link]/jbarbay.
G. Navarro

Estructuras de Datos Compactas