La codificación de Huffman es un algoritmo de compresión de datos sin pérdidas. La idea es asignar códigos de longitud variable para ingresar caracteres, las longitudes de los códigos asignados se basan en las frecuencias de los caracteres correspondientes.
El carácter más frecuente obtiene el código más pequeño y el carácter menos frecuente obtiene el código más grande.
Los códigos de longitud variable asignados a los caracteres de entrada son códigos de prefijo, significa que los códigos (secuencias de bits) se asignan de tal manera que el código asignado a un carácter no es el prefijo del código asignado a ningún otro carácter. Así es como Huffman Coding se asegura de que no haya ambigüedad al decodificar el flujo de bits generado.
Comprendamos los códigos de prefijo con un ejemplo de contador. Supongamos que hay cuatro caracteres a, b, cyd, y sus códigos de longitud variable correspondientes son 00, 01, 0 y 1. Esta codificación conduce a la ambigüedad porque el código asignado a c es el prefijo de los códigos asignados a a y b. Si el flujo de bits comprimido es 0001, la salida descomprimida puede ser “cccd” o “ccb” o “acd” o “ab”.
Hay principalmente dos partes principales en Huffman Coding
1) Construye un árbol Huffman a partir de los caracteres de entrada.
2) Atraviesa el Árbol Huffman y asigna códigos a los personajes.
- ¿Qué es mejor en C #, mantener una variable con un tamaño de matriz o llamar a la longitud de la matriz?
- Dados n puntos en un plano 2D, ¿cómo encontrarías el número máximo de puntos que se encuentran en la misma línea recta? Proporcione un algoritmo para resolver este problema.
- ¿Qué tan bien funciona el algoritmo NativeTrack de AppsFlyer?
- Cómo aprender estructuras de datos usando C ++ de manera simple
- ¿Qué significa Yoshua Bengio que la principal limitación de los algoritmos de aprendizaje automático actuales es que necesitan demasiados datos para aprender?
Pasos para construir Huffman Tree
La entrada es una matriz de caracteres únicos junto con su frecuencia de ocurrencias y la salida es Huffman Tree.
1. Cree un nodo hoja para cada carácter único y cree un montón mínimo de todos los nodos hoja (El montón mínimo se usa como una cola de prioridad. El valor del campo de frecuencia se usa para comparar dos nodos en el montón mínimo. Inicialmente, el carácter menos frecuente está en la raíz)
2. Extraiga dos nodos con la frecuencia mínima del montón mínimo.
3. Cree un nuevo nodo interno con una frecuencia igual a la suma de las frecuencias de los dos nodos. Haga el primer nodo extraído como su hijo izquierdo y el otro nodo extraído como su hijo derecho. Agregue este nodo al montón mínimo.
4. Repita los pasos 2 y 3 hasta que el montón contenga solo un nodo. El nodo restante es el nodo raíz y el árbol está completo.
Código fuente con ejemplo en: Algoritmos codiciosos | Set 3 (Codificación Huffman) – GeeksforGeeks
Espero que ayude 🙂
