Complejidad Temporal
Mejor: O(n log n)
Prom: O(n log n)
Peor: O(n log n)
La Codificación de Huffman es un algoritmo voraz para compresión de datos sin pérdida. Asigna códigos binarios más cortos a los caracteres frecuentes y más largos a los raros, reduciendo la cantidad total de bits necesarios para representar los datos.
Cómo funciona:
1. Contar cuántas veces aparece cada carácter
2. Crear un nodo hoja por carácter y ponerlos en una cola de prioridad mínima
3. Quitar repetidamente los dos nodos de menor frecuencia y fusionarlos bajo un nuevo padre cuya frecuencia sea la suma
4. Cuando quede un solo nodo, usarlo como raíz del árbol
5. Asignar códigos recorriendo el árbol: izquierda = 0, derecha = 1
Por qué funciona:
Ningún código es prefijo de otro, así que el flujo de bits codificado se decodifica sin ambigüedad. La fusión voraz garantiza un código de prefijo óptimo para las frecuencias dadas.
Complejidad Temporal:
Mejor: O(n log n)
Promedio: O(n log n)
Peor: O(n log n)
Complejidad Espacial: O(n)
Propiedades:
- Sin pérdida: los datos originales se recuperan exactamente
- Óptimo entre los códigos de prefijo para una distribución de frecuencias conocida
- Usado en DEFLATE (ZIP, gzip, PNG), JPEG y MP3
Inventado por David A. Huffman en 1952 cuando era estudiante en el MIT, sigue siendo un pilar de la compresión moderna.
Algoritmos relacionados
Preguntas frecuentes
- ¿Qué es Codificación de Huffman?
- La Codificación de Huffman es un algoritmo voraz para compresión de datos sin pérdida. Asigna códigos binarios más cortos a los caracteres frecuentes y más largos a los raros, reduciendo la cantidad total de bits necesarios para representar los datos.
- ¿Cuál es la complejidad de Codificación de Huffman?
- Tiempo (promedio): O(n log n) · Espacio: O(n)
- ¿Para quién es este visualizador de Codificación de Huffman?
- La visualización de Codificación de Huffman está pensada para nivel avanzado, dentro de la categoría Compresión. Ideal para estudiantes, entrevistas técnicas y repaso práctico.
- ¿Qué algoritmos relacionados hay con Codificación de Huffman?
- En la misma categoría (Compresión) puedes explorar: Run-Length Encoding, LZ77, LZW. Todos tienen visualización interactiva.