informatica

Cap´
ıtulo 4
T´cnicas de Diccionario
e
Cuando tratamos con textos de alg´n lenguaje de programaci´n, entre
u
o
otros ejemplos, determinados grupos de letras son muy frecuentes y, por el
contrario, otras combinaciones no se dan o son muy raras. Esta caracter´
ıstica
puede explotarse para conseguir una mayor compresi´n. Lo usual es elaborar
o
una lista o diccionario con lascombinaciones m´s frecuentes de letras del
a
alfabeto fuente y las palabras-c´digo correspondientes. Por lo general, las
o
palabras-c´digo ser´n de igual longitud.
o
a
El diccionario puede ser est´tico o din´mico. Cuando se tiene un buen
a
a
conocimiento a priori de la fuente en cuesti´n, se utiliza un diccionario eso
t´tico. Por ejemplo, si se desea comprimir los datos de los estudiantes de una
auniversidad, hay palabras como estudiante, nombre, cr´ditos, etc que ser´n
e
a
muy frecuentes. Por el contrario, si no se dispone de ese conocimiento previo,
tendremos que adquirirlo, de alg´n modo, en el momento de la codificaci´n.
u
o
Esta es la idea clave para la elaboraci´n de un diccionario din´mico.
o
a

4.1.

Diccionarios est´ticos
a

Una de las formas m´s comunes de crearun diccionario est´tico es la sigua
a
iente. El diccionario consta de todas las letras del alfabeto fuente junto con las
cadenas de 2 s´
ımbolos (llamadas digrams) m´s frecuentes, hasta completar
a
57

´
CAP´
ITULO 4. TECNICAS DE DICCIONARIO

58

el tama˜o escogido para ´ste. Por tanto, se precisa un conocimiento previo
n
e
acerca del tipo de datos. Si se trata, por ejemplo, detexto en castellano,
podemos analizar varias p´ginas al azar de alg´n libro para determinar las
a
u
frecuencias con que aparecen los distintos pares de s´
ımbolos, incluido el espacio, y escoger los pares m´s frecuentes para formar el diccionario junto con
a
los propios s´
ımbolos individuales. As´ si se desea elaborar un diccionario de
ı,
tama˜o 256 para codificar los 95 caracteresimprimibles ASCII, las primeras
n
95 entradas del diccionario ser´ los caracteres mencionados y las restantes
ıan
161 entradas ser´ las parejas m´s frecuentes. Cada entrada de nuestro dicıan
a
cionario se codifica con una cadena binaria de 8 bits.
El codificador lee el primer par de s´
ımbolos y trata de ver si est´ en
a
el diccionario. Si lo est´, codifica el par con la palabra-c´digo que lecorrea
o
sponde. Si, por el contrario, no lo est´, codifica el primer s´
a
ımbolo del par
con la palabra-c´digo correspondiente y pasa a considerar un nuevo par, que
o
estar´ formado por la segunda componente del par anterior y el siguiente
ıa
s´
ımbolo en el mensaje. Como todas las palabras-c´digo son de igual longitud
o
la decodificaci´n no ofrece problema alguno.
o

Ejemplo 4.1.1.Supongamos que S = {a, b, c, d, e} es el alfabeto fuente y que
sabemos que las parejas de s´
ımbolos m´s frecuentes son : ab, ac, ad. Podemos
a
elaborar un diccionario de tama˜o 8 como el que se indica a continuaci´n
n
o
Entrada
a
b
c
d
e
ab
ac
ad

Palabra-c´digo
o
000
001
010
011
100
101
110
111

´
CAP´
ITULO 4. TECNICAS DE DICCIONARIO

59

En el c´digo ASCII de 7bits el mensaje sin comprimir consta de 35 bits
o
y comprimido de esta forma, 9.

4.2.

Diccionarios din´micos
a

La mayor´ de las t´cnicas de compresi´n de datos que se basan en dicıa
e
o
cionarios din´micos tienen su ra´ en los trabajos de J. Ziv y A. Lempel,
a
ız
miembros del Departamento de Ingenier´ El´ctrica en Technion (Haifa). En
ıa e
1977 publicaron el art´
ıculo “Auniversal algorithm for sequential data compression”, en la revista IEEE Transactions on Information Theory, y un a˜o
n
despu´s en la misma revista el que lleva por t´
e
ıtulo “Compression of individual
sequences via variable-rate coding”. Estos trabajos proporcionan dos modos
diferentes de construir diccionarios din´micos y, de hecho, a partir de cada
a
una de ellas se han originado...