Acerca de este experimento
Todos los archivos ZIP, las imágenes PNG y las pistas MP3 ocupan menos que los datos sin procesar porque eliminan las repeticiones. Prueba dos métodos clásicos sin pérdida con tu propio mensaje. La codificación por longitud de secuencia sustituye una secuencia de símbolos idénticos por un recuento; es excelente para imágenes sencillas e inútil para el texto habitual. La codificación de Huffman asigna códigos cortos a los símbolos frecuentes y códigos largos a los poco frecuentes. Los códigos se construyen paso a paso a partir de un árbol, y el resultado queda a menos de un bit por símbolo del límite teórico que Claude Shannon descubrió en 1948.
Objetivos de aprendizaje
- Explica la diferencia entre la compresión sin pérdida y la compresión con pérdida
- Codifica y decodifica un mensaje mediante codificación por longitud de secuencia y explica cuándo resulta útil
- Construye un árbol de Huffman uniendo repetidamente los dos símbolos menos frecuentes
- Lee las palabras de código del árbol y explica por qué ningún código es el comienzo de otro
- Compara los tamaños comprimidos con el límite de entropía y calcula una tasa de compresión
Cómo usarlo
- 1Elige la fila de píxeles y la codificación por longitud de secuencia. ¿Cuántos bits necesita la fila antes y después? ¿Por qué funciona tan bien?
- 2Cambia a Hamlet con la codificación por longitud de secuencia. ¿Por qué aumenta el tamaño del mensaje?
- 3Elige Mississippi y pulsa «Crear el árbol». ¿Qué dos árboles se unen en cada paso y por qué?
- 4Cuando el árbol esté terminado, encuentra la palabra de código de la letra más común y la de la más rara. Cuenta los bits.
- 5Decodifica a mano los primeros bits del mensaje codificado, recorriendo el árbol desde la raíz.
- 6Escribe un mensaje que use una sola letra y luego otro en el que todas las letras sean distintas. Compara Huffman con el límite de entropía en ambos casos.
El modelo
Supuestos
- El mensaje original usa 8 bits por carácter, como en ASCII.
- Cada par de longitud de racha se almacena como un contador de 8 bits y un carácter de 8 bits, por lo que las rachas de más de 255 se dividen.
- El tamaño de Huffman cuenta solo el mensaje codificado. Un archivo real también debe almacenar la tabla de códigos o las frecuencias, lo cual importa en los mensajes cortos.
- Cuando dos árboles tienen el mismo peso, se elige primero el que se creó antes, y el árbol de menor peso pasa a ser la rama 0. Otras reglas para resolver empates producen códigos distintos de la misma longitud total.
Pruébalo en clase
- Q1Codifica BBBBBWWWBBBBBBBB con codificación por longitud de racha. ¿Cuántos bytes necesita?
- Q2Construye el árbol de Huffman para las frecuencias A 5, B 2, R 2, C 1, D 1 y calcula el número total de bits para ABRACADABRA.
- Q3¿Por qué un código de Huffman debe ser un código prefijo? ¿Qué saldría mal si A fuera 0 y B fuera 01?
- Q4Un texto usa 8 letras diferentes con la misma frecuencia. ¿Cuál es su entropía y puede Huffman comprimirlo?
- Q5JPEG y MP3 comprimen mucho más que la codificación de Huffman. ¿A qué renuncian para lograrlo?
Preguntas frecuentes
¿Dónde se usa hoy la codificación de Huffman?
En muchos formatos habituales: ZIP y gzip (el método DEFLATE), imágenes PNG, imágenes JPEG después de la etapa con pérdida y audio MP3. Normalmente es la última etapa, después de que otro método haya convertido las repeticiones en números.
¿Se puede comprimir cualquier archivo?
No. Un método sin pérdida que redujera el tamaño de todos los archivos permitiría comprimir el resultado una y otra vez, lo cual es imposible porque hay menos archivos cortos que largos. Los datos aleatorios y los archivos ya comprimidos normalmente no se hacen más pequeños.
¿Es único el árbol de Huffman?
No siempre. Cuando las frecuencias están empatadas, distintas elecciones producen árboles y palabras de código diferentes, pero todos los árboles de Huffman para las mismas frecuencias dan el mismo número total de bits.