Post on 29-Sep-2018
transcript
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
Motivación
Compresión semistática orientada a palabras Guión
Compresión Huffman semistática
• Codificación Orientada a palabras
• Huffman orientado a palabras: Plain y Tagged Huffman
Compresores semiestáticos densos
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
Compresión semistática orientada a palabras Guión
Compresión Huffman semistática
• Codificación Orientada a palabras
• Huffman orientado a palabras: Plain y Tagged Huffman
Compresores semiestáticos densos
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
Plain Huffman y Tagged Huffman
para
los
vocabularios
en los
2 escenarios
siguientes:
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 y Tagged Huffman
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
Compresión semistática orientada a palabras Guión
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
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
Códigos de 2 bytes 1xxxxxxx0xxxxxxx
Códigos de 3 bytes 1xxxxxxx0xxxxxxx0xxxxxxx
Códigos de 1 byte 1xxxxxxx
Antonio Fariña
Compresores semistáticos densos End-Tagged Dense Code
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
Compresores semistáticos densos End-Tagged Dense Code
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
Compresores semistáticos densos End-Tagged Dense Code
—
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
Compresores semistáticos densos End-Tagged Dense Code
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
Compresores semistáticos densos End-Tagged Dense Code
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
Compresores semistáticos densos End-Tagged Dense Code
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
Tagged Dense Code• (s,c)-
Dense Code• Resultados Teóricos• Resultados Empíricos
Motivación
Compresión Huffman semiestática
Compresión semistática orientada a palabras Guió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
Compresores semistáticos densos (s,c)-Dense Code
20 15 12 11 8 8 3 3 2 1 1
20 35 47 58 … … … 1000Num occs
Frec. acum
* k ;
Antonio Fariña
Compresores semistáticos densos (s,c)-Dense Code
—
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
Compresores semistáticos densos (s,c)-Dense Code
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
Compresores semistáticos densos (s,c)-Dense Code
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
Compresores semistáticos densos (s,c)-Dense Code
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
Compresores semistáticos densos (s,c)-Dense Code
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
Tagged Dense Code• (s,c)-
Dense Code• Resultados Teóricos• Resultados Empíricos
Compresores semiestáticos densos
Motivación
Compresión Huffman semiestática
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
Compresores semiestáticos densos Acotación analítica de Huffman
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
Compresores semiestáticos densos Acotación analítica de Huffman
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
Compresores semiestáticos densos Acotación analítica de Huffman
Cota Inferior
Análogamente:
Tomando
Puesto que : nuestra cota superior, viene dada por:
Antonio Fariña
• End
Tagged Dense Code• (s,c)-
Dense Code• Resultados Teóricos• Resultados Empíricos
Compresores semiestáticos densos
Motivación
Compresión Huffman semiestática
Compresión semistática orientada a palabras Guió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.)
PH (s ,c )-DC ETDC TH
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.)
PH (s ,c )-DC ETDC TH
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
Compresores semistáticos densos Resultados Empíricos : Resumen
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)