Principio del algoritmo de compresión

La codificación Huffman es el mejor método de compresión sin pérdidas. Reemplaza cada símbolo con una descripción prebinaria, cuya longitud está determinada por la frecuencia de aparición del símbolo especial. Los símbolos de uso frecuente requieren pocos bits para representarse y los símbolos poco comunes requieren muchas acciones para representarse.

El algoritmo de Huffman es el mejor para cambiar la codificación binaria de cualquier símbolo, lo que da como resultado una pequeña cantidad de expresiones densas. Sin embargo, no maneja ordenar y repetir secuencias de símbolos o números de secuencia.

2.1 Principio

No voy a entrar en todos los detalles prácticos de la codificación Huffman, pero el principio básico es encontrar una nueva representación binaria para cada símbolo, de modo que normalmente el Los símbolos rara vez usan bits, los símbolos que se usan con menos frecuencia usan más bits.

En resumen, la forma de resolver este problema es encontrar la universalidad de cada símbolo. Construimos un histograma de los datos sin comprimir; creamos un árbol binario dividiendo recursivamente este histograma en dos partes, la mitad de. cada recursión debe tener el mismo peso que la otra mitad (el peso es ∑ N K =1 número de símbolos K, donde N es el número de símbolos en la partición y el número de símbolos K es el número de apariciones del símbolo K).

Este árbol tiene dos propósitos:

1. El codificador utiliza este árbol para encontrar la mejor representación de cada símbolo.

2. El decodificador utiliza este árbol para identificar de forma única el principio y el final de cada código en el flujo comprimido. Al atravesar el árbol de arriba a abajo mientras lee los bits de datos comprimidos, selecciona una rama basada en cada bit individual del flujo de datos. Una vez que se alcanza el nodo hoja, el decodificador sabe que se ha leído el código completo.

El flujo de datos comprimidos es de 24 bits (tres bytes), no de 80 bits (10 bytes). Por supuesto, debo almacenar el árbol de Huffman para que el decodificador pueda decodificar el flujo comprimido correspondiente, lo que hace que el flujo de datos real en este caso sea más grande que los datos del flujo de entrada. Este es un efecto secundario de que los datos sean relativamente cortos. Para grandes cantidades de datos, el árbol de Huffman anterior no ocupa mucho.

Al decodificar, el árbol se recorre de arriba a abajo y se selecciona la rama izquierda/derecha para la secuencia comprimida. Cada vez que se encuentra un nodo hoja, los bytes correspondientes se pueden escribir en el flujo de salida descomprimido y luego recorrerlos desde la raíz.

2.2 Implementación

El codificador Huffman se puede encontrar en la biblioteca de compresión básica y es una implementación muy sencilla.

Los defectos básicos de esta implementación son:

1. Implementación de flujo de bits lento

2 Decodificación bastante lenta (más lenta que la codificación)

3. La profundidad máxima del árbol es 32 (el codificador sale en cualquier momento cuando supera los 32 bits). Si leo correctamente, esto no es posible a menos que los datos de salida tengan más de 2^32 bytes.

Por otro lado, esta implementación tiene varias ventajas:

1. Los árboles de Huffman se almacenan en una forma compacta, lo que requiere 12 bits por símbolo (para símbolos de 8 bits), lo que significa que el encabezado más grande es 384.

2. La codificación es fácil de entender

La codificación de Huffman es muy buena cuando los datos son ruidosos (no regulares, como RLE), en cuyo caso la mayoría se basa en diccionarios. Es un problema con el codificador del patrón.