Codificación Huffman (algoritmo codicioso)

Referencia: codificación Huffman

La codificación Huffman es un método de codificación muy eficaz, ampliamente utilizado en la compresión de datos

Mediante el uso desigual El método de codificación larga selecciona codificaciones de diferentes longitudes según diferentes frecuencias de caracteres. Para caracteres con frecuencias más altas, se utilizan codificaciones más cortas para lograr un alto grado de compresión de datos.

Este método de codificar caracteres con frecuencias más altas utilizando códigos más cortos aplica la idea de un algoritmo codicioso.

Veamos un ejemplo:

Si tenemos un archivo que contiene 1000 caracteres, cada carácter ocupa 1 byte (1byte=8bits), entonces almacenamos estos 100 caracteres ***Requiere. 8000 bits. Todavía hay algunos grandes

Contemos el número total de caracteres en estos 1000 caracteres. Resulta que se necesitan 8 bits para representar un carácter. Si se usan menos bits para representar estos caracteres, es posible. reducir el espacio de almacenamiento.

Supongamos que hay 6 tipos de caracteres a, b, c, d, e, f en estos 1000 caracteres. Si se utilizan 3 bits binarios para representarlos, solo se almacenarán estos 1000 caracteres. Requiere 3000 bits, lo que ahorra espacio de almacenamiento que antes.

Quizás también puedas comprimirlo más:

Proporciona a los caracteres códigos de longitud desigual según la frecuencia de aparición. Cuanto mayor sea la frecuencia, más corto será el código. cuanto más corto sea el código, más largo.

No puede leer directamente bits binarios de una longitud fija y traducirlos a caracteres como la codificación de igual longitud. Para leer con precisión los caracteres traducidos, requiere que la codificación de un carácter no pueda ser el prefijo de. otro personaje.

Suponiendo que la frecuencia de aparición de los seis caracteres a, b, c, d, e y f disminuye en orden, podemos darles tal codificación

Si la frecuencia de aparición de los caracteres Como se muestra en la figura, según esta codificación, el número total de bits es 2100 bits, lo que ahorra más espacio.

Estrategia codiciosa: los caracteres con poca frecuencia se colocan primero en la cola.

Pasos:

1. Trate cada carácter como un nodo, use la frecuencia de aparición como peso y colóquelos en una cola de prioridad (un montón mínimo

2. Quite de la cola dos nodos cada vez y cree un nodo padre cuyo peso sea la suma de los pesos de los nodos que acaban de sacar de la cola y sea el nodo padre de los dos nodos (fusión). Luego agregue este árbol a la cola.

3. Repita la operación 2 hasta que solo haya un elemento en la cola (este elemento debe estar representado como un árbol en este momento) y se complete la creación.

Después de crear el árbol, ¿cómo codificarlo?

Para un árbol de Huffman, todos los nodos que comienzan desde el nodo principal están marcados con 0 a la izquierda y 1 a la derecha. Luego se puede encontrar el código secuencial para llegar al nodo hoja.

C: Juego de caracteres

Q: Cola de prioridad

EXTRACT-MIN: Pasar una cola y eliminar el elemento más pequeño de la cola

INSERTAR: Insertar z en Q

Cuando finaliza el ciclo for, solo hay un elemento en la cola, que es el árbol de Huffman que necesitamos. Finalmente, devuelve este árbol.

Suponga que el árbol T ya es un árbol óptimo. Suponga que las frecuencias de xey son menores o iguales que las a y b más bajas, y luego intercambie x, a, y y b.

Calcular si el coste ha cambiado.

Por ejemplo, aquí comparamos si el costo cambia después de que T cambia a T ’, y encontramos que el costo se vuelve menor o no cambia.

De la misma manera, T' a T'', y debido a que originalmente se asumió que T es óptimo, solo pueden ser iguales.

Por lo tanto, T'' también debe cumplir con el condiciones, es decir, el algoritmo codicioso, es correcto tomar los dos nodos más pequeños cada vez