Post on 04-Aug-2020
I t d ió l ióIntroducción a la compresión y a la autoindexación de texto
Antonio FariñaAntonio FariñaLaboratorio de Bases de Datos
Universidade da CoruñaUniversidade da CoruñaSegovia, 11 de abril de 2013
Pongámonos en situaciónCompresiónCompresión
Doc
Doc1
Doc2
Doc1 Doc2Doc i
Dónde hablan deDoc3
DocDoc3
Doc2DocN
Colección de Texto
100%
Dónde hablan de “acueductos”?
20%100%
30% Colección de Texto comprimida
p7zip, edge-2,
10010000000
Doc3Doc
Doc1
Doc3Doc2
Doc1
DocN
Doc2Doc i
Colección de Textocomprimida
p p, g ,MPPM-2
Obviamente: Se reduce el espacio de almacenamiento
No tan obvio: Se puede reducir el tiempo de búsqueda(menos datos que procesar)
Pongámonos en situaciónIndexaciónIndexación
Doc
Doc1
Doc2
Doc1 Doc2Doc i
Dónde apareceDoc3
DocDoc3
Doc2DocN
100%
Dónde aparece“acueducto”
Palabra 1
…
Colección de Texto
100%…
acueducto
…
Palabra n
Í
acueducto
30%
(> 5-30%)Índice
Doc3Doc
Doc1
Doc3Doc2
Doc1
DocN
Doc2Doc i
Colección de Textocomprimida
Además del texto (comprimido?), es necesario almacenar el índice(el índice también se puede guardar “comprimido”)
Se reduce el tiempo de búsqueda: no es necesario escaneo completo
Pongámonos en situaciónauto-indexaciónauto-indexación
Dónde aparece Doc
Doc1
Doc2
Doc1 Doc2Doc i
Dónde aparece“acueducto”
Palabra 1
…
Doc3Doc
Doc3Doc2
DocN
100%Colección de Texto
…
acueducto
…
Palabra n
Í
acueducto
0 0 0 01 1 1 Palabra 1
Autoíndice (wavelet-tree)
(> 5-30%)Índice 0 1
0 1 0 10 0 0
…
acueducto
…
Palabra n
acueducto
Autoíndice contiene implícitamente texto (es capaz de “recuperarlo”)
Permite búsquedas sublineares (eficientes): ¡es un índice!
I t d ió l ióIntroducción a la compresión y a la autoindexación de texto
parte 1 – Compresiónparte 1 Compresión(word-based byte-oriented compressors)
Guión de la exposiciónGuión de la exposición
Motivación
Estado del arte
Compresores semiestáticos de palabras
IntroducciónM ti ió G l l ióMotivación General para la compresión
P i i ??- Porque comprimir ?? Mi disco es GRANDÍSIMO y BARATO !!
T “b t ” “ ” di- Tu “barato” y “gran” disco esLENTO!!!
IntroducciónMotivación General para la compresiónMotivación General para la compresión
¡ La compresión no sólo reduce espacio !¡ La compresión no sólo reduce espacio !— Tiempo de acceso a disco (tu enorme disco es lento)— Tiempo de transmisión (las redes son incluso más lentas)— Tiempo de búsqueda (menos datos a procesar)
La compresión puede estar integrada en los Sistemas de Recuperación de Textos mejorandoSistemas de Recuperación de Textos, mejorando su rendimiento en todos los aspectos
IntroducciónImportancia de la compresión en las BDTImportancia de la compresión en las BDT
Importancia de la compresión en las Bases de Datos TextualesDatos Textuales— Reduce su tamaño: 30% de ratio de compresión— Reduce tiempo de acceso a disco y tiempo de transmisión— Es posible buscar en texto comprimido directamente— La descompresión es necesaria sólo para mostrar resultados
La compresión puede estar integrada en los Sistemas de— La compresión puede estar integrada en los Sistemas de Recuperación de Textos, mejorando su rendimiento
— …
Propiedades deseables básicas:— Búsquedas directas y descompresión aleatoriaBúsquedas directas y descompresión aleatoria
Guión de la exposiciónGuión de la exposición
Motivación
Estado del arte
• Conceptos básicos• Conceptos básicos
• Compresión Estadística semiestática
• Codificación Huffman
Compresores semiestáticos de palabrasp p
Estado del arteClasificación: alfabetos entrada / salida
• El compresor puede elegir como alfabeto de entrada• El compresor puede elegir como alfabeto de entrada– Un número fijo de símbolos (compresores estadísticos):
Ejemplo: 1 carácter, 1 palabra, Un número variable de símbolos (compresores de diccionario):– Un número variable de símbolos (compresores de diccionario):
Ejemplo: La primera vez que aparece el símbolo a se comprime “solo”; en su segunda ocurrencia se codifica con el siguiente símbolo ax
• Los códigos se crean sobre los símbolos de un alfabeto de salida:– Códigos de longitud fija (1bit, 10 bits, 1 byte, 2 bytes,…)– Códigos de longitud variable (unos de 1 bit/byte, otros de 2, etc)
• Clasificación: (fixed-to-variable, variable-to-fixed, var-to-var)
t dí ti
Alfabeto salida
fijfijo var-- estadísticosAlfabeto entrada diccionario var2var
fijovar
Estado del arte2 grandes familias2 grandes familias
Dos grandes familias de compresoresg p— Basados en diccionario (gzip, compress,… )
— Compresores estadísticos (Huffman, aritmético, PPM,… )
Compresores estadísticosCompresores estadísticos— Calculan las frecuencias de los símbolos de entrada
Asocian códigos más pequeños a los símbolos más frecuentes— Asocian códigos más pequeños a los símbolos más frecuentes
Obtenemos compresiónObtenemos compresión
Estado del arteTécnicas basadas en diccionarioTécnicas basadas en diccionario
¿Cómo comprimir?asocian códigos de longitud fija a símbolos de longitud variable— asocian códigos de longitud fija, a símbolos de longitud variable (substrings del texto)
— Cuánto más largo sea el substring substituido mejor compresión se obtiene
Representante más conocido: Familia Lempel-ZivRepresentante más conocido: Familia Lempel Ziv— LZ77 (1977): gzip, pkzip, arj …— LZ78 (1978) LZW (1984) C i á GIF LZW (1984): Compress, imágenes GIF
— …
LZWlo
ejem
p
Parte de un diccionario inicial (que contiene los símbolos de ) Dada una posición en el texto.
— Leer caracteres w=w0 w1 w2 … mientras w aparezca en el diccionario— Cuando w0 …wk wk+1 no esté en el diccionario y w0 …wk sí (NOTA l ódi d ú t d l ) output ( i = entryPos(w0 …wk)) (NOTA: long código dep núm entradas = log2 n) insertar entrada w0 …wk wk+1
Continuar a partir de wk+1 (incluido)
O diccionario tiene tamaño limitado y podría llenarse en un momento dado— Políticas: LRU, truncar diccionario y continuar, …
LZWlo
ejem
p
Parte de un diccionario inicial (que contiene los símbolos de ) Dada una posición en el texto.
— Leer caracteres w=w0 w1 w2 … mientras w aparezca en el diccionario— Cuando w0 …wk wk+1 no esté en el diccionario y w0 …wk sí (NOTA l ódi d ú t d l ) output ( i = entryPos(w0 …wk)) (NOTA: long código dep núm entradas = log2 n) insertar entrada w0 …wk wk+1
Continuar a partir de wk+1 (incluido)
O diccionario tiene tamaño limitado y podría llenarse en un momento dado— Políticas: LRU, truncar diccionario y continuar, …
Guión de la exposiciónGuión de la exposición
Motivación
Estado del arte
• Conceptos básicos• Conceptos básicos
• Compresión Estadística Semiestática
• Codificación Huffman
Compresores semiestáticos de palabrasp p
Estado del arteCompresores estadísticos semiestáticosCompresores estadísticos semiestáticos
Compresión estadística
Semiestática: 2 pasos— Calcular las frecuencias de los símbolos de entrada y
codificar (modelado y codificación)codificar (modelado y codificación)— Compresión (substitución símbolo código)
Estado del arteCompresores estadísticos semiestáticosCompresores estadísticos semiestáticos
1er paso: Procesar texto > Ordenar vocabulario > Generar códigos
vocabulario
En un lugar de 1de 2 C1
códigos
En un lugar de
la Mancha de
cuyo nombre
i
1
1
no 2
En 1
C2
C3
Cno quiero
acordarme no
…
1
1
1
2un 1
lugar 1
la 1
C4
C5
C61
1
1
la 1
Mancha 1
cuyo 1
C6
C7
C8
Texto
1
1
1
2
d 1
nombre 1
quiero 1
C
C9
C10
Símbolo = palabra 1acordarme 1 C11Símbolo = palabra
Estado del arteCompresores estadísticos semiestáticosCompresores estadísticos semiestáticos
2o paso: Substitución palabra código
vocabulario
C1de 2
código
E l d
1
C2
C3
no 2
En 1de*no*En*… cabecera
En un lugar de
la mancha de
cuyo nombreC3 C4 C5 C1
C6 C7 C8C1
C4
C5
C6
un 1
lugar 1
la 1 Datos
de no En … cabece a
no quiero
acordarme no
…
C6
C11
C7 C8
C9 C2 C10
C1
C2 …
C6
C7
C8
la 1
Mancha 1
cuyo 1
DatosCompr.
C
C9
C10
d 1
nombre 1
quiero 1Texto Fichero de salida
C11acordarme 1
Estado del arteCompresores estadísticos semiestáticosCompresores estadísticos semiestáticos
Compresión estadística
2 pasos— Calcular las frecuencias de las palabras y codificar
C ió ( b tit ió l b ódi )— Compresión (substitución palabra código)
La asociación entre símbolo de entrada código no cambia a lo largo del texto— La búsqueda directa es posible permite Text retrieval
Mét d á t ti H ff Método más representativo: Huffman.
Guión de la exposiciónGuión de la exposición
Motivación
Estado del arte
• Conceptos básicos• Conceptos básicos
• Compresión Estadística semiestática
• Codificación Huffman
Compresores semiestáticos de palabrasp p
Estado del arteCodificación de HuffmanCodificación de Huffman
Método Huffman clásico
— Código libre de prefijo óptimo (i.e., menor longitud total)
— Basado en caracteres (originalmente) Los caracteres son los símbolos a codificar
— Orientado a bits: Los códigos son secuencias de bits
— Se construye un árbol de Huffman para generar los códigos
Estado del arteCódigos libres de prefijoCódigos libres de prefijo
Códigos libres de prefijo— Un código nunca es prefijo de otro más largo.
Al l ódi d d difi i id d d— Al leer un código ya puede decodificarse sin necesidad de leer más símbolos.
Ejemplo: Compresión del texto: ABCABAC
Código decodificable Código libre de A1 A0B10
gunívocamente.No libre de prefijo
gprefijoB10
C100
B10C110
?? ?1 10 100 1 10 1 10 0 10 110 0 10 0 110Texto comprimido
A B C A B A C A B C A B A CTexto descomprimido
Estado del arteCodificación de HuffmanCodificación de Huffman
Método Huffman clásico
— Código libre de prefijo óptimo (i.e., menor longitud total)
— Basado en caracteres (originalmente) Los caracteres son los símbolos a codificar
— Orientado a bits: Los códigos son secuencias de bits
— Se construye un árbol de Huffman para generar los códigos
Estado del arteConstrucción del árbol de HuffmanConstrucción del árbol de Huffman
Ordenación de símbolos por frecuencia
Símbolos A B C D EFrecuencia / n 0.25 0.25 0.20 0.15 0.15CódigoCódigo
Estado del arteConstrucción del árbol de HuffmanConstrucción del árbol de Huffman
Construcción de abajo a arriba
0.30
ED
0.15 0.15
Símbolos A B C D EFrecuencia / n 0.25 0.25 0.20 0.15 0.15CódigoCódigo
Estado del arteConstrucción del árbol de HuffmanConstrucción del árbol de Huffman
Construcción de abajo a arriba
0.30
0.45
ED ED
CB
0.25 0.20
0.15 0.15
Símbolos A B C D EFrecuencia / n 0.25 0.25 0.20 0.15 0.15CódigoCódigo
Estado del arteConstrucción del árbol de HuffmanConstrucción del árbol de Huffman
Construcción de abajo a arriba Construcción de abajo a arriba
0.30
0.450.55
ED ED
CB
0.25 0.20
A
ED
CB
0.25
0.15 0.15
Símbolos A B C D EFrecuencia / n 0.25 0.25 0.20 0.15 0.15CódigoCódigo
Estado del arteConstrucción del árbol de HuffmanConstrucción del árbol de Huffman
Construcción de abajo a arriba Construcción de abajo a arriba1.00
0 30
0.450.55
0.30
0.25 0.200.25
A
ED
CB
0.15 0.15
0.200 5ED
Símbolos A B C D EFrecuencia / n 0.25 0.25 0.20 0.15 0.15CódiCódigo
Estado del arteConstrucción del árbol de HuffmanConstrucción del árbol de Huffman
Etiquetar ramasq1.00
0 30
0.450.550 1
ED
0.30
ED
CB
0.25 0.20
A
ED
CB
0.25
A
ED
CB
ED
0.15 0.15
ED ED ED
Símbolos A B C D EFrecuencia / n 0.25 0.25 0.20 0.15 0.15Código
Estado del arteConstrucción del árbol de HuffmanConstrucción del árbol de Huffman
Etiquetar ramas
0 1
1.00
0 1
10
10
0.30
0.450.55
A1
E
0
D
CB
0.25 0.200.25
0.15 0.15
Símbolos A B C D EFrecuencia / n 0.25 0.25 0.20 0.15 0.15CódiCódigo
Estado del arteConstrucción del árbol de HuffmanConstrucción del árbol de Huffman
Asignación de códigos1.00
g g
0 1
10
10
0.30
0.450.55
1
E
0
D
CB
0 30
0.25 0.200.25
A
0.15 0.15
Símbolos A B C D EFrecuencia / n 0.25 0.25 0.20 0.15 0.15Códi 001000111001Código 001000111001
Estado del arteConstrucción del árbol de HuffmanConstrucción del árbol de Huffman Asignación de códigos
1.00
0 1
10
10
0 30
0.55 0.45
1
A1
E
0
D
1
CB
0.30
0.25 0.25 0.20
Símbolos A B C D E
ED
0.150.15
Siempre hay combinaciones de bits que no se usanSímbolos A B C D E
Frecuencia / n 0.25 0.25 0.20 0.15 0.15
Código 01 10 11 000 001
Siempre hay combinaciones de bits que no se usan Asegurar libre de prefijo: ej: “00”, “0”, “1”
Ej.: codificando ADB
Código 01 10 11 000 001
01 000 10
Estado del arteCodificación de HuffmanCodificación de Huffman
Código libre de prefijo óptimo
Basado en caracteres (originalmente) Basado en caracteres (originalmente)— Los caracteres son los símbolos a codificar
O i t d bit L ódi i d bit Orientado a bits: Los códigos son secuencias de bits
Se construye un árbol de Huffman para generar los códigos
El árbol de Huffman tenía que ser almacenado con el texto comprimido (cabecera)p ( )
Ratio de compresión sobre el 60% (pobre poco utilizado BDT)
Guión de la exposiciónGuión de la exposición
Motivación
Estado del arte anterior
Compresores semiestáticos de palabras Compresores semiestáticos de palabras• Compresión orientada a palabras• Plain y Tagged Huffman• Plain y Tagged Huffman• End Tagged Dense Code• (s,c)- Dense Code• Resultados Empíricos
Compresores semistáticos de palabrasOrientación a palabras ¿por qué?Orientación a palabras ¿por qué?
Lenguaje natural: Ley de Zipf y Ley de Heaps
HeapsZipfZipf
Heaps:: el tamaño del vocabulario tiene poca importancia si tenemos textos grandes Zipf:: La distribución de frecuencias de las palabras de un texto es muy sesgada
Compresores semistáticos de palabrasHuffman orientado a palabrasHuffman orientado a palabras
Uso de orientación a palabras: Bentley (et al 1986) Moffat [’89] propuso usar palabras en vez de caracteres (+huffman) La distribución de frecuencias de las palabras es más sesgada
16
18 c
6
8
10
12
14
16
frec
Word freq distributionCharacter freq distribution (Spanish)
0
2
4
E A O L S N D R U I T C P M Y Q B H G F V J Ñ Z X K W n
Se consiguen ratios de compresión de hasta 25% (en inglés)
Así los elementos básicos para compresión y Text Retrievalson los mismos: las palabras
Compresores semistáticos de palabrasCompresión + indexaciónCompresión + indexación
Ejemplo:El que poco coco come poco coco compra Texto original:
poco
Vocabulario Esquema codificación
10Í C1pocococo
El
10110010
pocococo
El
5
16
2328
Índice invertido orientado a palabras:
1028
C1C2C3
quecome
00110110
Elque
comecompra
13711
C4C5
compra 0111 C6
Texto comprimido: 0010 0011 10 11 0110 10 11 0111 1 2 3 4 5 6 7 8 9 10 11 12
Guión de la exposiciónGuión de la exposición
Motivación
Estado del arte anterior
Compresores semiestáticos de palabras Compresores semiestáticos de palabras• Compresión orientada a palabras• Plain y Tagged Huffman• Plain y Tagged Huffman• End Tagged Dense Code• (s,c)- Dense Code• Resultados Empíricos
Compresores semistáticos de palabrasPlain Huffman & Tagged HuffmanPlain Huffman & Tagged Huffman
1998: Moura, Navarro, Ziviani y Baeza: — 2 nuevas técnicas: Plain Huffman y Tagged Huffman
Elementos comunes:— Basados en Huffman— Orientado a palabras— Usan bytes (no bits) (compresión ±30% pero más velocidad)
Plain Huffman = Huffman sobre bytes (árbol 256-ario) Tagged Huffman marca el inicio de cada código
El primer bit es: •“1” para el 1er bit del 1er byte“0” l 1er bit d l b t t tEl primer bit es: •“0” para el 1er bit de los bytes restantes
1xxxxxxx 0xxxxxxx 0xxxxxxx
Compresores semistáticos de palabrasPlain Huffman & Tagged HuffmanPlain Huffman & Tagged Huffman
Ejemplo (b=2): to be lucky or not
01or
00be
PLAIN HUFFMAN
11 00
10be
TAGGED HUFFMAN
11 00lucky
10not
01or
11 01 01 00lucky
11 01 00not
11 00or
Busquemos “lucky”
11 11to 11 01 01 01to
permite búsquedas eficientesto be lucky or not
1111 00 1100 01 10Falso emparejamiento
to be lucky or not
11010101 10 11010100 1100 110100I ibl j i t f l
permite búsquedas eficientes
Búsqueda directa (comprimir el patrón y buscarlo)Bú d ti B M ibl ( lt d b t )
Búsquedas mejoradas
Falso emparejamiento Imposible emparejamientos falsos
Búsqueda tipo Boyer-Moore es posible (saltando bytes) Acceso aleatorio:
Empezar la búsqueda (y la descompresión) desde cualquier lugar
Compresores semistáticos de palabras Plain Huffman & Tagged HuffmanPlain Huffman & Tagged Huffman
Ejemplo (b=2): to be lucky or not
01or
00be
PLAIN HUFFMAN
11 00
10be
TAGGED HUFFMAN
11 00lucky
10not
01or
11 01 01 00lucky
11 01 00not
11 00or
Plain Huffman : ratio de compresión de 30-32%
Busquemos “lucky”
11 11to 11 01 01 01to
Tagged Huffman: ratio de compresión de 33.5-35% permite búsquedas + eficientes
to be lucky or not 1111 00 1100 01 10
Falso emparejamiento
to be lucky or not
11010101 10 11010100 1100 110100I ibl j i t f l
permite búsquedas + eficientes
Búsqueda directa (comprimir el patrón y buscarlo)Bú d ti B M ibl ( lt d b t )
Búsquedas mejoradas
Falso emparejamiento Imposible emparejamientos falsos
Búsqueda tipo Boyer-Moore es posible (saltando bytes) Acceso aleatorio:
Empezar la búsqueda (y la descompresión) desde cualquier lugar
Guión de la exposiciónGuión de la exposición
Motivación
Estado del arte anterior
Compresores semiestáticos de palabras Compresores semiestáticos de palabras• Compresión orientada a palabras• Plain y Tagged Huffman• Plain y Tagged Huffman• End Tagged Dense Code• (s,c)- Dense Code• Resultados Empíricos
Compresores semistáticos de palabras End-Tagged Dense Code
Pequeño cambio: Una marca señala el final de un código1
Primer bit es:“1” --> para el 1er bit del último byte“0” --> para el 1er bit del resto de bytes
1xxxxxxx
0xxxxxxx
Código libre de prefijo independ. de restantes 7 bits del byte
Ya no se necesita usar HuffmanEs posible usar TODAS las combinaciones de bits: Código Denso
Tiene bit de Flag igual que Tagged Huffman en búsquedas
Compresores semistáticos de palabras End-Tagged Dense Code
Pequeño cambio: Una marca señala el final de un código1
Códigos de 1 byte 1xxxxxxx
Primer bit es:“1” --> para el 1er bit del último byte“0” --> para el 1er bit del resto de bytes
1xxxxxxx
0xxxxxxxCódigos de 2 bytes 1xxxxxxx0xxxxxxx
Código libre de prefijo independ. de restantes 7 bits del byteCódigos de 3 bytes 1xxxxxxx0xxxxxxx0xxxxxxx
Ya no se necesita usar HuffmanEs posible usar TODAS las combinaciones de bits: Código Denso
Tiene bit de Flag igual que Tagged Huffman en búsquedas
Compresores semistáticos de palabrasEnd Tagged Dense CodeEnd-Tagged Dense Code
Esquema de codificación
128 l b á f t10000000
00000000:10000000
128 palabras más frecuentes
(128 = 27 códigos de 1 byte)
10000001…..11111111
1282 palabras de 128+1 a 128+1282
(1282 = 214 códigos de 2 bytes)
00000000:10000000…..01111111:11111111
1283 Las palabras 128+ 1282+1 a 128 +1282 +1283 usan tres bytes
3 21
00000000:00000000:10000000……01111111:01111111:11111111
.....
(1283 = 221 códigos)
Los códigos dependen de la posición de la palabra en el ránking no de su frecuencia
Compresores semistáticos de palabras E d T d D C dEnd-Tagged Dense Code
Procedimiento de codificación secuencial— Ordenación de palabras por frecuencia— Asignación de códigosAsignación de códigos ...0xxxxxxx
< 2b-10xxxxxxx
< 2b-11xxxxxxx
≥ 2b-1
Procedimiento de codificación directa (“al vuelo”)
C codificar(i)Ci codificar(i)i decodificar(Ci)
Compresores semistáticos de palabras E d T d D C dEnd-Tagged Dense Code
Procedimiento de codificación secuencial— Ordenación de palabras por frecuencia— Asignación de códigosAsignación de códigos ...0xxxxxxx
< 2b-10xxxxxxx
< 2b-11xxxxxxx
≥ 2b-1
Procedimiento de codificación directa (“al vuelo”)
C codificar(i)Pon las formulas y las complejidadesO(|x|) = O(log i)
Ci codificar(i)i decodificar(Ci)
O(log i)
Compresores semistáticos de palabras End-Tagged Dense CodeEnd-Tagged Dense Code
Descompresión: dos pasos— Cargar el vocabulario ordenado
i decodificar(C ) :: O(bytes T Comp)— i decodificar(Ci) :: O(bytes T.Comp)
vocabulario
C2 C3 C4 C0
de*no*En*… cabecera de
no
En
0
1En un lugar de
la mancha deC5
C10
C6 C7
C8 C1 C9
C0
C
Datoscompr.
En
un
lugar
2
3
4
cuyo nombre
no quiero
aco da me no
decode
C1 …
Fichero comprimidola
4
5
Texto plano
acordarme no
……
Texto plano
Compresores semistáticos de palabras End Tagged Dense Code: búsquedas TCEnd-Tagged Dense Code: búsquedas TC
Búsquedas directas:
1) Obtener el código asociado al patrón P Cp1) Obtener el código asociado al patrón P Cp2) Buscar el código Cp dentro del texto comprimido usando
un algoritmo de tipo Boyer Moore (skipping bytes)un algoritmo de tipo Boyer-Moore (skipping bytes)
3) Tras un emparejamiento chequear si es una ocurrencia real del patrónreal del patrón
Es una ocurrencia o el sufijo de un código más largo? Byte previo ≥ 128 ?
— Ej. Búsqueda de: “Pedrito” C(“Pedrito”) = 25 234
39 25 234 234100 129 25 234110 25 2342 2 251
False match True match
Compresores semistáticos de palabras E d T d D C dEnd-Tagged Dense Code
Es un código denso. Pueden utilizarse todos los códigos disponibles.disponibles.— Comprime mejor que TH (2-3 puntos).— Es superado por PH (≤1 punto).
Marca mismas capacidades de búsqueda de Tagged Huffman— Búsqueda directa,
A l t i— Acceso aleatorio.
Codificación y decodificación eficienteProcedimientos secuencial y directo— Procedimientos secuencial y directo
Fácil de programarp g
Guión de la exposiciónGuión de la exposición
Motivación
Estado del arte anterior
Compresores semiestáticos de palabras Compresores semiestáticos de palabras• Compresión orientada a palabras• Plain y Tagged Huffman• Plain y Tagged Huffman• End Tagged Dense Code• (s,c)- Dense Code• Resultados Empíricos
Compresores semistáticos de palabras (s c)-Dense Code(s,c)-Dense Code
End Tagged Dense Code — 128 valores disponibles [128, 255] para el último byte (stoppers)— 128 valores disponibles [0, 127] para los restantes bytes (continuers)
Por qué usar valores fijos de s y c?
Adaptar (s,c) al vocabulario s minimizando tamaño Texto Comp.Número de palabras— Número de palabras
— Distribución de frecuencia de las palabras
End-Tagged Dense Code es un (128,128)-Dense Code
Compresores semistáticos de palabras (s c)-Dense Code(s,c) Dense Code
Esquema de codificación
http://vios.dc.fi.udc.es/codes
— Stoppers: último byte. s valores entre [0,s-1]— Continuers: otros bytes c valores entre [s 255]
q
Continuers: otros bytes. c valores entre [s, 255]
0... s palabras más frecuentes...s-1
s palabras más frecuentes
s 0l b d 1
s+1...255
1...s 1
sc palabras de s+1 a s+sc
255 s-1s...255
s...255
sc2 palabras de s+sc+1 a s+sc+sc20...S 1255 255 S-1
Compresores semistáticos de palabras (s c) Dense Code(s,c)-Dense Code
Ejemplo (b=3) Ejemplo (b=3)
0 200 200 200 20[000]0 20A
ETDC(5,3)(6,2)PH(4,4)- DC (ETDC)(5,3)-DC(6,2)-DCP.H.FreqPalabra
[000] [000] [000]
0,150,150,150,15[011]0,15D
0,150,150,150,15[010]0,15C
0,200,200,200,20[001]0,20B
0,200,200,200,20[000]0,20A
[011]
[010]
[001]
[000]
[011]
[010]
[001]
[000]
[011]
[010]
[001]
[000]
0,180,180,090,09[101]0,09F
0,280,140,140,14[100]0,14E
0,150,150,150,15[011]0,15D
[101]
[100]
[011]
[101][000]
[100]
[011]
[100][001]
[100][000]
[011]
0,010,010,010,01[111][001]0,005I
0,040,040,040,04[111][000]0,02H
0,080,080,080,04[110]0,04G
[110][010]
[110][001]
[110][000]
[101][011]
[101][010]
[101][001]
[101][000]
[100][011]
[100][010]
1,301,161,071,03Longitud media del código
0,010,010,010,01[111][010]0,005J [110][011] [101][100] [101][001]
End-Tagged Dense Code es un (2b-1,2b-1)-DC
Compresores semistáticos de palabras (s,c)-Dense Code
Codificación Secuencial...xxxxxxxx xxxxxxxx zzzzzzzz
Codificación directa
s≤ vc < 2b-1 0≤ vs< ss≤ vc< 2b-1
Codificación directa
C difi ( i)Ci codifica(s, i)i decodifica(s, Ci) Pon las formulas
O(log i)
O(|x|) = O(log i)
Compresores semistáticos de palabras ( ) D C d(s,c)-Dense Code
Es un código densoC i j TH (3 4 t )— Comprime mejor que TH (3-4 puntos)
— Comprime mejor que ETDC (0.5 puntos)
— Es superado por PH (0.25 puntos)
— RATIO: PH < SCDC << ETDC <<< TH
C difi ió d difi ió i l Codificación y decodificación simple
Marca? (byte valor < s)Marca? (byte valor < s)— Mismas capacidades de búsqueda que ETDC y Tagged Huffman
S óptimo entre 180 y 190
Guión de la exposiciónGuión de la exposición
Motivación
Estado del arte anterior
Compresores semiestáticos de palabras Compresores semiestáticos de palabras• Compresión orientada a palabras• Plain y Tagged Huffman• Plain y Tagged Huffman• End Tagged Dense Code• (s,c)- Dense Code• Resultados Empíricos
Compresores semistáticos de palabras Resultados empíricos y Plataforma de pruebaResultados empíricos y Plataforma de prueba
Textos del TREC-2 y TREC-4Textos del TREC-2 y TREC-4
Mostrando resultados para:CORPUS Tamaño (bytes) Nº palabras Nº palabras diferentes
CALGARY 2,131,045 528,611 30,995— Ratio de compresión— Tiempo de codificación y compresión— Tiempo de descompresión
FT91 14,749,355 3,135,383 75,681
CR 51,085,545 10,230,907 117,713
FT92 175,449,235 36,803,204 284,892— Velocidad de búsqueda
, , , , ,
ZIFF 185,220,215 40,866,492 237,622
FT93 197,586,294 42,063,804 291,427
FT94 203 783 923 43 335 126 295 018FT94 203,783,923 43,335,126 295,018
AP 250,714,271 53,349,620 269,141
ALL FT 591,568,807 124,971,944 577,352
ALL 1 080 719 883 229 596 845 886 190ALL 1,080,719,883 229,596,845 886,190
— Intel Pentium-III (x2) 800 MhzD bi GNU/Li (k l 2 2 19)— Debian GNU/Linux (kernel 2.2.19)
— gcc 3.3.3 20040429 y optimización –O9— Tiempo muestra CPU user-time
Compresores semistáticos de palabrasTiempos de codificación y compresiónp y p
a
osión
pasa
da
ETD
C
cons
árb
ol est alturas
ón d
e có
digo
ompr
esi
1ap
Gen
erac
ióco
asad
a2a
p
Compresores semistáticos de palabras Resultados Empíricos
34
35
Ratio de compresión (%)
260
280
Tiempo de codificación (msg.)
30
31
32
33
ompr
essi
on ra
tio (%
)
160
180
200
220
240
Enc
odin
g tim
e (m
sec.
)
PH (s ,c )-DC ETDC TH
28
29
30co
technique(s,c)-DC ETDC TH
30.73 30.88 31.56 34.16PH
<( ) DC ETDC TH<<PH
P H (s ,c )-DC E TDC TH
100
120
140
E
technique
260 143 104 270PH (s,c)-DC ETDC TH
0.8 pp 2.5 pp<(s,c)-DC ETDC TH<<
0.2 ppPH
Velocidad de compresión (Mb/sg.)6.2
25% 45% 2%< < <ETDC (s,c)-DC PH TH
Velocidad de descompresión (Mb/sg.)25
5 7
5.8
5.9
6
6.1
peed
(Mby
tes/
sec)
23
23.5
24
24.5
peed
(Mby
tes/
sec)
5.3
5.4
5.5
5.6
5.7
Com
pres
sion
sp
5.92 5.88 5.90 5.8320.5
21
21.5
22
22.5
Deo
mpr
essi
on s
23.86 23.55 24.15 22.51
>ETDC (s,c)-DC TH>=PH
PH (s ,c )-DC ETDC THtechnique(s,c)-DC ETDC THPH
1,5% 4%= > >ETDC PH (s,c)-DC TH
PH (s ,c )-DC ETDC THtechnique
(s,c)-DC ETDCPH TH
Compresores semistáticos de palabrasBúsquedas de patrones simplesq p p
2.3
2.4
2.5
Tiempo de búsqueda (sg.)
1.9
2
2.1
2.2
earc
h tim
e (s
ec.)
PH (s c)-DC ETDC TH
1.6
1.7
1.8
Se
2.30 1.70 1.80 2.00PH (s c) DC ETDC THPH (s,c) DC ETDC TH
techniquePH (s,c)-DC ETDC TH
5% 5-10% 10%< < <(s,c)-DC ETDC TH PH
Buscando patrones:- Formados por 1 única palabraFormados por 1 única palabra- Cuyos códigos tienen la misma longitud
Compresores semistáticos de palabrasBúsquedas multipatrón (100pats.)q p ( p )
Multi-pattern searches
14.602
10.667 10.49121416
c.)
9.143
68
10
earc
h tim
e (s
ec
1.987 2.497 2.283
024
se
TH ETDC SCDC DETDC+DEC DETDC AGREPrev Set-HoorspolTH ETDC SCDC DETDC+DEC DETDC AGREP rev Set-Hoorspol
Algorithm used
TH SCDC ETDC Plain text15-20% 5% 400%
Multipatrón < < <
Compresores semistáticos de palabrasResultados Empíricos : ResumenResultados Empíricos : Resumen
34
35
n ra
tio
Plain HuffmanTagged Huffman(s,c)-Dense CodeEnd Tagged Dense Code
31
32
33
com
pres
sion End-Tagged Dense Code
100 120 140 160 180 200 220 240 260 28030
encoding time (msec)
35
33
34
35
sion
ratio Plain Huffman
Tagged Huffman(s,c)-Dense CodeEnd-Tagged Dense Code
30
31
32
com
pres
End-Tagged Dense Code
18 18.2 18.4 18.6 18.8 19 19.2 19.4 19.6 19.8 2030
search time (sec)
Compresores semistáticos de palabrasResultados Empíricos : ResumenResultados Empíricos : Resumen
Antonio Fariña
Compresores semistáticos de palabrasResultados Empíricos : ResumenResultados Empíricos : Resumen
Los compresores “densos” semiestáticos: ETDC y SCDC Codificación más simple y rápida que los basados en Huffman.
— Codificación secuencial— Codificación directa (“al vuelo”)
Permiten búsqueda directa y acceso aleatorio
Velocidad: Buena velocidad de compresión y descompresión
Ratio de compresión próximo a Plain Huffman
Superan a Tagged Huffman en:Superan a Tagged Huffman en:— Ratio de compresión, — Velocidad de compresión y de descompresión
Velocidad de búsquedas (en general)— Velocidad de búsquedas (en general).
I t d ió l ióIntroducción a la compresión y a la autoindexación de texto
parte 2 – autoindexaciónparte 2 autoindexación(wavelet trees)
Guión de la exposiciónGuión de la exposición
Motivación
Í
Wavelet trees
Índices invertidos
Wavelet trees
Wavelet trees sobre códigos densos WTDC
MotivaciónMotivació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:p Técnicas de compresión
Dos hechos cambian el panorama— Dos hechos cambian el panorama Aparición de los compresores orientados a palabra Aparición de índices comprimidos y autoíndices
ya los conocemos!!
p p y
MotivaciónEstructuras de indexación: autoíndicesEstructuras de indexación: autoíndices
Índice tradicional Índice tradicional
COUNT & LOCATE Índice invertido, Array de sufijos, …
Autoíndice
C ti t ió i lí it i id d l t t
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 de Sadakane FM Index SSA SLP Array de sufijos comprimido de Sadakane, FM-Index, SSA, SLP, … … (http://pizzachili.dcc.uchile.cl/indexes)
Guión de la exposiciónGuión de la exposición
Motivación
Í
Wavelet trees
Índices invertidos
Wavelet trees
Wavelet trees sobre códigos densos WTDC
Índices invertidosEstructuraEstructura
SPIREworkshop
t i
0 103
58 159 399277147
Vocabulario Listas ocurr.
SPIREworkshop
121
Vocabulario Listas ocurr.
stringretrieval
processinginformation
Europe
58 159 39992 31365 166 40680 302
476
stringretrieval
processinginformation
Europe
1 21 21 21 22
Bú d
Europeeven
476486
Texto indexado
Europeeven
22
Búsquedas
Palabra recuperar la lista de ocurrenciasFrase intersección de listas de ocurr.
SPIRE 2012 is the 19th Annual Edition of the Symposium on string processing and informationretrieval. SPIRE has its origins in the South American workshop on string processing which was first held in Belo Horizonte (Brazil, 1993).
Doc
1
Tradeoff espacio/tiempo
Granularidad:
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
Doc
2
- Información posicional completa- Direccionamiento Documento/Bloque
years.
Índices invertidosEstructura
V b l i Li t
Estructura
SPIREworkshop
string
0 103
58 159 399277147
Vocabulario Listas ocurr.
gretrieval
processinginformation
Europe
92 31365 166 40680 302
476486even 486
Texto indexado
Compresión
- Texto indexado (+- 30% ratio)
SPIRE 2012 is the 19th Annual Edition of the Symposium on string processing and informationretrieval. SPIRE has its origins in the South American workshop on string processing which was first held in Belo Horizonte (Brazil, 1993).
Doc
1
·Huffman, ETDC, SCDC…
- Listas de ocurrencias!!
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
Doc
2
years.
Índices invertidosCompresión de listas de ocurrencias
— Se basa en 2 factores principales
Compresión de listas de ocurrencias
Se basa en 2 factores principales Las listas continen valores en orden creciente Las diferencias son menores en las listas más largas
Almacenemos diferencias en lugar de valores absolutos C i á l ódi d l it d i bl Comprimámoslas con códigos de longitud variable
4 10 15 25 29 40 46 54 57 70 79 82Original Posting list
1 2 3 4 5 6 7 8 9 10 11 121 2 3 4 5 6 7 8 9 10 11 12
4 6 5 10 4 11 6 8 3 13 9 3Diffs
c4 c6 c5 c10 c4 c11 c6 c8 c3 c13 c9 c3Codif long. variableDescompresióncompleta
57 A di t4
c6 c5 c10
29
c11 c6 c8
57
c13 c9 c3
Sampling absoluto + codif long. variable
Acceso directo
Descompresiónparcial
Índices invertidosAlgoritmos de intersección de listas
Intersección de 2 listas N y M
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 intersecarRecorrer 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 Recorrer lista más corta y buscar sus elementos en la más larga Diferentes formas de buscar:
Búsqueda secuencial Búsqueda secuencial Búsqueda binaria Búsqueda exponencial
Requiere acceso directo a la lista más larga
— Otras…
Guión de la exposiciónGuión de la exposición
Motivación
Í
Wavelet trees
Índices invertidos
Wavelet trees
Wavelet trees sobre códigos densos WTDC
Wavelet TreeConceptos básicosConceptos básicos
CONSTRUCCIÓN
Wavelet tree:distribuye los bits que forman el código de cada símbolo en los distintos niveles del árboldistintos niveles del árbol
TEXTO WAVELET TREEA B A C D A C00 01 00 10 11 00 A B A C D A C10
SÍMBOLO CÓDIGO0001B
A
A B A C D A C0 0 0 01 1
0 11
CD
1011
A B A A C D C0 1 0 10 0 0
Wavelet TreeConceptos básicosConceptos básicos
BÚSQUEDA
¿Dónde aparece la 1ª ‘D’?
TEXTO WAVELET TREEA B A C D A CA B A C D A C ¿dónde está
SÍMBOLO CÓDIGO0001B
A
A B A C D A C0 0 0 01 1
0 1
el 2º ‘1’? en la 5ª pos.
1
CD
1011
A B A A C D C0 1 0 10 0 0 ¿dónde está
el 1er ‘1’? l 2ª
es el segundo bit del nodo1
en la 2ª pos.
Wavelet TreeConceptos básicosConceptos básicos
RECUPERACIÓN DE TEXTO
¿Cuál es el siguiente símbolo?¿Qué símbolo aparece en la 6ª posición?
TEXTO WAVELET TREEA B A C D A CA B A C D A C
¿Cuántos ‘0’s hay hasta la posición 6?
SÍMBOLO CÓDIGO0001B
A
A B A C D A C0 0 0 01 1
0 1
posición 6?es el 4º ‘0’1
CD
1011
A B A A C D C0 1 0 10 0 0
¿Qué bit está en cuarto lugar del nodo0?
Hay un 0Hay un 0El código leído es 00
Wavelet TreeConceptos básicosConceptos básicos
RECUPERACIÓN DE TEXTO
¿Cuál es el siguiente símbolo?¿Qué símbolo aparece en la 7ª posición?
TEXTO WAVELET TREEA B A C D A CA B A C D A C
¿Cuántos ‘1’s hay hasta la posición 7?
SÍMBOLO CÓDIGO0001B
A
A B A C D A C0 0 0 01 1
0 1
posición 7?es el 3er ‘1’1
Para buscar:
CD
1011
A B A A C D C0 1 0 10 0 0Para recuperar el texto:
¿Qué bit está en 3er lugar del nodo1?
Hay un 0Hay un 0El código leído es 10
Wavelet TreeConceptos básicosConceptos 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
Wavelet TreeConceptos básicosConceptos básicos
RANK
B = 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 01 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 211 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 i i 1 i (i l id )posiciones 1 e i (incluidas)
Wavelet TreeConceptos básicosConceptos básicos
RANK
B = 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 01 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 211 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?rank0(16) 10
rankb(i) = número de veces que aparece el bit b entre las i i 1 i (i l id )
¿Cuántos 0 s hay hasta la posición 16?
posiciones 1 e i (incluidas)
Wavelet TreeConceptos básicosConceptos básicos
SELECT
B = 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 01 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 211 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
Wavelet TreeConceptos básicosConceptos básicos
SELECT
0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 01 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 211 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’?select0(9)
selectb(j) = posición de la j-ésima aparición del bit b
¿dó de está e 9 0
Wavelet TreeConceptos básicosConceptos básicos
BÚSQUEDA
¿Dónde aparece la 1ª ‘D’?
TEXTO WAVELET TREEA B A C D A CA B A C D A C ¿dónde está
SÍMBOLO CÓDIGO0001B
A
A B A C D A C0 0 0 01 1
0 1
el 2º ‘1’? en la 5ª pos.
1 select1(2)=5
¿dónde estáel 1º ‘1’? en la 2ª pos
CD
1011
A B A A C D C0 1 0 10 0 0 select1(1)=2
en la 2ª pos.
es el segundo bit del nodo1Para buscar: select
Para recuperar el texto: rank
Guión de la exposiciónGuión de la exposición
Motivación
Í
Wavelet trees
Índices invertidos
Wavelet trees
Wavelet trees sobre códigos densos WTDC
Wavelet tree sobre Dense Code(WTDC)(WTDC)
Características básicas del Wavelet Tree sobre Dense Code (WTDC)
Estrategia de wavelet tree— Estrategia de wavelet tree Estructura en árbol que permite indexar caracteres
B d l b— 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
(También se puede usar otro bytecode: De hecho, PH es preferible)( p y , p )
WTDCE d T d D C d (ETDC)End-Tagged Dense Code (ETDC)
End-Tagged Dense Code (ETDC)
— Basado en palabras y orientado a bytes: A i d l b ódi i d b t
Ya lo conocemos!!
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:más frecuentes: Palabras muy frecuentes 1 byte Palabras de frecuencia media 2 bytes Palabras muy poco frecuentes 3 bytesPalabras muy poco frecuentes 3 bytes
— Utiliza un bit de marca (en el último byte del código)
— Comprime el texto aproximadamente en un 30-35%
WTDCCreación del autoíndiceCreació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 árboldistintos niveles del árbol
XTO WAVELET TREA F C B B C D A E
10 0111 A F C B B C D A E0010 11 11 0010 001110 0110
TEXTO WAVELET TREE
SÍMBOLO CÓDIGO1011B
A
A F C B B C D A E10 01 00 0011 11 00 10 01
00 01 10 11CD
00 1000 11 C C D F E
10 10 1011 11E 01 10F 01 11F 01 11
WTDCUso del autoíndiceUso del autoíndice
BÚSQUEDA
¿Dónde aparece la 1ª ‘D’?¿dónde estáel 3er ‘00’?
A F C B B C D A EXTO WAVELET TREA F C B B C D A E
en la 7ª pos.TEXTO WAVELET TREE
A F C B B C D A E
SÍMBOLO CÓDIGO1011B
A10 01 00 0011 11
00 01
00 10 01
F EC C DCD
00 1000 11 10 10 1011 11
E 01 10F 01 11
¿dónde está el 1º ‘11’? en la 3ª pos.¿dónde está el 1º ‘11’? en la 3ª pos.
es el 3er byte del nodo00
F 01 11
WTDCUso del autoíndiceUso del autoíndice
RECUPERACIÓN DEL TEXTO
¿Cuál es el siguiente símbolo?¿Qué símbolo aparece en la 8ª posición?
A F C B B C D A E
XTO WAVELET TREA F C B B C D A E TEXTO WAVELET TREE
A F C B B C D A ESÍMBOLO CÓDIGO
1011B
A10 01 00 0011 11
00 01
00 10 01
El código leído es 10
C C D F ECD
00 1000 11
10 10 1011 11E 01 10F 01 11F 01 11
WTDCUso del autoíndiceUso del autoíndice
RECUPERACIÓN DEL TEXTO
¿Cuál es el siguiente símbolo?¿Qué símbolo aparece en la 9ª posición?
¿Cuántos ‘01’s hay hasta la posición 9?
A F C B B C D A E
XTO WAVELET TREA F C B B C D A E
es el 2º ‘01’TEXTO WAVELET TREE
A F C B B C D A ESÍMBOLO CÓDIGO
1011B
A10 01 00 0011 11
00 01
00 10 01
C C D F ECD
00 1000 11
10 10 1011 11E 01 10F 01 11
¿Qué byte está en 2º lugar del nodo01?
Hay un 10
F 01 11
Para buscar:Hay un 10
El código leído es 01 10Para recuperar el texto:
Wavelet tree sobre Dense Code(WTDC)(WTDC)
Propiedades claves del WTDC— Árbol no balanceado
— Árbol no binario, un hijo por cada tipo de byte
— Altura máxima: 3 niveles (4 a lo sumo)
— Ocupa un 30% del tamaño del texto original y además está indexadoestá indexado
— Reto principal: operaciones de rank y select sobreReto principal: operaciones de rank y select sobre secuencias de bytes
Wavelet tree sobre Dense Code(WTDC)(WTDC)
Propiedades claves del WTDC— Árbol no balanceado
— Árbol no binario, un hijo por cada tipo de byte
— Altura máxima: 3 nivelesDescompresión: rank
— Ocupa un 30% del tamaño del texto original y además está indexado
Búsquedas: selectestá indexado
— Reto principal: operaciones de rank y select sobreReto principal: operaciones de rank y select sobre secuencias de bytes
Implementación eficiente de rank yImplementació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
255 3 61 66 3 25 66 33 34 66 27 3 2223 61
rank66(10) = 2
2 3 4 5 6 7 8 9 10 11 12 13 141 15
select3(4)=13
Rank y select sobre bits se puede realizar en O(1)
66( ) 3( )
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 - tiempobits, pero no obtienen un buen balance espacio tiempo
rank y select sobre secuencias de bytesrank y select sobre secuencias de bytesNueva aproximación
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 bloquesbloques— Cada bloque almacena 256 contadores, uno por cada valor de byte— contador[b] guarda el nº de veces que aparece b antes del inicio delcontador[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)
- Se consigue complejidad sublineal y es parametrizable
rank y select sobre secuencias de bytesNueva aproximaciónNueva aproximación
¿ rank12 (17) ? = 4
Es parametrizable: Trade-off espacio/tiempo
Wavelet-trees y códigos orientados a byteSincronismo un valor añadidoSincronismo, 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 Podemos utilizar otros byte-codes, no sólo ETDC— Plain Huffman o RPBC (Moffat & Culpepper, Spire 2005)
Mejor compresión (+ 1%) Mejor compresión (+- 1%) Mismas propiedades
Resultados experimentalesResultados experimentalesMarco 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 4 GB DDR 400Mhz RAM— Intel Pentium IV 3.00 GHz, 4 GB 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.
Resultados experimentalesResultados experimentalesParámetros a medir
Si consideramos el WTDC como un compresor, los parámetros más importantes que se deben medir:
Tiempo de compresión — Memoria usada para— Tiempo de compresión— Tiempo de descompresión— Ratio de compresión
Memoria usada para comprimir
Considerando el WTDC como un índice, se debe medir:— Tiempo de búsqueda de: — Tiempo de cargaTiempo de búsqueda de: Count Locate Display
Tiempo de carga— Memoria usada para buscar
Display
Resultados experimentalesResultados experimentalesWTDC como compresor
Ratio de compresión48
WTDC
44
46
%)
WTDCETDCgzip
38
40
42
com
pres
ión
(
34
36
38
Rat
io d
e c
CALG FT91 CR FT92 ZIFF FT93 FT94 AP FTALL ALL30
32
CALG FT91 CR FT92 ZIFF FT93 FT94 AP FTALL ALL
Corpus utilizado
Resultados experimentalesResultados experimentalesWTDC como compresor
Ratio de compresión Differencias mínimas(+- 0.01%)
Compression ratio (ZIFF corpus)
34 00 33.77 33.77
33.4033.6033.8034.00
ratio
(%)
32.88 32.8832.88 32.89
32.8033.0033.2033 0
mpr
essi
on
32.4032.60
PH ETDC RPBC
Com
Method used
Original Reorganized with WT
Resultados experimentalesResultados experimentalesWTDC como compresor
Tiempo de compresión
160
WTDC
120
140
(sg.
)
ETDCgzip
80
100
com
pres
ión
(
40
60
Tiem
po d
e c
CALG FT91 CR FT92 ZIFF FT93 FT94 AP FTALL ALL0
20
CALG FT91 CR FT92 ZIFF FT93 FT94 AP FTALL ALL
Corpus utilizado
Resultados experimentalesResultados experimentalesWTDC como compresor
Tiempo de compresiónPrácticamente idénticos
(2% - 4% peor)
Compression time (ZIFF corpus)
10.9711.03 11.0211.47 11.3911.2010.0012.0014.00
time
(s)
4.006.008.00
mpr
essi
on t
0.002.00
PH ETDC RPBC
Com
Method used
Original Reorganized with WT
Resultados experimentalesResultados experimentalesWTDC como compresor
Tiempo de descompresión25
WTDC
20
ión
(sg.
)
ETDCgzip
10
15
desc
ompr
esi
5
10
Tiem
po d
e
CALG FT91 CR FT92 ZIFF FT93 FT94 AP FTALL ALL0
Corpus utilizado
Corpus utilizado
Resultados experimentalesResultados experimentalesWTDC como compresor
Tiempo de descompresiónMayores diferencias, pero todavía “muy rápido”
(10% 20%)
Decompression time (ZIFF corpus)
(10% - 20%)
2.25 2.292.31 2.692.84
2.662 503.003.50
time
(s)
1.001.502.002.50
mpr
essi
on t
0.000.50
PH ETDC RPBC
Dec
om
Method used
Original Reorganized with WT
Resultados experimentalesWTDC como índiceWTDC como índice
Tiempo de contar el número de ocurrencias de una palabra(Corpus AP)
contar ocurrencias
403,35400
450403,35
1%
250
300
350
400
s) 208,05
143,71 143,56
100
150
200
250
t (m
s
143,56143,71
208,05
0,037935 0,045464 0,005492 0,000218570
50
100
03 3 208 0 1 3 1 1 3 6
Palab. 1 byte Palab. 2 bytes Palab. 3 bytes Palab. 1 ocurr
0,037935 0,0454640,005492 0,000218570,05
ETDC 403,35 208,05 143,71 143,56
WTDC 0,037935 0,045464 0,005492 0,000218571
Resultados experimentalesWTDC como índiceWTDC como índice
Tiempo de buscar la primera ocurrencia de una palabrap p p(Corpus AP)
buscar 1ª 1%buscar 1
54,42
50
60
54,42
30
40
50
ms)
18,07
18,07
10
20
30
t (m
0,7857
0 5
0,0714 0,7857 0,0950710,0335710,0008457 0,1020
10
ETDC 0 0714 0 7857 18 07 54 42
1 byte 2 bytes 3 bytes 1 ocurr
0,0714 0,0950710,0335710,0008457
0,1020,5
ETDC 0,0714 0,7857 18,07 54,42
WTDC 0,0008457 0,033571 0,095071 0,102
Resultados experimentalesWTDC como índiceWTDC como índice
Ti d l li l 10 000 i i i d l b Tiempo de localizar las 10.000 primeras posiciones de una palabra(Corpus AP)
localizar 10.000 ocurrencias
149,14160 149,14
1%
110,0714109,642100
120
140
s)
110,0714109,642
29,1440,043
40
60
80
t (m
s
29,1440,043
7,5914 0,2095 0,1021430
20
ETDC 29,14 149,14 109,642 110,0714
1 byte 2 bytes 3 bytes 1 ocurr
7,5914 0,2095 0,102143
WTDC 7,5914 40,043 0,2095 0,102143
Resultados experimentalesWTDC como índiceWTDC como índice
Tiempo de recuperar los 10.000 primeros snippets de una palabra(Corpus AP)
recuperar 10.000 snippets
3
1%
2,4642
2
2,5
1,1657
1
1,5
t (s)
0,159280,054850,22428 0,15907
0,010257 0,00036430
0,5
C 0 05485 0 22428 0 15907 0 15928
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
Resultados experimentalesWTDC como índiceWTDC 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)
recuperar 10.000 snippets
3
6%
2
2,5
1
1,5t (s)
0,159280,1835 0,0914290,054850,22428 0,15907
0,00071429 0,00036430
0,5
ETDC 0 05485 0 22428 0 15907 0 15928
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
Resultados experimentalesWT** como índiceWT como índice
Búsquedas (ALL corpus)
Memoria Count (ms) Locate (ms)1ª occ
Locate (s)todas
Snippet (s)10 palabras
Búsquedas (ALL corpus)
PH 35.13% 2605.6 48.861 2.648 7.955ETDC 35.95% 1027.4 22.933 0.940 1.144• WT+ mejora todas las capacidades de búsqueda si la
técnica “de partida” no se auto sincronizabaRPBC 35.14% 1996.3 41.66 2.009 7.283
WPH 35.13% 238.5 17.173 0.754 72.068
técnica de partida no se auto-sincronizaba.
• Sin estructuras adicionales (memoria extra), los WT’s obtienen resultados pobres a la hora de recuperarWTDC 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
obtienen resultados pobres a la hora de recuperar snippets.
• Con un poco de espacio extra (1%) ETDC es todavíaWPH+ 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
Con un poco de espacio extra (1%), ETDC es todavía mejor que WTDC+ al recuperar snippets. Aumentando ese espacio hasta un 6% extra WTDC+ mejora a ETDC.
WRPBC+ 36.09% 0.015 0.018 0.125 5.036
Resultados experimentalesIndexación implícitaIndexación implícita
Comparación frente a otros índices:— WTDC+ variando el tamaño extra disponible— WT-sobre huff-word (bit-oriented word-based)— WT-sobre huff-word (bit-oriented word-based)
— Índice invertido comprimido sobre texto comprimido con ETDC / HUFFMANHUFFMAN Direccionamiento a bloques parámetro Índice comprimido como en Rice Codes
— WCSA
Medimos tiempos para locate, display snippet, extract
Resultados experimentalesIndexación implícita
L t l b
Indexación implícita(corpus ALL)
Locate palabras
Resultados experimentalesIndexación implícita
L t f k l b
Indexación implícita(corpus ALL)
Locate frases k-palabras
Resultados experimentalesIndexación implícita
Di l 20 d
Indexación implícita(corpus ALL)
Display 20-word snippets
Resultados experimentalesC l i
Wavelet tree sobre códigos orientados a byte:
Conclusiones
Wavelet tree sobre códigos orientados a byte:
— Le da sincronismo a códigos que no se auto-sincronizan, t i d ( i) ti l id dmanteniendo (casi): ratio y velocidad
La mejor opción es la utilización de Plain Huffman Mantiene el mejor ratio de compresión Gracias a la reorganización, se auto-sincronizaGracias a la reorganización, se auto sincroniza
— Se obtienen propiedades de indexación implícita E ibl II bl ( ) i í di ñ Es posible superar a un II-bloques (…), si queremos un índice pequeño
Es un nuevo autoíndice
I t d ió l ióIntroducción a la compresión y a la autoindexación de texto
Antonio FariñaAntonio FariñaLaboratorio de Bases de Datos
Universidade da CoruñaUniversidade da CoruñaSegovia, 11 de abril de 2013