Transcript
Segunda parte: Indexación de texto
Antonio Fariña
Guión de la exposición
Motivación Índices invertidos Wavelet trees Wavelet trees sobre códigos densos WTDC Arrays de sufijos Arrays de sufijos comprimidos Otros indices y trabajo futuro Antonio Fariña
Motivación — Incremento del número de colecciones de texto y su tamaño Web, BD textuales, Bibliotecas digitales… — Dos necesidades: Realizar búsquedas eficientes sobre las colecciones:
Técnicas de indexación: índices invertidos, arrays de sufijos…
Disminuir el enorme consumo de espacio:
Técnicas de compresión
— Dos hechos cambian el panorama
Aparición de los compresores orientados a palabra Aparición de índices comprimidos y autoíndices
Antonio Fariña
Motivación
Estructuras de indexación: autoíndices
Índice tradicional
Índice invertido, Array de sufijos, …
Autoíndice
COUNT & LOCATE
COUNT, LOCATE & EXTRACT
— Contienen una representación implícita y comprimida
del texto:
Eliminan la necesidad de almacenarlo aparte !!!
— Ejemplos:
Wavelet Tree Array de sufijos comprimido (Sadakane), FM-Index … (http://pizzachili.dcc.uchile.cl/indexes)
Antonio Fariña
Guión de la exposición
Motivación Índices invertidos Wavelet trees Wavelet trees sobre códigos densos WTDC Arrays de sufijos Arrays de sufijos comprimidos Otros indices y trabajo futuro Antonio Fariña
Índices invertidos Estructura Vocabulario SPIRE workshop string retrieval processing information Europe even
Listas ocurr. 0 147 58 92 65 80 476 486
103 277 159 399 313 166 406 302
Vocabulario SPIRE workshop string retrieval processing information Europe even
Listas ocurr. 1 1 1 1 1 1 2 2
2 2 2 2 2
Doc2
Doc1
Texto indexado SPIRE 2008 is the 15th Annual Edition of the Symposium on string processing and information retrieval. SPIRE has its origins in the South American workshop on string processing which was first held in Belo Horizonte (Brazil, 1993). Starting in 1998, the focus of the workshop was broadened to include information retrieval due to its increasing relevance and its inter-relationship with the area of string processing. In addition, since 2000, SPIRE venue has been in Europe in even years.
Antonio Fariña
Búsquedas Palabra recuperar la lista de ocurrencias Frase intersección de listas de ocurr.
Tradeoff espacio/tiempo Granularidad: - Información posicional completa - Direccionamiento Documento/Bloque
Índices invertidos Estructura Vocabulario SPIRE workshop string retrieval processing information Europe even
Listas ocurr. 0 147 58 92 65 80 476 486
103 277 159 399 313 166 406 302
Doc2
Doc1
Texto indexado SPIRE 2008 is the 15th Annual Edition of the Symposium on string processing and information retrieval. SPIRE has its origins in the South American workshop on string processing which was first held in Belo Horizonte (Brazil, 1993). Starting in 1998, the focus of the workshop was broadened to include information retrieval due to its increasing relevance and its inter-relationship with the area of string processing. In addition, since 2000, SPIRE venue has been in Europe in even years.
Antonio Fariña
Compresión - Texto
indexado (+- 30% ratio)
·Huffman, ETDC, SCDC… - Listas de ocurrencias!!
Índices invertidos Algoritmos de intersección de listas
Intersección de 2 listas N y M — Intersección de tipo Merge
Recorrer ambas listas en paralelo e intersecar. Mejor opción si listas tienen un tamaño similar: |N| <= 20|M| Puede realizarse a medida que se van descomprimiendo.
— Aproximación Set-vs-set
Los elementos de la lista más corta se buscan dentro de la lista más larga Diferentes formas de buscar:
Búsqueda secuencial
Búsqueda binaria
Búsqueda exponencial
— Otras… Antonio Fariña
Requiere acceso directo a la lista más larga
Intersección de 2 listas: set-versus-set
Antonio Fariña
Índices invertidos Compresión de listas de ocurrencias
Listas de ocurrencias muy largas mucho espacio — Tamaño índice invertido tradicional ≈ al del texto
Debemos comprimir las listas de ocurrencias — Tener en cuenta la “posible necesidad” de acceso directo,
necesaria para búsquedas: p.ej: intersección svs de listas al buscar frases.
Diferentes estrategias de compresión de enteros: — Trivial:: manteniendo acceso directo (k-bits) — Compresión incremental:
Buena capacidad de compresión. Pérdida del acceso directo?? descompresión parcial o completa.
Antonio Fariña
Índices invertidos Compresión de listas: kbit-array (trivial)
Uso de arrays “de k-bits”
— Un entero 4 bytes = 32bits
¿Necesidad de utilizarlos todos? Solución: utilizar sólo los necesarios
Ejemplo:
Vector original: 12 enteros x 32 bits = 384 bits
11
4 2
1
10 31 4
3
9
19 25 23 16 6
5
8
7
6 10
9
numbits = log2 31 = 5 bits
15 26 11
12
01011 00100 01010 11110 01001 10011 11001 10111 10000 00110 01111 11010 1
2
3
4
5
6
7
8
9
10
11
12
Vector compactado: 12 enteros x 5 bits = 60 bits
Mantenemos accceso directo: longitud fija (i x numbits) Compresión típicamente pobre
Antonio Fariña
Índices invertidos Compresión incremental de listas
Ejemplo: 4 1
10
15
25
29
40
46
54
57
70
79
81
2
3
4
5
6
7
8
9
10
11
12
6
5
10
4
11
6
8
3
13
9
2
2
3
4
5
6
7
8
9
10
11
12
Codificación incremental
4 1
Codificación variable
C4 C6 C5 C10 C4 C11 C6 C8 C3 C13 C9 C2 1
2
3
Antonio Fariña
4
5
6
7
8
9
10
11
12
Índices invertidos Compresión incremental de listas
Ejemplo: 4 1
10
15
25
29
40
46
54
57
70
79
81
2
3
4
5
6
7
8
9
10
11
12
6
5 Codificación 10 4 11 6 8 — incremental
3
13
9
2
2
3 4 la magnitud 5 6 7 los 8números 9 10 Reduce de
11
12
Codificación incremental
4 1
Codificación variable
— Codificación de los incrementos con técnicas que usan códigos
de longitud variable
C4 C6 C5 C10 C4Bytecodes C11 C6 C8 C3 C13 C9 C2 1
2
3
4
10
11
12
Inconveniente: perdemos el acceso directo. —
Antonio Fariña
6 8 9 7 5 Golomb-rice codes
ej: ¿cúal es el 4º entero de la secuencia original?
Índices invertidos Compresión incremental de listas-occ — Se basa en 2 factores principales
Las listas contienen valores en orden creciente Las diferencias son menores en las listas más largas
Almacenemos diferencias en lugar de valores absolutos Comprimámoslas con códigos de longitud variable Original Posting list Diffs
4
10 15 25 29 40 46 54 57 70 79 82
1
2
3
4
5
6
7
8
9
10
4
6
5
10
4
11
6
8
3
13
11
12
9
3 Descompresión
Codif long. variable
c4 c6 c5 c10 c4 c11 c6 c8 c3 c13 c9 c3 completa
Sampling absoluto + codif long. variable
4 c6 c5 c10
Antonio Fariña
57
29 c11 c6 c8
Acceso directo
c13 c9 c3
Descompresión parcial
Índices invertidos Compresión incremental de listas-occ — Se basa en 2 factores principales
Las listas contienen valores en orden creciente Las diferencias son menores en las listas más largas
Codificación incremental Reduce la magnitud de los números Almacenemos diferencias en lugar de valores absolutos Codificación de los incrementos con técnicas que usan códigos —Comprimámoslas con códigos de longitud variable de longitud variable
Original 4 10 Bytecodes Posting list Diffs
15 25 29 40 46 54 57 70 79 82 (orientadas a byte) 12 1 2 3 4(orientados 5 6 a bit. 7 Parametrizables 8 9 10 para 11 cada Golomb-rice codes lista) 4 6 5 10 4 11 6 8 3 13 9 3 Otras variantes más nuevas (simple-9, carryover-12)…
Inconveniente: perdemos el acceso directo. Descompresión Codif long. variable — ej: ¿cúal el 4º c5 entero de lac4 secuencia original? c4 esc6 c10 c11 c6 c8 c3 c13 c9 c3 completa —
Requiere el uso de estructuras de sampling
Sampling absoluto + codif long. variable
c6 c5 c10 Antonio Fariña
57
29
4
c11 c6 c8
Acceso directo
c13 c9 c3
Descompresión parcial
Índices invertidos Compresión incremental + bytecodes — Orientada a bytes — Asigna a cada entero un nº variable de bytes. Siendo n el
número a comprimir: Si 0 < n < 128 1 byte Si 128 ≤ n < 1282 2 bytes Si 1282 ≤ n < 1283 3 bytes — Ejemplo: 65 1
11
274
6
47
401
80081
25
4
2
3
4
5
6
7
8
9
C65 C11 C274 C6 C47 C401 C80081 C25 C4 1
2
Antonio Fariña
3
4
5
6
7
8
9
Índices invertidos Compresión incremental + golomb-rice codes
Golomb codes (Golomb):
— Orientada a bits
Variables: — n: entero a comprimir — m: se fija de antemano. Múltiplo de 2 (Golomb Rice) — Cociente q: q = n/m — Resto r: r = n mod m — c = log2 m
— El código consta de 2 partes:
Codificar q en unario y añadir ‘0’ C2 = 110, Codificar r con c bits en binario.
Ejemplo: Codificar n=9, con m=4: q = 9/4 = 2 11 0 r = 9 mod 4 = 1 c = log2 4 = 2
Antonio Fariña
11 0 01
C4 = 11110
Índices invertidos golomb-rice codes- parámetros
b: parámetro local (= 0.69 * avg) o global Antonio Fariña
Índices invertidos Estructuras de datos: sampling — Códigos de long variable para gaps(golomb codes, bytecodes,…)
Estructuras de sampling para soporte de “acceso rápido” a las listas comprimidas (necesario para algoritmos tipo svs/lookup) 2 opciones:
Sampling a intervalos regulares de la posting-list [Moffat-Culpepper ’07] F-search en el 1er nivel + descompresión secuencial buckets de tamaño fijo* * Dada una lista L, el período de sampling se calcula como K*(log2 |L|), siendo K un parámetro del método. L
Posting list Original
4
10 15 25 29 40 46 54 57 70 79 81
1
2
3
4
5
6
k
7
8
k
PeriodoSampling = k x (log2 L)
4 ptr1 29 ptr2 57 ptr3 1
9
5
C6 C5 C10 C11 C6 C8 C13 C9 C2 2
3
Antonio Fariña
4
6
7
8
10
11
12
9
10 k
11
12
Índices invertidos Estructuras de datos: sampling — Códigos de long variable para gaps(golomb codes, bytecodes,…)
Estructuras de sampling para soporte de “acceso rápido” a las listas comprimidas (necesario para algoritmos tipo svs/lookup) 2 opciones:
Sampling a intervalos regulares de la posting-list [Moffat-Culpepper spire’07] Sampling regular de los valores del dominio [Sanders-Trasier alenex’07] Los valores pertenecerán a un bucket en función de sus K bits más significativos buckets de diferente tamaño. Acceso directo al bucket (no F-search en 1er nivel) + descompresión sec. Bucket. - Algoritmo lookup de Sanders&Trasier (tipo merge, pero procesando por buckets). L
Posting list Original
4 1
10 15 25 29 31 46 54 64 70 79 100 2
3
4
Siendo: U = máximo valor en cualquier lista
5
6
7
ptr1
8
9
ptr2
…
B = un parámetro prefijado K = el número de bits más significativos (determina en qué bucket se almacena cada valor de la lista)
Antonio Fariña
0<=x<=2^k
10
11
ptr2^k
12
B=2
K= log(u*B/|L|)=4
(i-1)2^k<=x<=i*2^k
x mod 2^k se almacena en los buckets (posiblemente comprimido con bc/rice codes,…)
Intersección de 2 listas: lookup
Valor dentro del bucket bN Dentro del mismo bucket ??
Antonio Fariña
Índices invertidos Otras variantes: bitmaps + cod variable
Versión híbrida
Lista ocurrencias N bloques 1 1
Texto
Cod Incremental Moffat
N bloques
bitmaps
Vocabulario
Uso de mapas de bits para palabras frecuentes — Acceso directo lista de ocurrencias representada como bitmap
Ahorramos acceder a la estructura en 2 niveles + rápido
Interesa bitmap si “muchos” 1’s
— Algoritmo creación bitmaps: ahorro de espacio
(Culpepper&Moffat ADCS’2007 listas long > Max/8)
En definitiva: búsquedas más rápidas y menos espacio !! Antonio Fariña
Experimental results: List intersection (doc size 2.4kb) 60,975,676
1.6
68,732,645 63,811,100
CPU time for intersection
1.4 1.2
53,880,883
1
56,744,691
64,795,606
merge svs-bin k=2 svs-bin k=32 svs-seq k=32 repair (no sampling) lookup B=64 repair(sample k=1)
0.8 0.6 0.4 0.2 0
— — — —
0
100
200
300 400 500 600 longer/shorter list length
Lookup faster but more space Merge good if similar list lengths Svs good choice. Improves results as lengths vary Repair good compression. Sampling good for x>120 Performing similar to bc+svs (with large sampling values)
Antonio Fariña
700
800
900
Experimental results: List intersection (zoomed) 2 1.8
CPU time for intersection
1.6 1.4 1.2 1 0.8
merge svs-bin k=2
0.6
svs-bin k=32 svs-seq k=32
0.4
repair (no sampling)
0.2 0
lookup B=64 repair(sample k=1)
0
10
Antonio Fariña
20
30
40 50 60 70 longer/shorter list length
80
90
100
Guión de la exposición
Motivación Índices invertidos Wavelet trees Wavelet trees sobre códigos densos WTDC Arrays de sufijos Arrays de sufijos comprimidos Otros indices y trabajo futuro Antonio Fariña
Wavelet Tree
Conceptos básicos CONSTRUCCIÓN
Wavelet tree: distribuye los bits que forman el código de cada símbolo en los distintos niveles del árbol
TEXTO
A B A C D A C 00 01 00 10 11 00 10
SÍMBOLO A B C D
Antonio Fariña
CÓDIGO 00 01 10 11
WAVELET TREE A B A C D A C 0 0 0 1 1 0 1 0
A B A A 0 1 0 0
1
C D C 0 1 0
Wavelet Tree
Conceptos básicos BÚSQUEDA
¿Dónde aparece la 1ª ‘D’?
TEXTO
A B A C D A C
SÍMBOLO A B C D
CÓDIGO 00 01 10 11
WAVELET TREE A B A C D A C ¿dónde está 0 0 0 1 1 0 1 el 2º ‘1’? en la 5ª pos. 0 1 A B A A 0 1 0 0
C D C 0 1 0 ¿dónde está el 1º ‘1’? en la 2ª pos.
es el segundo bit del nodo1
Antonio Fariña
Wavelet Tree
Conceptos básicos RECUPERACIÓN DE TEXTO
¿Cuál es el siguiente símbolo? ¿Qué símbolo aparece en la 6ª posición? TEXTO
WAVELET TREE
A B A C D A C
SÍMBOLO A B C D
CÓDIGO 00 01 10 11
A B A C D A C 0 0 0 1 1 0 1 0
A B A A 0 1 0 0
1
¿Cuántos ‘0’s hay hasta la posición 6? es el 4º ‘0’
C D C 0 1 0
¿Qué bit está en cuarto lugar del nodo0? Hay un 0 El código leído es 00 Antonio Fariña
Wavelet Tree
Conceptos básicos RECUPERACIÓN DE TEXTO
¿Cuál es el siguiente símbolo? ¿Qué símbolo aparece en la 7ª posición? TEXTO
WAVELET TREE
A B A C D A C
SÍMBOLO CÓDIGO A 00 Para buscar: 01 B C 10 D 11
A B A C D A C 0 0 0 1 1 0 1 0
Para recuperar el texto:
A B A A 0 1 0 0
1
¿Cuántos ‘1’s hay hasta la posición 7? es el 3er ‘1’
C D C 0 1 0
¿Qué bit está en 3er lugar del nodo1? Hay un 0 El código leído es 10 Antonio Fariña
Wavelet Tree Conceptos básicos USO DEL ÍNDICE
La búsqueda y recuperación de texto se apoyan en dos operaciones: — ¿Cuántos ‘0’s ó ‘1’s hay hasta determinada posición en un nodo?
rankb(i) = número de veces que aparece el bit b entre las posiciones 1 e i (incluidas)
— ¿Dónde está el j-ésimo 0 ó 1 en un nodo?
selectb(j) = posición de la j-ésima aparición del bit b
Antonio Fariña
Conceptos básicos: Rank/Select
RANK
B= 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
—
rank1(6) =
3
¿Cuántos ‘1’s hay hasta la posición 6?
rankb(i) = número de veces que aparece el bit b entre las posiciones 1 e i (incluidas)
Antonio Fariña
Conceptos básicos: Rank/Select RANK
B= 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
—
rank1(6) = 3
—
rank0(16) =
10
¿Cuántos ‘0’s hay hasta la posición 16?
rankb(i) = número de veces que aparece el bit b entre las posiciones 1 e i (incluidas)
Antonio Fariña
Conceptos básicos: Rank/Select SELECT
B= 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
—
select1(2) =
5
¿dónde está el 2º ‘1’?
selectb(j) = posición de la j-ésima aparición del bit b
Antonio Fariña
Conceptos básicos: Rank/Select SELECT
0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
—
select1(2) = 5
—
select0(9) =
14
¿dónde está el 9º ‘0’?
selectb(j) = posición de la j-ésima aparición del bit b
Antonio Fariña
Conceptos básicos: Rank/Select Implementando Rank en O(1) Vector de bits D = {10001010101011100011100000001010} Se implementa sobre un array de enteros (32 bits ó 64bits) Se construye el TAD bitVector Operaciones setBit(posición, valor) getBit(posición, valor) rank1(posición)
Antonio Fariña
Conceptos básicos: Rank/Select Implementando Rank en O(1) Vector de bits D Calcular rank1 en tiempo constante Se divide la secuencia binaria en superbloques de 256 bits (1 byte = 256 valores) Se almacena un valor para cada superbloque, en un directorio de primer nivel Valor = Número de bits a 1 antes del inicio del superbloque
Antonio Fariña
Conceptos básicos: Rank/Select Implementando Rank en O(1) Vector de bits D Dentro de un superbloque Se divide cada superbloque en 8 bloques de 32 bits Se almacena un valor para cada bloque, en un directorio de segundo nivel Valor = Número de bits a 1 dentro del superbloque y antes del inicio del bloque
Antonio Fariña
Conceptos básicos: Rank/Select Implementando Rank en O(1) rank1( D , p ) = Ds[ p / 256 ] + Db[ p / 32 ] + rank1(blq, i) Donde blq representa el bloque (32 bits) de la secuencia D que contiene a p, e i = p mod 32
Falta por calcular rank1(blq, i) Se transforma blq en blq’ de modo que rank1(blq, i) = rank1(blq’, 32) Desplazamos blq hacia la derecha 32 – i posiciones Se calculan el número de bits a 1 en blq’ Ej.: Queremos obtener rank1(blq, 25)
Antonio Fariña
Conceptos básicos: Rank/Select Implementando Rank en O(1) rank1( D , p ) = Ds[ p / 256 ] + Db[ p / 32 ] + rank1(blq, i) Donde blq representa el bloque (32 bits) de la secuencia D que contiene a p, e i = p mod 32
Falta por calcular rank1(blq, i) Se transforma blq en blq’ de modo que rank1(blq, i) = rank1(blq’, 32) Desplazamos blq hacia la derecha 32 – i posiciones Se calculan el número de bits a 1 en blq’ Ej.: Queremos obtener rank1(blq, 25)
Antonio Fariña
Conceptos básicos: Rank/Select Implementando Rank en O(1) rank1( D , p ) = Ds[ p / 256 ] + Db[ p / 32 ] + rank1(blq, i) Donde blq representa el bloque (32 bits) de la secuencia D que contiene a p, e i = p mod 32
Falta por calcular rank1(blq, i) Se transforma blq en blq’ de modo que rank1(blq, i) = rank1(blq’, 32) Desplazamos blq hacia la derecha 32 – i posiciones Se calculan el número de bits a 1 en blq’ Ej.: Queremos obtener rank1(blq, 25)
Antonio Fariña
Conceptos básicos: Rank/Select Implementando Rank en O(1) Contar el número de bits a 1 en un bloque de 32 bits Se divide el bloque en 4 sub-bloques (de 8 bits cada uno)
Se suman el número de bits a 1 en cada uno de los sub-bloques Se utiliza una tábla global (OnesInByte) Contiene el número de bits a 1 para cada posible secuencia de 8 bits Se accede directamente por el valor del byte
Antonio Fariña
Conceptos básicos: Rank/Select Implementando Rank en O(1) Tabla OnesInByte
En nuestro ejemplo:
Antonio Fariña
Wavelet Tree
Conceptos básicos BÚSQUEDA
¿Dónde aparece la 1ª ‘D’?
TEXTO
A B A C D A C
SÍMBOLO A B C D
CÓDIGO 00 01 10 11
WAVELET TREE
select1(2)=5
¿dónde está A B A C D A C el 2º ‘1’? 0 0 0 1 1 0 1 en la 5ª pos. 0
A B A A 0 1 0 0
1
select1(1)=2 C D C ¿dónde está 0 1 0 el 1º ‘1’? en la 2ª pos.
es el segundo bit del nodo1
Antonio Fariña
Wavelet Tree
Conceptos básicos BÚSQUEDA
¿Dónde aparece la 1ª ‘D’?
TEXTO
A B A C D A C
SÍMBOLO CÓDIGO A Para00 buscar: 01 B C 10 D 11
WAVELET TREE A B A C D A C ¿dónde está 2º ‘1’? 1(2)=5 0 0 0 1 1 0 1 elselect en la 5ª pos. 0 1 select
A B A A 0 1 0 0 Para recuperar el texto:
C D C ¿dónde está 0 1 0 rank el 1º ‘1’? select 1(1)=2 en la 2ª pos.
es el segundo bit del nodo1
Antonio Fariña
Wavelet Tree Wavelet tree (original) sobre cualquier alfabeto Σ Ejemplo:
T = la_cabra_abracadabra
Σ = {_, a, b, c, d, l, r}
1ª mitad rama izq. 2ª mitad rama der la _ cabra _ abracadabra B= 10000010000100010010 _abc
dlr
a _ caba _ abacaaba B’= 001010001010010 _a
dl
bc
a _ aa _ aaaaa
a
b
r
ld 10
cbbcb 10010
B’’= 1011011111 _
lrrdr 01101
c
d
l
Localizar el carácter que ocupa la posición 13 del texto? bajar Dónde está la 4ª a? subir Antonio Fariña
Wavelet Tree Wavelet tree (original) sobre cualquier alfabeto Σ RECUPERACIÓN DE TEXTO
Σ = {_, a, b, c, d, l, r} Localizar el carácter que ocupa la posición 13 del texto Se recorre el árbol de arriba a abajo Se lee el bit i, que nos indica a qué rama del hijo movernos rankb(B,i) obtiene la posición del hijo que hay que mirar Se llega a la hoja el carácter es la quinta “a” Antonio Fariña
Wavelet Tree Wavelet tree (original) sobre cualquier alfabeto Σ Σ = {$,_, a, b, d, l, r} (
)= 14
araadl_ l l $_bbaar_aaaa 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 =B $_ab (
)= 9
aaa_$_bbaa_aaaa
rd l l l r
1 1 1 0 0 0 1 1 1 1 0 1 1 1 1 = B’
1 0 0 0 0 1
$_
ab (
$
dlr
dl
)=
_$__
aaabbaaaaaa
1 0 1 1
0 0 0 1 1 0 0 0 0 0 0 = B’’
_
a
b
r
d l l l 0 1 1 1 d
l
¿Qué texto fue comprimido con este wavelet tree? Antonio Fariña
Wavelet Tree Wavelet tree (original) sobre cualquier alfabeto Σ Σ = {_, a, b, c, d, l, r}
¿Qué texto fue comprimido con este wavelet tree? Antonio Fariña
Guión de la exposición
Motivación Índices invertidos Wavelet trees Wavelet trees sobre códigos densos WTDC Arrays de sufijos Arrays de sufijos comprimidos Otros indices y trabajo futuro Antonio Fariña
Wavelet tree sobre Dense Code (WTDC)
Características básicas del Wavelet Tree sobre Dense Code (WTDC) — Estrategia de wavelet tree Estructura en árbol que permite indexar caracteres — Basado en palabras En vez de codificar cada carácter se codifica cada palabra — Orientado a bytes Cada nodo es una secuencia de bytes — Codificación usando una técnica de compresión (ETDC) End-Tagged Dense Code (ETDC) condiciona la forma del árbol
Antonio Fariña
WTDC
End-Tagged Dense Code (ETDC)
Recordando End-Tagged Dense Code (ETDC) — Basado en palabras y orientado a bytes:
Asigna a cada palabra un código que es una secuencia de bytes
— Compresor estadístico: asigna códigos más cortos a palabras
más frecuentes:
Palabras muy frecuentes 1 byte Palabras de frecuencia media 2 bytes Palabras muy poco frecuentes 3 bytes
— Utiliza un bit de marca (en el último byte del código)
Permite realizar búsquedas eficientes en texto comprimido y descompresión desde cualquier posición
— Comprime el texto aproximadamente en un 30%
Antonio Fariña
WTDC
Creación del autoíndice CONSTRUCCIÓN
Wavelet tree: distribuye los bytes que forman el código de cada símbolo en los distintos niveles del árbol
TEXTO
A F C B B C D A E 10 0111 0010 11 11 0010 001110 0110
SÍMBOLO A B C D E F
Antonio Fariña
CÓDIGO 10 11 00 10 00 11 01 10 01 11
WAVELET TREE A F C B B C D A E 10 01 00 11 11 00 00 10 01 00
C C D 10 10 11
01
F E 11 10
10
11
WTDC
Uso del autoíndice BÚSQUEDA
¿Dónde aparece la 1ª ‘D’?
TEXTO
A F C B B C D A E SÍMBOLO A B C D E F
CÓDIGO 10 11 00 10 00 11 01 10 01 11
¿dónde está el 3º ‘00’? en la 7ª pos.
WAVELET TREE A F C B B C D A E 10 01 00 11 11 00 00 10 01 00
01
C C D 10 10 11
¿dónde está el 1º ‘11’? en la 3ª pos. es el 3º byte del nodo00
Antonio Fariña
F E 11 10
WTDC
Uso del autoíndice RECUPERACIÓN DEL TEXTO
¿Cuál es el siguiente símbolo? ¿Qué símbolo aparece en la 8ª posición?
TEXTO
A F C B B C D A E SÍMBOLO A B C D E F
Antonio Fariña
CÓDIGO 10 11 00 10 00 11 01 10 01 11
WAVELET TREE A F C B B C D A E 10 01 00 11 11 00 00 10 01 00
01
El código leído es 10
C C D 10 10 11
F E 11 10
WTDC
Uso del autoíndice RECUPERACIÓN DEL TEXTO
¿Cuál es el siguiente símbolo? ¿Qué símbolo aparece en la 9ª posición?
TEXTO
es el 2º ‘01’ WAVELET TREE
A F C B B C D A E SÍMBOLO A B C D E F
CÓDIGO 10 11 00 10 00 11 01 10 01 11
¿Cuántos ‘01’s hay hasta la posición 9?
A F C B B C D A E 10 01 00 11 11 00 00 10 01 00
C C D 10 10 11
01
F E 11 10
¿Qué byte está en 2º lugar del nodo01? Hay un 10 El código leído es 01 10 Antonio Fariña
WTDC
Uso del autoíndice RECUPERACIÓN DEL TEXTO
¿Cuál es el siguiente símbolo? ¿Qué símbolo aparece en la 9ª posición?
TEXTO
es el 2º ‘01’ WAVELET TREE
A F C B B C D A E SÍMBOLO ParaCÓDIGO buscar: A 10 B 11 00 10 C D Para recuperar 00 11 el texto: E 01 10 F 01 11
¿Cuántos ‘01’s hay hasta la posición 9?
A F C B B C D A E 10 01 00 11 11 00 00 10 01 00
C C D 10 10 11
01
F E 11 10
¿Qué byte está en 2º lugar del nodo01? Hay un 10 El código leído es 01 10 Antonio Fariña
Wavelet tree sobre Dense Code (WTDC)
Propiedades claves del WTDC — Árbol no balanceado — Árbol no binario, un hijo por cada tipo de byte — Altura máxima: 3 niveles — Ocupa un 30% del tamaño del texto original y además
está indexado — Reto principal: operaciones de rank y select sobre
secuencias de bytes Antonio Fariña
Wavelet tree sobre Dense Code (WTDC)
Propiedades claves del WTDC — Árbol no balanceado — Árbol no binario, un hijo por cada tipo de byte — Altura máxima: 3 niveles — Ocupa un 30% del tamaño del texto original y además
está indexado — Reto principal: operaciones de rank y select sobre
secuencias de bytes Antonio Fariña
Wavelet tree sobre Dense Code (WTDC)
Propiedades claves del WTDC — Árbol no balanceado — Árbol no binario, un hijo por cada tipo de byte — Altura máxima: 3 niveles — Ocupa un 30% del tamaño del texto original y además
está indexado — Reto principal: operaciones de rank y select sobre
secuencias de bytes Antonio Fariña
Wavelet tree sobre Dense Code (WTDC)
Propiedades claves del WTDC — Árbol no balanceado — Árbol no binario, un hijo por cada tipo de byte Descompresión:
rank
Búsquedas:
select
— Altura máxima: 3 niveles
— Ocupa un 30% del tamaño del texto original y además
está indexado — Reto principal: operaciones de rank y select sobre
secuencias de bytes Antonio Fariña
Implementación eficiente de rank y select sobre secuencias de bytes
Operaciones sobre vectores de bytes — rankb(i) = número de veces que aparece el byte b en hasta la posición i — selectb(j) = posición de la j-ésima aparición del byte b
3 255 3 1
2
3
61 66 4
5
3 6
25 66 33 34 66 27 7
8
9
10
11
rank66(10) = 2
12
3 222 61 13
14
15
select3(4)=13
Rank y select sobre bits se puede realizar en O(1)
Problema para secuencias de bytes: no hay implementaciones eficientes — Existen aproximaciones basadas en las soluciones para secuencias de
bits, pero no obtienen un buen balance espacio - tiempo
Antonio Fariña
rank y select sobre secuencias de bytes Uso de Sampling
Se almacena la secuencia de bytes como un array de enteros
— Se consigue recorrer la secuencia de forma más eficiente
Adicionalmente, se construye una estructura de bloques
— Cada bloque almacena 256 contadores, uno por cada valor de byte — contador[b] guarda el nº de veces que aparece b antes del inicio del
bloque
rankb(i) contador [ i / Tbloque][b] + contar (i – i mod Tbloque, i)
Antonio Fariña
rank y select sobre secuencias de bytes
Nueva aproximación
Es parametrizable: Trade-off espacio/tiempo ¿ rank12 (17) ?
Antonio Fariña
=4
Wavelet-trees y códigos orientados a byte Sincronismo, un valor añadido
Al distribuir los bytes en forma de wavelet-tree — Siempre sabemos dónde comienza un código
El comienzo está en el primer nivel !!
Ya tenemos una marca de sincronización Podemos utilizar otros byte-codes, no sólo ETDC — Plain Huffman o RPBC (Moffat & Culpepper, Spire 2005)
Mejor compresión (+- 1%) Mismas propiedades
Antonio Fariña
Resultados experimentales Marco experimental
Se han realizado pruebas sistemáticas sobre textos reales en lenguaje natural extraídas del TREC — 10 corpus de distintos tamaños (desde 2 MB a 1 GB) — Diferente naturaleza (noticias en formato XML, texto plano, etc.)
La máquina utilizada es: — Intel Pentium IV 3.00 GHz (16Kb L1 + 1024Kb L2 caché) — 4 GB dual-channel DDR-400Mhz RAM — Debian GNU/Linux (kernel versión 2.4.27) — El compilador usado es gcc versión 3.3.5, indicando las optimizaciones
del compilador -O9.
Antonio Fariña
Resultados experimentales Parámetros a medir
Si consideramos el WTDC como un compresor, los parámetros más importantes que se deben medir: — Tiempo de compresión — Tiempo de descompresión
— Memoria usada para
comprimir
— Ratio de compresión
Considerando el WTDC como un índice, se debe medir: — Tiempo de búsqueda de:
Count Locate Display
Antonio Fariña
— Tiempo de carga — Memoria usada para buscar
Resultados experimentales
WTDC como compresor
Ratio de compresión
48 WTDC ETDC gzip
46
Ratio de compresión (%)
44 42 40 38 36 34 32 30
CALG
FT91
Antonio Fariña
CR
FT92
ZIFF FT93 Corpus utilizado
FT94
AP
FTALL
ALL
Resultados experimentales
WTDC como compresor
Ratio de compresión
Differencias mínimas (+- 0.01%)
Compression ratio (ZIFF corpus) Compression ratio (%)
34.00 33.80 33.60 33.40 33.20 33.00 32.80 32.60 32.40
33.77
32.88
33.77
32.88
32.88
PH
ETDC Method used
Antonio Fariña
Original
Reorganized with WT
32.89
RPBC
Resultados experimentales
WTDC como compresor
Tiempo de compresión 160
WTDC ETDC gzip
Tiempo de compresión (sg.)
140 120 100 80 60 40 20 0
CALG
FT91
Antonio Fariña
CR
FT92
ZIFF FT93 Corpus utilizado
FT94
AP
FTALL
ALL
Resultados experimentales
WTDC como compresor
Tiempo de compresión
Prácticamente idénticos (2% - 4% peor)
Compression time (ZIFF corpus) 14.00 Compression time (s)
12.00
11.03
11.47
10.97
11.20
11.02
11.39
10.00 8.00 6.00 4.00 2.00 0.00 PH
ETDC Method used
Antonio Fariña
Original
Reorganized with WT
RPBC
Resultados experimentales
WTDC como compresor
Tiempo de descompresión
Tiempo de descompresión (sg.)
25 WTDC ETDC gzip
20
15
10
5
0
CALG
FT91
Antonio Fariña
CR
FT92
ZIFF FT93 Corpus utilizado
FT94
AP
FTALL
ALL
Resultados experimentales
WTDC como compresor
Tiempo de descompresión Mayores diferencias, pero todavía “muy rápido” (10% - 20%) Decompression time (ZIFF corpus) Decompression time (s)
3.50 3.00 2.50
2.66
2.31
2.25
2.69
2.84 2.29
2.00 1.50 1.00 0.50 0.00 PH
ETDC Method used Original
Antonio Fariña
Reorganized with WT
RPBC
Resultados experimentales
WTDC como índice
Tiempo de contar el número de ocurrencias de una palabra (Corpus AP) 1%
contar ocurrencias 450
403,35
400 350 300
t (ms)
250
208,05 208,05
200
143,71 143,71
150 100 50 0,05 0
0,037935
0,045464
0,037935
0,045464
0,005492 0,005492
143,56 143,56
0,00021857 0,00021857
Palab. 1 byte
Palab. 2 bytes
Palab. 3 bytes
Palab. 1 ocurr
ETDC
403,35
208,05
143,71
143,56
WTDC
0,037935
0,045464
0,005492
0,000218571
Antonio Fariña
Resultados experimentales
WTDC como índice
Tiempo de buscar la primera ocurrencia de una palabra (Corpus AP) 1%
buscar 1ª 60
54,42
54,42
50 40
t (ms)
18,07
30 20
0,7857
0,5 10
0
0,0714 0,0714 0,0008457
0,7857 0,033571
18,07
0,095071 0,095071
0,102 0,102
1 byte
2 bytes
3 bytes
1 ocurr
ETDC
0,0714
0,7857
18,07
54,42
WTDC
0,0008457
0,033571
0,095071
0,102
Antonio Fariña
Resultados experimentales
WTDC como índice
Tiempo de localizar las 10.000 primeras posiciones de una palabra (Corpus AP) 1%
localizar 10.000 ocurrencias 160
149,14 149,14
140 120
110,0714 110,0714
109,642 109,642
100
t (ms)
80 60 40 20 0
40,043 40,043 29,14 29,14 7,5914 7,5914
0,2095 0,2095
0,102143 0,102143
1 byte
2 bytes
3 bytes
1 ocurr
ETDC
29,14
149,14
109,642
110,0714
WTDC
7,5914
40,043
0,2095
0,102143
Antonio Fariña
Resultados experimentales
WTDC como índice
Tiempo de recuperar los 10.000 primeros snippets de una palabra (Corpus AP) 1%
recuperar 10.000 snippets 3 2,4642
2,5 2
t (s)
1,5
1,1657
1 0,5 0,05485 0
0,22428
0,15907
0,010257
0,15928 0,0003643
1 byte
2 bytes
3 bytes
1 ocurr
ETDC
0,05485
0,22428
0,15907
0,15928
WTDC
2,4642
1,1657
0,010257
0,00036429
Antonio Fariña
Resultados experimentales
WTDC como índice
Tiempo de recuperar los 10.000 primeros snippets de una palabra (empeorando un 6% el ratio de compresión del texto en memoria) 6%
recuperar 10.000 snippets 3 2,5 2
t (s)
1,5 1 0,5 0,05485 0
0,1835
0,22428 0,091429
0,15907 0,00071429
0,15928 0,0003643
1 byte
2 bytes
3 bytes
1 ocurr
ETDC
0,05485
0,22428
0,15907
0,15928
WTDC
0,1835
0,091429
0,00071429
0,000030214
Antonio Fariña
Resultados experimentales
WT** como índice
Búsquedas (ALL corpus) Memoria Count (ms) Locate (ms) 1ª occ
Locate (s) todas
Snippet (s) 10 palabras
PH
35.13%
2605.6
48.861
2.648
7.955
ETDC
35.95%
1027.4
22.933
0.940
1.144
RPBC
35.14%
1996.3
41.66
2.009
7.283
WPH
35.13%
238.5
17.173
0.754
72.068
WTDC
35.96%
221.9
17.882
0.762
77.845
WRPBC
35.14%
238.7
17.143
0.773
75.435
WPH+
36.11%
0.015
0.017
0.123
5.339
WTDC+
36.95%
0.015
0.014
0.129
6.130
WRPBC+
36.09%
0.015
0.018
0.125
5.036
Antonio Fariña
Resultados experimentales
WT** como índice
Búsquedas (ALL corpus) Memoria Count (ms) Locate (ms) 1ª occ 48.861
Snippet (s) 10 palabras
2.648
7.955
PH
35.13%
ETDC
• WT+ mejora todas las22.933 capacidades 0.940 de búsqueda 1.144 si la 1027.4 35.95% técnica “de partida” no se auto-sincronizaba. 1996.3 41.66 2.009 7.283 35.14%
RPBC
2605.6
Locate (s) todas
WTDC+
238.5 adicionales 17.173 0.754 72.068 35.13% • Sin estructuras (memoria extra), los WT’s obtienen 221.9 resultados pobres de recuperar 17.882a la hora 0.762 77.845 35.96% snippets. 238.7 17.143 0.773 75.435 35.14% • Con un poco de espacio extra (1%),0.123 ETDC es todavía 0.015 0.017 5.339 36.11% mejor que WTDC+ al recuperar snippets. Aumentando 0.015 0.014 0.129mejora a6.130 36.95% ese espacio hasta un 6% extra WTDC+ ETDC.
WRPBC+
36.09%
WPH WTDC WRPBC WPH+
Antonio Fariña
0.015
0.018
0.125
5.036
Resultados experimentales
Indexación implícita
Comparación frente a otros índices: — WTDC+ variando el tamaño extra disponible — Índice invertido comprimido sobre texto comprimido con ETDC
Direccionamiento a bloques parámetro Índice comprimido como en Culpepper & Moffat, SPIRE’07 parámetro
Comparamos 2 alternativas — II-1 vs WT-1 (usando el 45% de lo que ocupaba el texto original) — II-2 vs WT-2 (usando el 39% de lo que ocupaba el texto original)
Medimos tiempos para locate y snippets, usando — Palabras de distintas frecuencias — Frases de distintas longitudes
Antonio Fariña
Resultados experimentales
Indexación implícita
Búsqueda de 100 palabras simples (corpus ALL) WT-1 Word freq. Locate (s)
II-1 45 %
WT-2
II-2 39 %
1-100
0.005
0.02
0.008
0.27
101-1,000
0.134
0.58
1.343
7.26
1,001-10,000
0.478
5.82
1.715
42.13
>10,000
3.702
31.24
6.748
66.45
1-100
0.028
0.03
0.064
0.28
0.771
0.64
2.845
7.3
5.456
6.13
13.251
42.44
44.115
33.7
102.722
68.87
Snippets 101-1,000 (s) 1,001-10,000 >10,000
Antonio Fariña
Resultados experimentales
Indexación implícita
Búsqueda de frases de k-palabras (corpus ALL) WT-1 # words Locate (s)
Snippets (s)
Antonio Fariña
II-1 45 %
WT-2
II-2 39 %
2
1.92
5.57
4.25
22.88
4
2.02
4.98
4.09
16.50
6
1.30
2.02
3.05
10.99
8
0.94
1.25
2.63
8.47
2
5.07
5.75
11.73
23.05
4
2.10
4.99
4.23
16.50
6
1.30
2.02
3.06
11.00
8
0.95
1.25
2.63
8.46
Resultados experimentales
Indexación implícita
Búsqueda de frases de k-palabras (corpus ALL) WT-1 # words 2
II-1 45 %
1.92
WT-2
II-2 39 %
5.57
4.25
22.88
4 2.02 4.98 4.09 16.50 Locate (s) 6 1.30 2.02 3.05 10.99 • WT-* es mejor que la II-orientado a bloques cuando 8 1.25(<55%).2.63 8.47 se dispone de poco0.94 espacio extra Snippets (s)
Antonio Fariña
2
5.07
5.75
11.73
23.05
4
2.10
4.99
4.23
16.50
6
1.30
2.02
3.06
11.00
8
0.95
1.25
2.63
8.46
Resultados experimentales Conclusiones
Wavelet tree sobre códigos orientados a byte: — Le da sincronismo a códigos que no se auto-sincronizan,
manteniendo (casi): ratio y velocidad
La mejor opción es la utilización de PH
Mantiene el mejor ratio de compresión Gracias a la reorganización, se auto-sincroniza
— Se obtienen propiedades de indexación implícita
Es posible superar a un II-bloques, si queremos un índice pequeño
Puede considerarse como un nuevo autoíndice Antonio Fariña
Guión de la exposición
Motivación Índices invertidos Wavelet trees Wavelet trees sobre códigos densos WTDC Arrays de sufijos Arrays de sufijos comprimidos Otros indices y trabajo futuro Antonio Fariña
Array de sufixos
Índice ya clásico — Permite buscar cualquier patrón en tiempo logarítmico. Búsqueda binaria
Especialmente interesante para buscar frases.
— Ordena lexicográficamente los sufijos del texto
Sufijo está identificado por su posición en “T”.
T
A
=
=
Sufijo T[i..n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
c
a
v
a
_
o
_
c
a
b
o
_
n
a
_
c
o
v
a
$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
20
7
15
12
5
19
14
4
9
2
10
8
1
16
13
6
11
17
18
3 v a_ o_ ca bo _n a _c ov a$
v a$
o va $
o _n a_ c o v a $
o _c ab o_ n a_ co va $
n a_ c ov a $
c o v a$
c a v a_ o_ ca b o _na _ c ov a $
c ab o_ n a _ co va $
b o_ na _ co va$
a va _o _c ab o_ n a_ co va $
a bo _n a _c o va $
a _o _ c ab o _n a_ co va $
a _c ov a$
a$
_ o_ ca bo _ n a _c ov a$
_ na _ c ov a$
_ co va $
_ ca bo _n a _ c ov a$
$
Antonio Fariña
Array de sufixos
Índice ya tradicional
— Ordena lexicográficamente los sufijos del texto
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
c
a
v
a
_
o
_
c
a
b
o
_
n
a
_
c
o
v
a
$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
20
7
15
5
19
4
9
2
10
8
1
16
13
6
11
17
18
3 a _ o _ c a b o _ n a _ c o va $
a bo _ na _c ov a$
a va _ o _ c a b o _ n a _ c o v a $
c ab o _ n a _ c o va $
c av a_ o _ ca b o _na _ c ov a$
14 12 A =
o va $ o _n a_c ov a $ o _ c a b o _ n a _ c o va $ n a_cov a $ c ov a $
b o_ n a_ co v a $
a _c ov a$ a$ _ o_ ca b o _ na _c ov a$ _ na _c ov a$ _ co va $ _ ca b o _n a _c o v a$ $
Antonio Fariña
v a_ o _ c a b o _ n a _ c o v a $
3
v a$
2
T =
1
Array de sufixos
Busqueda binaria — Ejemplo: Búsqueda del patrón = “ca”
Como ca > ava_o_cabo_na_cova → buscamos en la mitad derecha Antonio Fariña
Array de sufixos
Búsqueda binaria — Ejemplo: Búsqueda del patrón = “ca”
T=
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
c
a
v
a
_
o
_
c
a
b
o
_
n
a
_
c
o
v
a
$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
4
9
2
10
8
1
A = 20
7
15 12
5
19 14
16 13
6
11 17 18
Como ca > ava_o_cabo_na_cova → eliminamos la mitad izquierda Repetimos el proceso hasta localizar el intervalo
Antonio Fariña
3
Array de sufixos
Búsqueda binaria — Ejemplo: Búsqueda del patrón = “ca”
T=
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
c
a
v
a
_
o
_
c
a
b
o
_
n
a
_
c
o
v
a
$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
4
9
2
10
8
1
A = 20
7
15 12
5
19 14
16 13
6
11 17 18
3
Positivo: Velocidad en las búsquedas Negativo: Ocupa mucho espacio porque necesita el array Y el texto Antonio Fariña
Guión de la exposición
Motivación Índices invertidos Wavelet trees Wavelet trees sobre códigos densos WTDC Arrays de sufijos Arrays de sufijos comprimidos Otros indices y trabajo futuro Antonio Fariña
Array de sufixos Comprimidos Mejoras sobre el array de sufijos
Distintas mejoras para construir índices basados en arrays de sufijos
Dos ideas fundamentales: — Comprimir el array de sufixos
Array de sufixos compacto de Mäkinen Array de sufixos comprimido de Grossi e Vitter
— Prescindir do texto
Autoíndice de Sadakane
Antonio Fariña
Autoíndice de Sadakane: La función Ψ
Antonio Fariña
Autoíndice de Sadakane: La función Ψ
Antonio Fariña
Autoíndice de Sadakane: La función Ψ
Antonio Fariña
Autoíndice de Sadakane: La función Ψ
Antonio Fariña
Autoíndice de Sadakane: La función Ψ
Antonio Fariña
Autoíndice de Sadakane: La función Ψ
Antonio Fariña
Autoíndice de Sadakane: La función Ψ
Antonio Fariña
Autoíndice de Sadakane: La función Ψ
Antonio Fariña
Antonio Fariña
Autoíndice de Sadakane
Antonio Fariña
Autoíndice de Sadakane
Antonio Fariña
Autoíndice de Sadakane
Antonio Fariña
Resultados experimentales orientativos!! Corpus FT91 (15MB) y FT94 (200MB) Estructuras orientadas a palabras (no a caracteres!!!) Búsqueda de frases — —
Entre 5 y 10 palabras por frase Frecuencia entre 50 y100
Tempo medio de busca Tempo medio de busca
0,1
0,1
0,09 0,08 0,07
0,09
Array de Sufixos
Autoíndice
0,06
0,08 0,07 Tempo (ms)
Tempo (ms)
0,05 0,04 0,03
0,05 0,04 0,03 0,02
0,01
0,01
0
0
Antonio Fariña
Autoíndice
0,06
0,02
Tempos para o texto FT91
Array de Sufixos
Tempos para o texto FT94
Resultados experimentais Eficiencia espacial
Espazo de almacenamento (bytes): Estructuras orientadas a palabras
Antonio Fariña
Texto
Texto
Autoíndice
F. comp
FT91
14.749.355
5.486.842
37,20%
FT92
175.449.615
55.935.301
31,88%
FT93
197.586.334
59.068.028
29,89%
FT94
203.783.923
60.719.766
29,80%
Texto
Array de sufixos
Autoíndice
F. comp
FT91
23.987.835
5.486.842
22,87%
FT92
321.530.311
55.935.301
17,40%
FT93
364.674.086
59.068.028
16,20%
FT94
375.942.627
60.719.766
16,15%
Algunhas destas transparencias pertencen a outros investigadores do LBD (http://lbd.udc.es): — Susana Ladra — Eduardo Rodríguez López
Antonio Fariña