it d ió lintroducción a la compresión y a la...

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!


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


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, …


Motivación

Estado del arte


• Compresión Estadística Semiestática



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)


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


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


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.


Motivación

Estado del arte


• Compresión Estadística semiestática



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


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


Construcción de abajo a arriba

0.30

ED

0.15 0.15



Construcción de abajo a arriba

0.30

0.45

ED ED

CB

0.25 0.20

0.15 0.15



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



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


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


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


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


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)


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


Motivación



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


Motivación



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)


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


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


Motivación



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


Motivación



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)


Antonio Fariña


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


parte 2 – autoindexaciónparte 2 autoindexación(wavelet trees)


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)


Motivación

Í

Wavelet trees

Índices invertidos

Wavelet trees


Índices invertidosEstructuraEstructura

SPIREworkshop

t i

0 103

58 159 399277147

Vocabulario Listas ocurr.

SPIREworkshop

121


stringretrieval

processinginformation

Europe

58 159 39992 31365 166 40680 302

476

stringretrieval


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


gretrieval


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…


Motivación

Í

Wavelet trees

Índices invertidos

Wavelet trees


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


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á


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.


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?


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


RECUPERACIÓN DE TEXTO


TEXTO WAVELET TREEA B A C D A CA B A C D A C



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


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


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)


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)


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’?



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)


¿dó de está e 9 0


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á


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


Motivación

Í

Wavelet trees

Índices invertidos

Wavelet trees


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


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


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


RECUPERACIÓN DEL TEXTO


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


RECUPERACIÓN DEL TEXTO



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:


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


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


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


Tiempo de compresión

160

WTDC

120

140

(sg.

)

ETDCgzip

80

100

com

pres

ión

(

40

60

Tiem

po d

e c


20

CALG FT91 CR FT92 ZIFF FT93 FT94 AP FTALL ALL

Corpus utilizado


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



Tiempo de descompresión25

WTDC

20

ión

(sg.

)

ETDCgzip

10

15

desc

ompr

esi

5

10

Tiem

po d

e


Corpus utilizado

Corpus utilizado


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


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


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


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


7,5914 0,2095 0,102143

WTDC 7,5914 40,043 0,2095 0,102143


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


ETDC 0,05485 0,22428 0,15907 0,15928

WTDC 2,4642 1,1657 0,010257 0,00036429


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


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


L t f k l b


Locate frases k-palabras


Di l 20 d


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


Antonio FariñaAntonio FariñaLaboratorio de Bases de Datos

Universidade da CoruñaUniversidade da CoruñaSegovia, 11 de abril de 2013

it d ió lintroducción a la compresión y a la...

Documents