Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor...

69
AGuión de la exposición Compresores semiestáticos Compresores dinámicos (estadísticos) Motivación Conceptos básicos DETDC (Dynamic ETDC) DSCDC (Dynamic (s,c)-DC) Resultados Empíricos Compresores dinámicos Ligeros Compresión variable-to-variable

Transcript of Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor...

Page 1: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Guión de la exposición

Compresores semiestáticos

Compresores dinámicos (estadísticos)• Motivación• Conceptos básicos• DETDC (Dynamic ETDC)• DSCDC (Dynamic (s,c)-DC)• Resultados Empíricos

Compresores dinámicos Ligeros

Compresión variable-to-variable

Page 2: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos Motivación General

Tienen diferentes marcos de utilidad:

Compresión Semiestática (2 pasadas)

Almacenamiento de Texto

Recuperación de Texto

Compresión Dinámica (1 pasada)

Transmisión en tiempo real

Transmisión de datos y flujos de texto

No permite Recuperación de Texto*

Asociación variable: palabra código

Paralelismo de:

Compresión - transmisión y recepción – descompresión

Page 3: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos Motivación General

compresión

transmisión

recepción

descompresión

ejemplo: servicios mensajería instantánea

Transmisión usando compresión dindináámicamica

Hi JohnDid youknow …?

Page 4: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Guión de la exposición

Compresores semiestáticos

Compresores dinámicos• Motivación• Conceptos básicos• DETDC (Dynamic ETDC)• DSCDC (Dynamic (s,c)-DC)• Resultados Empíricos

Compresores dinámicos Ligeros

Compresión variable-to-variable

Page 5: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos (estadísticos) Conceptos básicos

Las frecuencias son computadas dinámicamente a medida que va apareciendo el texto.

El emisor y el receptor…

— Empiezan con un vocabulario vacío.

— Actualizan su vocabulario durante el proceso.

— Ambos procesos son simétricos.

Page 6: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos (estadísticos) Estructura básica simétrica

Estructura general compresión simétrica dinámica

Page 7: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos (estadísticos) Conceptos básicos

una

emisorreceptor

Ejemplo: una rosa rosarosa es una rosa

rosa

rosa

C1

C2

C3

C4

vocabulario

1

C2

1

una

rosa

C1

C2

C3

C4

vocabulario

1

1

Buscar “rosa” en el vocabulario del emisor y emitir código C2

Page 8: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos (estadísticos) Conceptos básicos

rosa

emisorreceptor

Ejemplo: una rosa rosarosa es una rosa

rosa

una

C1

C2

C3

una

C4

vocabulario

2

C2

rosa

1 rosa

C1

1C2

C3

C4

vocabulario

1

Emisor actualiza vocabulario (intercambio rosauna, e incrementa frec. A “rosa”)

Receptor decodifica C2 es una palabra existente escribe “rosa”

Page 9: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos (estadísticos) Conceptos básicos

receptor

Ejemplo: una rosa rosarosa es una rosa

rosa

rosa

una

C1

C2

C3

C4

vocabulario

2

1

CA

CB

CC

CD

CA

CB

CC

CD

Receptor actualiza vocabulario (intercambio rosa una)

La codificación asociada a cada palabra del vocabulario “puede” haber cambiado (ej. Huffman)

rosa

emisor

rosa

una

vocabulario

2

C2

1

Page 10: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos Conceptos básicos

Ejemplo: una rosa rosa eses una rosa

es es

“es” = nueva palabra añadir al final enviar código escape (Cc) seguido de “es” Por último la codificación puede haber cambiado de nuevo…

CCes

Page 11: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos Conceptos básicos: Huffman (refs)

Page 12: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos Conceptos básicos: Huffman

Huffman dinámico basado en caracteres: — [Fal73, Gal78], [Knu85] algoritmo FGK, [Vit87]

Page 13: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos Conceptos básicos: Huffman

Huffman dinámico basado en caracteres: — [Fal73, Gal78], [Knu85] algoritmo FGK, [Vit87]

Nuestra implementación: Dynamic Plain Huffman (DPH)— Basado en palabras

Uso de una tabla hash para almacenar las palabras (y encontrarlas eficientemente)

— Orientado al Byte

Peor ratio de compresión pero mejor velocidad de descompresión

Árbol 256-ario de Huffman Más complejo que el orientado a bit

— Árbol Huffman bien formado durante compresión/decompr.

Actualizar el árbol es una tarea compleja O(log h)

— Ratio de compresión en torno a 30-35 %.

Page 14: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos Conceptos básicos: Huffman

Nuestra implementación: Dynamic Plain Huffman (DPH)

En definitiva

Page 15: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos Conceptos básicos: Huffman

9

30

8 7

6

6

0

e

Ejemplo: b=2 hasta 22 = 4 hijos por nodo

Page 16: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos Conceptos básicos: Huffman

e

Page 17: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos Conceptos básicos: Huffman

g

Page 18: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos Conceptos básicos: Huffman

-0

0

a1

1

-0

-

Initial state

a

New letter

aaaaaaaa

Increase weight

a9

9

-0

b

New letter

a9

10

b1

-0

bbbbbbb

Increase weight

a9

17

b8

-0

c

New letter

a9

18

b8

c1

-0

d

New letter

a9

19

b8

c1

d1

1

-0

d

Increase weight

a9

20

b8

d2

c1

1

-0

1 2 3 4

5 6 7 8

Ejemplo: Huffman dinámico D-ario:texto transmitido: aaaaaaaaabbbbbbbbcddddddcccccceeefg

Page 19: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos Conceptos básicos: Huffman

e

New letter

a9

32

b8

c7

d6

8

e2

-0

a9

31

b8

c7

d6

7

e1

-0

dddd

Increase weight

a9

24

b8

d6

c1

1

-0

ccccc

Increase weight

a9

29

b8

d6

c6

6

-0

c

Increase weight

a9

30

b8

c7

d6

6

-0

e

Increase weight

e

Increase weight

a9

33

b8

c7

d6

9

e3

-0

f

New letter

a9

34

b8

c7

d6

10

e3

f1

-0

g

New letter

a9

35

b8

c7

d6

11

e3

f1

g1

1

-0

9 10 11 12

13 14 15 16

Ejemplo: Huffman dinámico D-ario:texto transmitido: aaaaaaaaabbbbbbbbcddddddcccccceeefg

Page 20: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos Conceptos básicos: Huffman

Coste de compresión O(nº símbolos de salida)— Orientado a byte O(nº bytes de salida)— Orientado a bit O(nº bits de salida)

La altura del árbol es:— Menor en la aproximación orientada a byte

Menos propagaciones de cambios hacia arriba en el árbol.

Page 21: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Guión de la exposición

Compresores semiestáticos

Compresores dinámicos• Motivación• Conceptos básicos• DETDC (Dynamic ETDC)• DSCDC (Dynamic (s,c)-DC)• Resultados Empíricos

Compresores dinámicos Ligeros

Compresión variable-to-variable

Page 22: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

enviar código

Compresores dinámicos densos Dynamic End-Tagged Dense Code

Usa los algoritmos de codificación y decodificación directa— Requisitos: mantener el vocabulario ordenado por frecuencia

speed

vocabulario

1 the 8

2 is 4

3 code 2

4 tag 2

5 Huffman 2

6

7 ratio 1

8 1

ETDC

speed

1

C8 = encode (8)

Ejemplo

Page 23: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

intercambio con top

Incrementar frecuencia

Compresores dinámicos densos Dynamic End-Tagged Dense Code

Usa los algoritmos de codificación y decodificación directa— Requisitos: mantener el vocabulario ordenado por frecuencia

vocabulario

1 the 8

2 is 4

3 code 2

4 tag 2

5 Huffman 2

6

7 ratio 1

8 1

speed

ETDC

2

Ejemplo

Page 24: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariñaintercambio con topenviar códigoincrementar frecuencia

Compresores dinámicos densos Dynamic End-Tagged Dense Code

Usa los algoritmos de codificación y decodificación directa— Requisitos: mantener el vocabulario ordenado por frecuencia.

speed

vocabulario

1 the 8

2 is 4

3 2

4 tag 2

5 Huffman 2

6

7 ratio 1

8 1ETDC

2 C6 = encode (6)

code

speed

3

Ejemplo: “llega speed”

Page 25: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

intercambio con topenviar código incrementar frecuencia

Compresores dinámicos densos Dynamic End-Tagged Dense Code

Usa los algoritmos de codificación y decodificación directa— Requisitos: mantener el vocabulario ordenado por frecuencia.

speed

vocabulario

1 the 8

2 is 4

3 2

4 tag 2

5 Huffman 2

6

7 ratio 1

8 1ETDC

2 C6 = encode (6)

code

speed

Ejemplo: speed otra vezvocabulario

1 the 8

2 is 4

3 2

4 tag 2

5 Huffman 2

6

7 ratio 1

8 1ETDC

2

speed

code

3

Page 26: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos densos Dynamic End-Tagged Dense Code

Transmission of words C, C, D and D having transmitted ABABBC earlier.

Reception of c2, c2, c3D# and c3 having received c0A#c1B#c0c1c1c2C# previously.

Page 27: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos densos Dynamic End-Tagged Dense Code

Page 28: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos densos Dynamic End-Tagged Dense Code

DETDC es mucho más simple que Huffman Dinámico:

— Mantener las palabras ordenadas Vs mantener un árbol de Huffman.

— Ejecutar un único intercambio por código O(1) Vs O(altura árbol Huffman)

— Coste de la compresiónO(nº códigos de salida) Vs O(nº bytes de salida)

Page 29: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Guión de la exposición

Compresores semiestáticos

Compresores dinámicos• Motivación• Conceptos básicos• DETDC (Dynamic ETDC)• DSCDC (Dynamic (s,c)-DC)• Resultados Empíricos

Compresores dinámicos Ligeros

Compresión variable-to-variable

Page 30: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos densos Dynamic (s,c)-Dense Code

Generalización del ETDC Dinámico— Codificación y decodificación directa,— Mantener el vocabulario ordenado y,— Mantener un valor óptimo de s

Distintas aproximaciones para ajustar valor de s:— Contar bytes

Con historia, Sin historia, Umbral

Ref.:Brisaboa, N. R.; Fariña, A.; Navarro, G.; Paramá, J. R. “New

Adaptive Compressors for Natural Language Text”. En Software, Practice & Experience(38)-2. pp. 1429-1450, 2008.

Page 31: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos densos Dynamic (s,c)-Dense Code

s = 256 mientras n < 256 con código de un byte

s = 255 mientras n < 510 usando códigos de dos bytes

s cae hasta s=129 (para n = 16,512) códigos de tres bytes son usados (s = 129 maximiza s + sc = # 1- or 2-byte códigos)

Entonces … el valor s crece para mejorar la compresión en palabras con alta frecuencia

0 50,000 100,000 150,000 200,000 250,000

140

160

180

200

220

240

n

s va

lue

s=129

Ap Newswire corpus

0 5,000 10,000 15,000 20,000 25,000 30,000

140

160

180

200

220

240

n

s v

alue

s=129

Calgary corpus

Evolución del valor de s

Page 32: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos densos Dynamic (s,c)-Dense Code

Evolución Otros casos reales.

Page 33: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos densos Dynamic (s,c)-Dense Code

Después de procesar una palabra …— s puede incrementarse en 1: s s +1— s puede decrementarse en 1: s s -1

Usamos 3 variables prev, curr, y next para acumular el tamaño del texto comprimido para esos 3 valores de s.

prev Tamaño texto Compr. sí #stoppers = s-1

Tamaño texto Compr. sí #stoppers = s0Curr

Tamaño texto Compr. sí #stoppers = s+1next

If prev < curr then s0 s-1

If next < curr then s0 s+1

Page 34: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos densos Dynamic (s,c)-Dense Code

Supongamos prev < s0 y por tanto s s-1

Pero…. ¿como reinicializar prev?

prev5 6 9

curr next

0 0curr nextprev

0

s0 s+1s -1s -2

Descarta HistorialInicialización a 0

prev5 6 9

curr next

5 6curr nextprev

5

s0 s+1s -1s -2

Guarda Historial (next s0 +1)Inicialización a S0

¿Uso de un umbral? menos cambios pérdida de compresión

Page 35: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos densos Dynamic (s,c)-Dense Code

Page 36: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Guión de la exposición

Compresores semiestáticos

Compresores dinámicos• Motivación• Conceptos básicos• DETDC (Dynamic ETDC)• DSCDC (Dynamic (s,c)-DC)• Resultados Empíricos

Compresores dinámicos Ligeros

Compresión variable-to-variable

Page 37: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Técnicas comparadas:— Versiones Semiestáticas y Dinámicas de:

Plain Huffman

(s,c)-Dense Code

End-Tagged Dense Code

— Compresor aritmético basado en palabras y orientado a bit— Gzip— Bzip2

Comparaciones en:— Ratio de compresión— Velocidad de compresión— Velocidad de descompresión

Compresores dinámicos densos Resultados Empíricos

Page 38: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos densos Resultados Empíricos: dinámicos

D-PH D-SCDC D-ETDC31.5

32

32.5

com

pres

sion

ratio

(%)

D-PH D-SCDC D-ETDC55006000650070007500

com

pres

sion

spe

edK

byte

s/se

c

D-PH D-SCDC D-ETDC

800010000120001400016000

deco

mpr

essi

on s

peed

Kby

tes/

sec

31.71 31.84 32.54

5,724 6,944 7,459

7,791 14,067 14,800

Ratio de compresión

(%)

Veloc. compresión(Kbytes/sg)

Veloc. Descompresión

(Kbytes/sg)

Huffman mejor compresión, pero más lento que DETDC

DSCDC 5% más lento que DETDC, pero con mejor compresión

FT_ALL

Page 39: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos densos Resultados Empíricos: dinámicos

Ratio compresión: dinamismo empeora imperceptiblemente el ratio

Veloc compresión: 1-pass más rápidos (excepto DPH en textos largos)Veloc descompresión: 2-pass mucho más rápidos (no hay updates)

PH SCDC ETDC

25

30

35

PH SCDC ETDC

55006000650070007500

PH SCDC ETDC

8000

10000

12000

D-PH D-SCDC D-ETDC

D-PH D-SCDC D-ETDC

D-PH D-SCDC D-ETDC

Ratio de compresión

(%)

Veloc. compresión

(Kbytes/sec)

Veloc descompresión(Kbytes/sec)

31.696 31.839 32.527 31.710 31.849 32.537

5,922 5,882 5,888 5,724 6,944 7,459

23,856 23,552 24,146 7,791 14,067 14,800

FT_ALLSemi-static Dynamic

Page 40: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos densos Resultados Empíricos: dinámicos

CALGARY FT91 CR FT92 ZIFF FT93 FT94 AP FT_ALL ALL

30

40

50

60

70

80

diff in decompression speed semi-static VS dynamic

% g

ain

ETDC SCDC PH

CALGARY FT91 CR FT92 ZIFF FT93 FT94 AP FT_ALL ALL-10

0

10

20

30

40

50

% lo

ss

diff in compression speed semi-static VS dynamic

ETDC SCDC PH

Gain in compression speed of the dynamic methods G

ain

(%)

Loss in decompression speed of the dynamic methods lo

ss(%

)

Page 41: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos densos Resultados Empíricos: Ratio

Ratio de compresión: bzip2 el mejor. Cód. Densos mejor que gzip

Page 42: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos densos Resultados Empíricos: Tiempo compresión

Velocidad compresión: Compresores densos son más rápidos (excp Dvbyte)

Page 43: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos densos Resultados Empíricos: Tiempo descompresión

Velocidad descompresión: gzip es el más rápido (excep semistáticos).

DETDC y DSCDC los siguientes

Page 44: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos densos Resultados Empíricos: Tiempo búsqueda

Es posible buscar ?

simular descompresión… pero sin necesidad de escribir códigos !

(patrones con 5 letras)

Técnicas semistáticas son prácticamente “imbatibles”

Page 45: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos densos Resultados Empíricos: compresión Vs tiempo

Ratio compresión Vs tiempo de búsqueda multipatrón.

Page 46: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

0 100 200 300 400 500 600 700 80025

30

35

40

45

compression time (sec)

com

pres

sion

ratio

(%) Dynamic PH

Dynamic (s,c)-Dense CodeDynamic End-Tagged Dense CodeArithmetic encodergzip -fbzip2 -b

0 50 100 150 200 25025

30

35

40

45

decompression time (sec)

com

pres

sion

ratio

(%) Dynamic PH

Dynamic (s,c)-Dense CodeDynamic End-Tagged Dense CodeArithmetic encodergzip -fbzip2 -b

Compresores dinámicos densos Resultados Empíricos: Resumen

Buen equilibrio entre

Ratio Compresión y

Tiempo Compresión

Buen equilibrio entre

Ratio Compresión y

Tiempo Descompresión

Page 47: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

3 técnicas dinámicas estadísticas orientadas a palabras— Dyn-Huffman comprime más que los otros— DETDC es el más rápido (DSCDC está cercano a DETDC)

Dinamismo:— Poco impacto en el ratio de compresión— Semiestáticos son más lentos que dinámicos al comprimir— Semiestáticos mucho más rápidos al descomprimir

+ Su interés— Menos compresión que bzip2 y aritm. pero mucho más rápido— Mejor ratio de compresión y velocidad que gzip. Más lento en descompresión— Búsquedas más rápidas que lzgrep (uncompress+search).

Simular descompresión: asociación “palabra” “código” varía

Buen ratio de compresión, Muy rápido en compresión y Buena velocidad en descompresión

Búsquedas simulando descompresión

Compresores dinámicos densos Sumario dinámicos

Page 48: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Guión de la exposición

Compresores semiestáticos

Compresores dinámicos

Compresores dinámicos Ligeros• Motivación• DLETDC (Dynamic Lightweight ETDC)• Búsquedas en texto comprimido con DLETDC• DLSCDC (Dynamic Lightweight (s,c)-DC)• Resultados Empíricos

Compresión variable-to-variable

Page 49: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos ligeros Motivación

El objetivo: Nuevas técnicas dinámicas, pero…— Descompresión más rápida ?

— Permitir búsquedas eficientes Texto comprimido

— Mantener ratio de compresión

— Mantener velocidad de compresión

— Permitiendo transmisión en tiempo real

Page 50: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos ligeros Motivación

Especialmente si …Tenemos problemas que impiden el uso de cualquier compresor dinámico:

— Una PDA tiene que poca potencia de cálculo y memoria.

— Necesitamos filtrar la información que llega a través de un canal (p.ej noticias)

Clasificación documentos según keywords

Page 51: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Guión de la exposición

Compresores semiestáticos

Compresores dinámicos

Compresores dinámicos Ligeros• Motivación• DLETDC (Dynamic Lightweight ETDC)• Búsquedas en texto comprimido con DLETDC• DLSCDC (Dynamic Lightweight (s,c)-DC)• Resultados Empíricos

Compresión variable-to-variable

Page 52: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Brisaboa, N. R., Fariña, A., Navarro, G., Paramá, J. R. Dynamic Lightweight Text Compression. ACM Transactions on Information Systems (ACM-TOIS). Por aparecer, 3(1). New York, NY, USA, 2010

Brisaboa, N. R., Fariña, A., Navarro, G., Paramá, J. R. Efficiently decodable and searchable natural language adaptive compression. Proc. of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'05), pp. 234-241. Bahia (Brazil), 2005

Page 53: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

New-symbolswap

01

128129

25500

127128129

128129

1270

1651116512

2550 128

016513 0 129

1272113662 127 2542113663 127 127 255

02113664 0 0 128

1272113661 127 253

Rank 1-byte2-byte

3-byteCompresores dinámicos ligeros

DLETDC – Ideas básicas

No mantienen correspondencia entre posiciNo mantienen correspondencia entre posicióón y cn y cóódigodigo

Códigos mantenidos explícitamente por el emisor

El receptor ignora rangos y frecuencias

EMISOR: guarda el vocabulario ordenado por frecuencia— Intercambia palabras si top(fi ) para mantener el vocabulario ordenado— Mantiene los códigos originales a no ser que sus longitudes varíen— De lo contrario: intercambio y notificación al receptor

RECEPTOR: mantiene palabras ordenadas por código— Decodifica los códigos

— Añade nuevos símbolos sobre Cnew

— Sólo intercambia cuando decodifica a Cswap

Page 54: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

2

C127

very 1

126

127

128

129

vocabulario

palabra

emisorreceptor

a

1

1 is

a

a

very

Ejemplo: … a rose rose is aa very nice one

126

127

128

129

vocabulario

palabra frec

125 rose125 rose 2 C125

is C126

a C127

C128

1-by

te2-

byte

No se necesita intercambio de código puesto que: “a” C127 y “is” C126

código

Compresores dinámicos ligeros DLETDC – Transmisión

Page 55: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

128

1127

12

C128 C127, Cswap

1

126

127

128

129

vocabulario

emisorreceptor

very

is

a

very

very

Ejemplo: … a rose rose is a veryvery nice one

126

129

vocabulario

125 rose125 rose 2 C125

a C127

is C126

very C128

1-by

te2-

byte

Se necesitar realiza un intercambio de códigos (1 y 2 bytes)

Compresores dinámicos ligeros DLETDC – Transmisión

palabrapalabra frec código

Page 56: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

128

130

Cnew

128

1127

1

1

126

127

129

vocabulario

emisorreceptor

nice

is

a

nice

very

Ejemplo: … a rose rose is a very nicenice one

126

129

vocabulario

125 rose125 rose 2 C125

a C127

is C126

very C128

1-by

te2-

byte

Caso en que se procesa una palabra nueva

nice

130

nice 1 C129 nice

Compresores dinámicos ligeros DLETDC – Transmisión

palabrapalabra frec código

Page 57: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Ejemplo: … a rose rose is a very nicenice one

Caso en que se procesa una palabra nueva

Compresores dinámicos ligeros DLETDC – Transmisión

Page 58: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos ligeros DLETDC – Ejemplo 2

Ejemplo: Transmisión de “… by step bit by bit”.

nueva antigua antigua antigua antigua (swap)

Page 59: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos ligeros DLETDC – pseudocódigo

Page 60: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Longitudes entre 1 y 2

Los intercambios empeoran el ratio de compresión y el tiempo de procesado.

¿Cuántos intercambios ocurren en la práctica?

ZIFF corpus4,6x107 words237,622 diff words

Compresores dinámicos ligeros DLETDC – Evolución de intercambios

Page 61: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Longitudes entre 2 y 3

Los intercambios empeoran el ratio de compresión y el tiempo de procesado.

¿Cuántos intercambios ocurren en la práctica?

ZIFF corpus4,6x107 words237,622 diff words

Compresores dinámicos ligeros DLETDC – Evolución de intercambios

Page 62: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Guión de la exposición

Compresores semiestáticos

Compresores dinámicos

Compresores dinámicos Ligeros• Motivación• DLETDC (Dynamic Lightweight ETDC)• Búsquedas en texto comprimido con DLETDC• DLSCDC (Dynamic Lightweight (s,c)-DC)• Resultados Empíricos

Compresión variable-to-variable

Page 63: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Horspool multipatrón— Patrones de búsqueda se colocan en un “trie”

Proceso de búsqueda: — Fase inicial

Búsqueda para el patrón ASCII: C_new | (patrón)

— Cuando encuentra

Lo reemplaza en el trie por su código: C_pat

— Observar los intercambios

Buscar C_swap C_pat * y C_swap * C_pat

Compresores dinámicos ligeros DLETDC – Búsquedas – Filtrado de términos

Page 64: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Guión de la exposición

Compresores semiestáticos

Compresores dinámicos

Compresores dinámicos Ligeros• Motivación• DLETDC (Dynamic Lightweight ETDC)• Búsquedas en texto comprimido con DLETDC• DLSCDC (Dynamic Lightweight (s,c)-DC)• Resultados Empíricos

Compresión variable-to-variable

Page 65: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Obtención de un DSCDC ligero.— Parámetros (s,c) variables rangos variables— Alternativas:

Fijar (s,c) y aplicar algoritmo de DLETDC

Cada cambio de (s,c) recolocación y notificación al receptor

Solución adoptada:— Almacenar posición x en lugar de código Cx | Cx encode(x,s)— Al cambiar s:

Recolocar y notificar sólo cambios en rango de 1 y 2 bytes

Ejemplo: s cambia de 190 a 191

191190189 194193192

C191C200 C193

s0

C195

191190189 194193192

C200C191 C193

s1

C195C191 código de

1 byte

Compresores dinámicos ligeros Dynamic Lightweight (s,c)-Dense Code

Page 66: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos ligeros Resultados Empíricos

24

26

28

30

32

34

36

com

pres

sion

ratio

(%)

Ratio de compresión (%)

35.09 33.69 33.19 33.66 27.98 25.98

Gzip DLETDC DLSCDC DETDC Arith Bzip250

100

150

200

250

300

350

400

Com

pres

sion

tim

e (s

ec)

Tiempo de compresión (sg.)

160.0 58.5 64.1 55.3 171.6 375.6

Gzip DLETDC DLSCDC DETDC Arith Bzip2

Tiempo de descompresión (sg.)

20

40

60

80

100

120

140

160

Deo

mpr

essi

on ti

me

(sec

)

21.1 16.3 15.9 25.3 147.2 156.2

Gzip DLETDC DLSCDC DETDC Arith Bzip2 5 25 1000123456789

1011

número de patrones

tiem

po m

edio

bús

qued

a (s

g)

Búsqueda multipatrón

ETDC:S-HDLSCDC:S-HDLETDC:S-HDETDC:allPlain: Set-HorsPlain:Agrep

Tiempo de búsqueda (sg.) (Promedio 10.000)

Page 67: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Compresores dinámicos ligeros Resultados Empíricos

Page 68: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

DLETDC y DLSCDC rompen la simetría común entre emisor y receptor en técnicas adaptativas

— Diseñados para: bajo ancho de banda y receptores poco potentes— Búsquedas posibles sobre texto comprimido dinámicamente

Compresores dinámicos ligeros:— Ratio de compresión competitivo (alrededor del 32-34% < gzip)

— Rápido al comprimir (más rápido otros estadísticos dinámicos)

— Muy rápido al descomprimir (incluso más rápido que gunzip!)

— Muy rápido en las búsquedas (3-4 veces más rápido que búsqueda en

texto plano)

Compresores dinámicos ligeros Sumario

Page 69: Guión de la exposicióndocencia.lbd.udc.es/edcaa/s3.0.pdf · Peor ratio de compresión pero mejor velocidad de descompresión Árbol 256-ario de Huffman Más complejo que el orientado

Antonio Fariña

Dense codes sumario

Familia “Densa” de compresores — Basados en palabras y orientada a bytes. — Ratio de compresión cercano al óptimo Plain Huffman— Muy fáciles de programar

Compresores semi-estáticos ETDC y SCDC— Mismas capacidades de búsqueda que Tagged Huffman.— Superan a Tagged Huffman en todos los aspectos.

Compresores dinámicos DETDC y DSCDC— Muy rápido al comprimir.— Buena velocidad de descompresión.

Compresores dinámicos ligeros DLETDC y DLSCDC— Permiten receptores con poca potencia PDA’s— Rapidísima descompresión, superan a gzip en todos los aspectos.— Permiten búsquedas.