Compresión semistática orientada a palabras Guión MotivaciónPlain Huffman y Tagged Huffman...

Antonio Fariña

Motivación

Compresión semistática orientada a palabras Guión

Compresión Huffman semistática

Compresores semiestáticos densos

• Lenguaje Natural: leyes.

• Indexación orientada a palabras

Antonio Fariña

Orientación a palabras ¿por qué?

Lenguaje natural: Leyes de Zipf

y de Heaps

Heaps:: el tamaño

tiene

poca

importancia

si

tenemos

textos

grandesZipf:: La distribución

de frecuencias

de las

palabras

de un texto

es

muy

sesgada

Antonio Fariña

Orientación a palabras (refs)

Refs básicas.

Antonio Fariña

Motivación



• Codificación Orientada a palabras

• Huffman orientado a palabras: Plain y Tagged Huffman


Antonio Fariña

Huffman orientado a palabras

Uso de orientación a palabras: —

Bentley, Sleator, Tarjan, and Wei (CACM-1986) ??—

Moffat

propuso usar palabras en vez de caracteres (+huffman)

La distribución de frecuencias de las palabras es más sesgada

0

2

4

6

8

10

12

14

16

18

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

frec

Word freq distributionCharacter freq distribution (Spanish)

Se consiguen

ratios de compresión

de hasta

25%

(en inglés)

Así

los elementos básicos para compresión y Text Retrieval son los mismos:

las palabras

Antonio Fariña

Compresión + indexación

Ejemplo:

poco

coco

El

que

come

compra

El que poco coco come

poco

coco compra Texto original:

Vocabulario Esquema codificación

10110010001101100111

pocococo

Elque

comecompra

5

13

6

7

2328

11

Índice invertido orientado a palabras:

1028

C1C2C3C4C5C6

Texto comprimido: 0010

0011 10

11 0110

10 11

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

Antonio Fariña

Motivación



• Codificación Orientada a palabras

• Huffman orientado a palabras: Plain y Tagged Huffman


Antonio Fariña

Plain Huffman y 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”

para el 1er bit de los

bytes

restantes

1xxxxxxx 0xxxxxxx 0xxxxxxx

Antonio Fariña

Plain Huffman y Tagged Huffman Codificación

Construcción

Huffman b-ario: —

Plain huffman

aridad: 2b=256, Tagged Huffman 2b=128

—

Codificación

huffman

normal

Bottom-Up:

1ª

iteración: R=número

de nodos

último

nivel

Restantes

iteraciones: eligiendo

2b

nodos

menos

frecuentes

Antonio Fariña

Plain Huffman y Tagged Huffman Ejemplos.

Distribución

uniforme: pi

=1/17 Distribución

exponencial: pi

= 2-i

Asúmase (b=3, bytes

“especiales”

de sólo 3 bits)

Obténgase

la codificación


para

los

vocabularios

en los

2 escenarios

siguientes:

Antonio Fariña

Plain Huffman y Tagged Huffman Ejemplo 1

Antonio Fariña

Plain Huffman y Tagged Huffman Ejemplo 2

Antonio Fariña

Plain Huffman & Tagged Huffman Búsquedas sobre texto comprimido

Ejemplo (b=2): to be lucky or

not

Búsqueda directa (comprimir el patrón y buscarlo) Empezar la búsqueda en cualquier lugar (y la descompresión) Búsqueda tipo Boyer-Moore

es posible (saltando bytes)

TH: Búsquedas mejoradas

to be lucky or not1111 0011 00

11001100

01 10

Falso

emparejamiento

Busquemos “lucky”

11 00lucky

10not

01or

00be

PLAIN HUFFMAN

11 11to

to be lucky or not

11010101

10 1110101001010100

1100 110100Imposible

emparejamientos

falsos

11 01 01 00lucky

11 01 00not

11 00or

10be

TAGGED HUFFMAN

11 01 01 01to

permite búsquedas eficientes

Antonio Fariña


Plain

Huffman. (árbol de aridad

2b=256)

—

Ratio +-

30-32%

—

Búsqueda simulando descompresión

(frases: Shift-Or autómata)

Tagged Huffman. (árbol de aridad

2b-1

=128)

—

Pérdida en el ratio de compresión (3.5 puntos)

Ratio +-

33.5-35%

—

El bit de marca indica el inicio de los códigos:

Búsquedas directas mejoradas (al ser posible usar Boyer-Moore)

Descompresión aleatoria

Sincronismo: Es posible (1)

ir a cualquier offset del texto comprimido, (2)

buscar el principio de un código allí, y (3)

comenzar la descompresión desde esa posición.

Antonio Fariña

Motivación

Compresión Huffman semiestática

Compresores semiestáticos densos• End

Tagged Dense Code• (s,c)-

Dense Code• Resultados Teóricos• Resultados Empíricos


Antonio Fariña

Compresores semistáticos densos End-Tagged Dense Code

Pequeño cambio: Una marca señala el final de un código

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

Primer bit

es:“1”

--> para el 1er

bit del último byte“0”

--> para el 1er

bit del resto de bytes1xxxxxxx

0xxxxxxx

Antonio Fariña


Pequeño cambio: Una marca señala el final de un código

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

Primer bit

es:“1”

--> para el 1er

bit del último byte“0”

--> para el 1er

bit del resto de bytes1xxxxxxx

0xxxxxxx

Códigos de 2 bytes 1xxxxxxx0xxxxxxx

Códigos de 3 bytes 1xxxxxxx0xxxxxxx0xxxxxxx

Códigos de 1 byte 1xxxxxxx

Antonio Fariña


Esquema de codificación

.....

1283

Las palabras

128+ 1282+1

a 128 +1282 +1283 usan

tres

bytes (1283

= 221

códigos)

00000000:00000000:10000000……01111111:01111111:11111111

1282 palabras

de 128+1

a 128+1282

(1282

= 214

códigos

de 2 bytes)

00000000:10000000…..01111111:11111111

128 palabras

más

frecuentes

(128

= 27

códigos

de 1 byte)

1000000010000001…..11111111

Los códigos dependen de la posición de la palabra en el ránking no de su frecuencia

Antonio Fariña

Procedimiento de codificación secuencial


Procedimiento de codificación directa

(“al vuelo”)

—

Ordenación de palabras por frecuencia—

Asignación de códigos ...0xxxxxxx< 2b-1

0xxxxxxx< 2b-1

1xxxxxxx≥

2b-1

Ci

codificar(i)i

decodificar(Ci

)

Antonio Fariña

Procedimiento de codificación secuencial


—

Ordenación de palabras por frecuencia—

Asignación de códigos ...0xxxxxxx< 2b-1

0xxxxxxx< 2b-1

1xxxxxxx≥

2b-1

Pon las formulas y las complejidades

Antonio Fariña


Procedimiento de codificación directa

(“al vuelo”)

Ci

codificar(i)i

decodificar(Ci

)Pon las formulas y las complejidades

O(log

i)

O(|x|) = O(log

i)

Ej. i=decodifica(x)

Antonio Fariña


Descompresión: dos pasos—

Cargar el vocabulario ordenado

—

i decodificar(Ci

)

:: O(bytes

T.Comp)

C2 C3 C4 C0

C5

C10

C6 C7

C8 C1 C9

C0

C1 …

Datoscompr.

de*no*En*… cabecera

Fichero comprimido

vocabulario

de

no

En

un

lugar

la

0

1

2

3

4

5

Texto plano

En un lugar de

la mancha de

cuyo nombre

no quiero

acordarme no

……

decode

Antonio Fariña

Búsquedas directas:

—

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 densos End-Tagged Dense Code: búsquedas TC

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

3) Tras

un emparejamiento

chequear

si

es

una

ocurrencia real del patrón

Es una

ocurrencia

o el sufijo

de un código

más

largo?

Byte previo

≥

128

?

Antonio Fariña

Compresores semistáticos densos End-Tagged Dense Code: búsquedas TC

Algoritmo

Horspool

modificado

para

ETDC.

En ETDC, c=128

Alg:

Programa

C:

TRUCO para

evitar

(i=0)39 25 234 234100 129 25 234110 25 2342 2 251

25 2340 1 2 3 z-1

0 k-1

T

P

Antonio Fariña


Es un código denso. Pueden utilizarse todos los códigos 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,

—

Acceso aleatorio.

Codificación y decodificación eficiente—

Procedimientos secuencial

y directo

Fácil de programar

Antonio Fariña

Compresores semiestáticos densos• End



Motivación



Antonio Fariña

Compresores semistáticos densos (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)

Adaptar (s,c) al vocabulario s minimizando tamaño Texto Comp.—

Número de palabras—

Distribución de frecuencia de las palabras

End-Tagged

Dense Code

es un (128,128)-Dense Code

Por qué

usar valores fijos de s y c?

Antonio Fariña


20 15 12 11 8 8 3 3 2 1 1

20 35 47 58 … … … 1000Num occs

Frec. acum

* k ;

Antonio Fariña


—

Stoppers: último

byte. s valores

entre

[0,s-1]—

Continuers: otros

bytes. c valores

entre

[s, 255]

0 ...s-1

s palabras más frecuentes

ss+1...255

01 ...s-1

sc palabras de s+1 a s+sc

s... 255

s... 255

sc2 palabras de s+sc+1 a s+sc+sc20... S-1

Esquema de codificación

http://vios.dc.fi.udc.es/codes

Antonio Fariña


Ejemplo

(b=3)

End-Tagged

Dense Code

es un (2b-1,2b-1)-DC

1,301,161,071,03Longitud media del código

0,010,010,010,01[111][010]0,005J

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

0,180,180,090,09[101]0,09F

0,280,140,140,14[100]0,14E

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

ETDC(5,3)(6,2)PH(4,4)-

DC(5,3)-DC(6,2)-DCP.H.FreqPalabra

[110][011]

[110][010]

[110][001]

[110][000]

[101]

[100]

[011]

[010]

[001]

[000]

[101][100]

[101][011]

[101][010]

[101][001]

[101][000]

[100]

[011]

[010]

[001]

[000]

[101][001]

[101][000]

[100][011]

[100][010]

[100][001]

[100][000]

[011]

[010]

[001]

[000]

Antonio Fariña

Codificación

Secuencial


Codificación

directa

Ci

codifica(s, i)i decodifica(s, Ci

)

...xxxxxxxx xxxxxxxx zzzzzzzz

s≤

vc

< 2b-1 0≤

vs

< ss≤

vc

< 2b-1

Pon las formulas

Antonio Fariña

Codificación

Secuencial


Codificación

directa

Ci

codifica(s, i)i decodifica(s, Ci

)

...xxxxxxxx xxxxxxxx zzzzzzzz

s≤

vc

< 2b-1 0≤

vs

< ss≤

vc

< 2b-1

Pon las formulas

O(|x|) = O(log

i)

O(log

i)

Antonio Fariña

Compresores semistáticos densos (s,c)-Dense Code : búsquedas TC

Algoritmo

Horspool

modificado

para

SCDC.

En SCDC, c=2b-s = 256-s

Alg:

Antonio Fariña


Es un código

denso—

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

Codificación y decodificación simple

¿Marca?

(byte valor < s)—

Mismas

capacidades

de búsqueda

que

End-Tagged Dense Code

y Tagged Huffman

S óptimo

entre

180 y 190

Antonio Fariña

Guión de la exposición

• End




Motivación


Antonio Fariña

Es posible obtener nuevas cotas analíticas de la compresión que puede alcanzarse con Huffman

usando (s,c)-DC

Gonzalo Navarro and

Nieves Brisaboa.

New

Bounds

on

D-ary

Optimal

Codes.

Information Processing Letters (IPL) 96(5):178-

184, 2005

Compresores semiestáticos densos Acotación analítica de Huffman

Antonio Fariña

Nuevas cotas analíticas de Huffman usando (s,c)-DC


Siendo el número de palabras codificables con k bytes,

indica el número de palabrascodificables con k bytes

Por tanto, la probabilidad de los lossímbolos codificados con hasta k bytes

es:

Dada la entropía (D bits): ,

Obteniéndose:

Antonio Fariña


Por la ley de Zipf: , , para ciertas constantes y donde:

Cota Superior

Sustituyendo c=D-s y minimizando, obtenemos una cota superior mínima cuando: y

Partiendo de que

Antonio Fariña


Cota Inferior

Análogamente:

Tomando

Puesto que : nuestra cota superior, viene dada por:

Antonio Fariña

• End




Motivación



Antonio Fariña

Compresores semistáticos densos Resultados empíricos y Plataforma de prueba

Textos del TREC-2

y TREC-4

Mostrando resultados para:—

Ratio de compresión—

Tiempo de codificación y compresión—

Tiempo de descompresión—

Velocidad de búsqueda

CORPUS Tamaño (bytes) Nº

palabras Nº

palabras diferentes

CALGARY 2,131,045 528,611 30,995

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

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

—

Intel Pentium-III (x2) 800 Mhz

con 768Mb RAM.

Debian

GNU/Linux

(kernel

2.2.19)

gcc

3.3.3 20040429 y optimización –O9

Time muestra CPU user-time

Antonio Fariña

Codificación

Extracción de vocabulario

Proces. del fichero

n1

Vector de palabras ordenado

pal

frec

Huffman

ETD

C

Generación secuencialcódigos

Creando árbol Huffman Buscar valores (s,c) óptimos

Lista acumuladade frecuencias

Encontrar mejor S

Tabla Hash

Fase de compresión

To

T1

cons

árb

ol est alturas

Gen

erac

ión

de c

ódig

os(s-c) DC

palcod

Generación secuencialcódigosco

mpr

esió

n

1apa

sada

2apa

sada

Compresores semistáticos densos Tiempos de codificación y compresión

Antonio Fariña

Compresores semistáticos densos Resultados Empíricos

PH (s ,c )-DC ETDC TH

28

29

30

31

32

33

34

35

com

pres

sion

ratio

(%)

technique

Ratio de compresión (%)

(s,c)-DC ETDC TH30.73 30.88 31.56 34.16

PH

0.8 pp 2.5 pp<(s,c)-DC ETDC TH<<

0.2 ppPH

>ETDC (s,c)-DC TH>=PH

Velocidad de compresión (Mb/sg.)


5.3

5.4

5.5

5.6

5.7

5.8

5.9

6

6.1

6.2

Com

pres

sion

spe

ed (M

byte

s/se

c)

technique

5.92 5.88 5.90 5.83(s,c)-DC ETDC THPH

P H (s ,c )-DC E TDC TH

100

120

140

160

180

200

220

240

260

280

Enc

odin

g tim

e (m

sec.

)

technique

Tiempo de codificación (msg.)

260 143 104 270PH (s,c)-DC ETDC TH

25% 45% 2%< < <ETDC (s,c)-DC PH TH

1,5% 4%= > >ETDC PH (s,c)-DC TH

Velocidad de descompresión (Mb/sg.)


20.5

21

21.5

22

22.5

23

23.5

24

24.5

25

Deo

mpr

essi

on s

peed

(Mby

tes/

sec)

technique(s,c)-DC ETDCPH TH

23.86 23.55 24.15 22.51

Antonio Fariña

Compresores semistáticos densos Búsquedas de patrones simples

PH (s,c)-DC ETDC TH

1.6

1.7

1.8

1.9

2

2.1

2.2

2.3

2.4

2.5

Sea

rch

time

(sec

.)

technique

2.30 1.70 1.80 2.00PH (s,c)-DC ETDC TH

5% 5-10% 10%< < <(s,c)-DC ETDC TH PH

Tiempo de búsqueda (sg.)

Buscando patrones:-

Formados por 1 única palabra-

Cuyos códigos tienen la misma longitud

Antonio Fariña

TH SCDC ETDC Plain

text15-20% 5% 400%

Multipatrón < < <

1.987 2.497 2.283

14.602

10.667 10.499.143

02468

10121416

sear

ch ti

me

(sec

.)

TH ETDC SCDC DETDC+DEC DETDC AGREP rev Set-Hoorspol

Algorithm used

Multi-pattern searches

Compresores semistáticos densos Búsquedas multipatrón (100pats.)

Plain TextCompressed Text

Antonio Fariña

Compresores semistáticos densos Resultados Empíricos : Resumen

100 120 140 160 180 200 220 240 260 28030

31

32

33

34

35

encoding time (msec)

com

pres

sion

ratio

18 18.2 18.4 18.6 18.8 19 19.2 19.4 19.6 19.8 2030

31

32

33

34

35

search time (sec)

com

pres

sion

ratio

Plain HuffmanTagged Huffman(s,c)-Dense CodeEnd-Tagged Dense Code

Plain HuffmanTagged Huffman(s,c)-Dense CodeEnd-Tagged Dense Code

Antonio Fariña


Antonio Fariña


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 (todo):—

Ratio de compresión, —

Velocidad de compresión y de descompresión—

Velocidad de búsquedas.

Antonio Fariña

Compresores semistáticos densos Ejercicio

Muestra

la codificación

ETDC que

se obtiene

para

los vocabularios

siguientes

(asúmanse

bytes de “sólo”

3 bits)

Distribución

uniforme: pi

=1/17 Distribución

exponencial: pi

= 2-i

¿En qué

se diferencian?

¿En qué

caso

se obtiene

una

compresión

mejor? Justifica

la respuesta.

Y si

el vocabulario

tuviese

20.000 símbolos. ¿qué

codigo

le correspondería

al símbolo

en la posición

16.512 (para

SCDC o ETDC)

Compresión semistática orientada a palabras Guión MotivaciónPlain Huffman y Tagged Huffman...

Documents

Transcript of Compresión semistática orientada a palabras Guión MotivaciónPlain Huffman y Tagged Huffman...