Un codificador de diccionario , también conocido como codificador de sustitución , es una clase de algoritmos de compresión de datos sin pérdida que operan 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 tal coincidencia, sustituye una referencia a la posición de la cadena en la estructura de datos.
Algunos codificadores de diccionario utilizan un 'diccionario estático', uno 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 mayor frecuencia cuando el mensaje o conjunto de mensajes que se codificarán es fijo y grande; 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 usa ese diccionario para comprimir los versos. Este esquema de utilizar 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 construye un diccionario a partir de la redundancia extraída de un entorno de datos (varios flujos de entrada), diccionario que luego se usa estáticamente para comprimir un flujo de entrada adicional. Por ejemplo, un diccionario se construye a partir de textos antiguos en inglés y luego se usa para comprimir un libro. [2]
Más comunes son los métodos 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 sirve como diccionario, almacenando efectivamente cada subcadena que ha aparecido en los últimos N bytes como entradas de diccionario. En lugar de un solo í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 ), lo que indica que la coincidencia se encuentra en la ventana deslizante que comienza con los bytes de compensación antes del texto actual.
LZ78 usa 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, el último índice (o cero) y el carácter coincidentes 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 de coincidencia y no se emite nada.
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 hexadecimal 00 a hexadecimal FF (decimal 255) están predefinidos. Las entradas del diccionario se agregarían comenzando con el valor de código hexadecimal 100. A diferencia de LZ78, si no se encuentra una coincidencia (o si el final de los datos), solo se emite 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 a LZW incluyen la manipulación de tamaños de símbolo distintos de 8 bits y tener códigos reservados para restablecer el diccionario e indicar el final de los datos.