Codificación por diccionario

La codificación por diccionario es una clase de compresión sin pérdida que busca coincidencias entre el texto a comprimir y un grupo de cadenas de caracteres en una estructura denominada diccionario administrada por el algoritmo codificador. Cuando este algoritmo encuentra una coincidencia sustituye la referencia a la posición de la cadena en la estructura de datos.

Métodos y aplicaciones

Algunos codificadores usan un 'diccionario estático', el cual no es modificado durante el proceso de codificación, sino que se mantiene desde antes de empezar el proceso, se suele utilizar cuando el mensaje a codificar es grande pero fijo como por ejemplo una aplicación para celulares que almacena el contenido de un libro en un espacio de almacenamiento reducido.

En los métodos más comunes el diccionario comienza con un estado predeterminado pero el contenido cambia durante el proceso de codificación teniendo en cuenta los datos que ya han sido codificados. Los algoritmos LZ77 y LZ78 usan este principio.

En el LZ77, hay un ''buffer' circular llamado ventana deslizante (sliding window) que contiene los últimos bytes procesados. Esta ventana sirve como diccionario pues almacena cada subcadena, que aparece en esos últimos bytes como entradas de diccionario, en vez de usar simples índices, para esto requiere de dos valores: el desplazamiento y el largo, el desplazamiento es la distancia a la que se encuentra el inicio de la cadena desde el texto actual y el largo indica la cantidad de caracteres que contiene esa cadena.

Ejemplo

El texto a comprimir empieza con "MANGOTANGO". En los primeros seis pasos de codificación, se recorre M, A, N, G, O, T, y se agregan entradas para MA, AN, NG, GO, OT, TA. En el séptimo paso, empezamos con "ANGO", la entrada más grande que tenemos es "AN". Entonces enviamos el índice para "AN", y agregamos en el diccionario una entrada para "ANG". En el octavo paso, enviamos el índice para "GO", y suponemos que un espacio sigue a MANGOTANGO, así que agregamos una entrada para "GO " en el diccionario. Si después en el texto encontramos otra vez la palabra "MANGOTANGO", podríamos codificarla como esta vez (asumiendo que empezó en la M) en solo 5 índices: MA, NG, OT, ANG, O.

Codificando MANGOTANGO
M	M
A	MA
N	AN
G	NG
O	GO
T	OT
A	TA
N	-- (AN ya está en el diccionario)
G	ANG
O	NGO (no interesa)

Referencias

• Datos: Q646363