¿Cómo funciona la codificación adaptativa de Huffman?

La codificación de Huffman es un método ampliamente utilizado de codificación de entropía utilizado para la compresión de datos. Se supone que tenemos un conocimiento completo de las estadísticas de una señal. Sin embargo, hay versiones de la codificación de Huffman que se utilizan con medios de transmisión y no pueden saber todo sobre las estadísticas de la señal. ¿Cómo funcionan estos codificadores adaptativos de Huffman ?

El artículo de Wikipedia tiene una descripción bastante buena del proceso de codificación adaptativo de Huffman utilizando una de las implementaciones notables, el algoritmo Vitter. Como notó, un codificador estándar de Huffman tiene acceso a la función de masa de probabilidad de su secuencia de entrada, que utiliza para construir codificaciones eficientes para los valores de símbolo más probables. En el ejemplo prototípico de compresión de datos basada en archivos, por ejemplo, esta distribución de probabilidad se puede calcular histogramando la secuencia de entrada, contando el número de ocurrencias de cada valor de símbolo (los símbolos podrían ser secuencias de 1 byte, por ejemplo). Este histograma se usa para generar un árbol Huffman, como este (tomado del artículo de Wikipedia):

El árbol se organiza disminuyendo el peso o la probabilidad de ocurrencia en la secuencia de entrada; los nodos de hoja en la parte superior representan los símbolos más probables, que por lo tanto reciben las representaciones más cortas en el flujo de datos comprimido. El árbol se guarda junto con los datos comprimidos y posteriormente el descompresor lo utiliza para regenerar la secuencia de entrada (sin comprimir) nuevamente. Como una de las primeras implementaciones de código de entropía, la codificación estándar de Huffman es bastante sencilla.

La estructura del codificador adaptativo de Huffman es bastante similar; utiliza una representación similar basada en un árbol de las estadísticas de la secuencia de entrada para seleccionar codificaciones eficientes para cada valor de símbolo de entrada. La principal diferencia es que, como implementación de transmisión del algoritmo, no se dispone de un conocimiento a priori de la función de masa de probabilidad de la entrada; Las estadísticas de la secuencia deben estimarse sobre la marcha. Si se va a utilizar el mismo esquema de codificación de Huffman, esto significa que el árbol utilizado para generar la codificación de cada símbolo en la secuencia comprimida debe construirse y mantenerse dinámicamente a medida que se procesa la secuencia de entrada.

El algoritmo de Vitter es una forma de lograr esto; A medida que se procesa cada símbolo de entrada, el árbol se actualiza, manteniendo su característica de disminución de la probabilidad de aparición del símbolo a medida que avanza hacia abajo. El algoritmo define un conjunto de reglas sobre cómo se actualiza el árbol a lo largo del tiempo y cómo se codifican los datos comprimidos resultantes en la secuencia de salida. A medida que se consume la secuencia de entrada, la estructura del árbol debe representar una descripción cada vez más precisa de la distribución de probabilidad de la entrada. A diferencia del enfoque de codificación estándar de Huffman, el descompresor no tiene un árbol estático para usar para la decodificación; debe realizar las mismas funciones de mantenimiento de árbol continuamente durante el proceso de descompresión.

En resumen : el codificador adaptativo de Huffman funciona de manera muy similar al algoritmo estándar; sin embargo, en lugar de una medición estática de las estadísticas de la secuencia de entrada completa (el árbol de Huffman), se utiliza una estimación dinámica, acumulativa (es decir, desde el primer símbolo hasta el símbolo actual) de la distribución de probabilidad de la secuencia para codificar (y decodificar) cada símbolo . A diferencia del enfoque de codificación estándar de Huffman, el algoritmo adaptativo de Huffman requiere este análisis estadístico tanto en el codificador como en el decodificador.