Codificador de diccionario

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 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. Este enfoque se utiliza con mayor frecuencia cuando el mensaje o conjunto de mensajes a codificar es fijo y extenso; 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 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), el cual se utiliza posteriormente de forma estática para comprimir otro flujo de entrada. Por ejemplo, se construye un diccionario a partir de textos antiguos en inglés y luego se utiliza para comprimir un libro. ^{[ 2 ]}

Más comunes son los métodos en los que el diccionario comienza en un estado predeterminado, pero su contenido cambia durante el proceso de codificación, según los datos ya codificados. Tanto el algoritmo LZ77 como el LZ78 funcionan con este principio. En LZ77, un búfer circular llamado "ventana deslizante" almacena los últimos N bytes de datos procesados. Esta ventana actúa como diccionario, almacenando efectivamente cada subcadena que ha aparecido en los N bytes anteriores como entradas del diccionario. En lugar de un único índice que identifique una entrada del 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 en el desplazamiento bytes anterior al texto actual.

LZ78 utiliza una estructura de diccionario más explícita; al inicio del proceso de codificación, el diccionario está vacío. Se utiliza un í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 coincidencia, el último índice coincidente (o cero) y el carácter se añaden al diccionario y se envían al flujo comprimido. Si hay coincidencia, el índice de trabajo se actualiza al índice coincidente y no se envía nada.

LZW es similar a LZ78, pero el diccionario se inicializa con todos los símbolos posibles. La implementación típica trabaja 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 de código hexadecimal 100. A diferencia de LZ78, si no se encuentra una coincidencia (o si se llega al final de los datos), solo se muestra 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 la documentación de LZW para obtener más información sobre cómo se maneja esto. Las mejoras de LZW incluyen el manejo de tamaños de símbolo distintos de 8 bits y la reserva de códigos para reiniciar el diccionario e indicar el final de los datos.

Brotli es un ejemplo de un codificador de uso común que se inicializa con un diccionario predefinido, pero que posteriormente utiliza un modelado de contenido más sofisticado. El diccionario de Brotli se compone principalmente de palabras en lenguaje natural y fragmentos de HTML y JavaScript, basados ​​en un análisis del tráfico web. ^{[ 3 ]}

• Código basado en gramática
• Codificación de entropía