| Símbolo | Apariciones | Código | Bits | Bits en total |
|---|
Constructor de códigos de Huffman
¿Por qué una letra común como la e debería ocupar tantos bits como una rara como la k? La codificación de Huffman da códigos cortos a los símbolos frecuentes y códigos largos a los raros, y lo hace de la mejor manera posible. Escribe un texto o elige un ejemplo y construye su árbol de Huffman paso a paso: los dos árboles más ligeros se unen bajo un nuevo nodo, una y otra vez, hasta que queda un solo árbol. Entonces cada camino desde la cima forma un código, y puedes seguir cada símbolo a través de los bits codificados. Escribe un texto o elige un ejemplo. Cada símbolo empieza como una hoja con su número de apariciones. Avanza por la construcción paso a paso: cada paso une los dos árboles más ligeros bajo un nuevo nodo con su suma, hasta que queda un solo árbol. Entonces el camino desde la cima hasta una hoja da su código, 0 para la izquierda y 1 para la derecha. Haz clic en una hoja, una fila o un trozo de los bits para seguir un símbolo, y compara el total con un código de longitud fija y con la entropía.
Cómo funciona
- Escribe o pega un texto, o elige un ejemplo como ABRACADABRA o MISSISSIPPI RIVER.
- Avanza por la construcción con Siguiente paso, o pulsa Reproducir: cada paso une los dos árboles más ligeros bajo un nodo con su suma.
- Cuando el árbol esté completo, haz clic en una hoja, una fila de la tabla o un trozo de los bits para seguir un símbolo, y compara los totales de los recuadros.
Cómo se construye el árbol
Cuenta cuántas veces aparece cada símbolo y convierte cada uno en un árbol de una sola hoja, con su número de apariciones como peso. Después repite un único paso sencillo: toma los dos árboles de menor peso y cuélgalos bajo un nuevo nodo cuyo peso es su suma. Cada paso deja un árbol menos, así que tras n − 1 pasos para n símbolos queda un solo árbol. Los símbolos raros se unieron primero y quedan en lo más profundo; los comunes se unieron tarde y quedan cerca de la cima.
Leer los códigos
Baja desde la cima: un paso a la izquierda añade un 0, un paso a la derecha, un 1. El camino hasta una hoja es el código de ese símbolo. Como los símbolos solo están en las hojas, ningún código es el comienzo de otro, así que una cadena de bits se puede decodificar sin ningún separador: sigue los bits árbol abajo y, cada vez que llegues a una hoja, escribe su símbolo y vuelve a empezar desde la cima. Para ABRACADABRA, Huffman necesita 23 bits, frente a 33 de un código fijo de 3 bits por letra.
Preguntas frecuentes
¿Por qué el código de Huffman es el mejor posible?
Entre todos los códigos que dan a cada símbolo su propia cadena de bits enteros, ninguno tiene un total más corto para las apariciones dadas. La demostración sigue la construcción: en un código óptimo, los dos símbolos más raros siempre pueden convertirse en hermanos en el nivel más profundo, y unirlos deja un problema más pequeño del mismo tipo. El número total de bits es igual a la suma de los pesos de todos los nodos internos del árbol.
¿Qué es un código prefijo?
Un código en el que ninguna palabra de código es el comienzo de otra, como 0, 10, 110 y 111. Esa propiedad permite a un decodificador leer un flujo de bits sin separadores, porque siempre sabe dónde termina una palabra de código. Todo código de Huffman es un código prefijo: los símbolos solo están en las hojas del árbol.
¿Es único el árbol de Huffman?
No del todo: cuando dos árboles tienen el mismo peso, se puede tomar primero cualquiera de los dos, y la izquierda y la derecha se pueden intercambiar. Elecciones distintas dan códigos distintos, pero siempre el mismo número total de bits. El constructor siempre deshace los empates de la misma manera, así que un texto siempre da el mismo árbol.
¿Cuánto se acerca Huffman a la entropía?
La longitud media de los códigos es como mínimo la entropía y la supera en menos de un bit. Es igual a la entropía cuando cada probabilidad es una potencia de un medio, como en el ejemplo de las mitades sucesivas. La codificación aritmética y los codificadores de rango modernos evitan el límite de los bits enteros y se acercan todavía más.
¿Se envía mi texto a algún sitio?
No. El árbol y los códigos se calculan en tu navegador, y tu texto se queda en el almacenamiento local de este navegador.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Ir al editor