Un codificador de diccionario , también conocido a veces como codificador de sustitución , es una clase de algoritmos de compresión de datos sin pérdida que funcionan buscando coincidencias entre el texto que se va a comprimir y un conjunto de cadenas contenidas en una estructura de datos (llamada "diccionario") mantenida por el codificador. Cuando el codificador encuentra dicha coincidencia, sustituye una referencia a la posición de la cadena en la estructura de datos.
Algunos codificadores de diccionarios utilizan un "diccionario estático", cuyo conjunto completo de cadenas se determina antes de que comience la codificación y no cambia durante el proceso de codificación. Este enfoque se utiliza con más frecuencia cuando el mensaje o el conjunto de mensajes que se van a codificar son fijos y grandes; por ejemplo, una aplicación que almacena el contenido de un libro en el espacio de almacenamiento limitado de una PDA generalmente crea un diccionario estático a partir de una concordancia del texto y luego utiliza ese diccionario para comprimir los versículos. Este esquema de uso de la codificación de Huffman para representar índices en una concordancia se ha denominado "Huffword". [1]
En un método relacionado y más general, se crea un diccionario a partir de redundancia extraída de un entorno de datos (varios flujos de entrada) y luego se utiliza estáticamente para comprimir un flujo de entrada adicional. Por ejemplo, se crea un diccionario a partir de textos antiguos en inglés y luego se utiliza para comprimir un libro. [2]
Los métodos más comunes son aquellos en los que el diccionario comienza en un estado predeterminado pero el contenido cambia durante el proceso de codificación, en función de los datos que ya se han codificado. Tanto el algoritmo LZ77 como el LZ78 funcionan según este principio. En LZ77, un búfer circular llamado "ventana deslizante" contiene los últimos N bytes de datos procesados. Esta ventana funciona como diccionario, almacenando efectivamente cada subcadena que ha aparecido en los últimos N bytes como entradas de diccionario. En lugar de un único índice que identifique una entrada de diccionario, se necesitan dos valores: la longitud , que indica la longitud del texto coincidente, y el desplazamiento (también llamado distancia ), que indica que la coincidencia se encuentra en la ventana deslizante, comenzando con un desplazamiento bytes antes del texto actual.
LZ78 utiliza una estructura de diccionario más explícita; al comienzo del proceso de codificación, el diccionario está vacío. Se utiliza un valor de índice de cero para representar el final de una cadena, por lo que el primer índice del diccionario es uno. En cada paso del proceso de codificación, si no hay ninguna coincidencia, entonces el último índice coincidente (o cero) y el último carácter se agregan al diccionario y se envían a la secuencia comprimida. Si hay una coincidencia, entonces el índice de trabajo se actualiza al índice coincidente y no se envía nada a la salida.
LZW es similar a LZ78, pero el diccionario se inicializa con todos los símbolos posibles. La implementación típica funciona con símbolos de 8 bits, por lo que los "códigos" del diccionario para los valores hexadecimales 00 a FF (decimal 255) están predefinidos. Las entradas del diccionario se agregarían comenzando con el valor del código hexadecimal 100. A diferencia de LZ78, si no se encuentra una coincidencia (o si se trata del final de los datos), solo se genera el código del diccionario. Esto crea un problema potencial ya que la salida del decodificador está un paso por detrás del diccionario. Consulte LZW para saber cómo se maneja esto. Las mejoras de LZW incluyen el manejo de tamaños de símbolos distintos de 8 bits y la reserva de códigos para restablecer el diccionario e indicar el final de los datos.