Math
Código de Huffman
Una cola ordenada de frecuencias se convierte en un árbol de códigos prefijo. Selecciona un símbolo para seguir sus bits y cada unión.
Qué ocurre
Cada paso une los dos pesos menores. Las ramas 0 y 1 forman el código desde la raíz hasta el símbolo. Seleccionar una letra resalta ese camino. L es la longitud media del código y H la entropía. Huffman minimiza L entre los códigos prefijo binarios de símbolos individuales, incluso si L > H. Hay igualdad para probabilidades 2^(-k). El número de bits no incluye la tabla de códigos ni las cabeceras.
Ecuaciones del módulo
Ecuaciones construcción: se fusionan los dos nodos más ligeros, n−1 veces; el código de un símbolo es su camino desde la raíz, izquierda 0, derecha 1 L = Σ p(i)·l(i) (bits por símbolo); H = −Σ p(i)·log₂ p(i); la longitud del código l(i) es la profundidad de la hoja Kraft: todo código prefijo cumple Σ 2^(−l(i)) ≤ 1, y todo vector así es un árbol; el árbol de Huffman es completo, así que la suma es exactamente 1 H ≤ L < H + 1 siempre; L = H exactamente cuando todo p(i) es una potencia de dos la optimalidad se comprueba frente a una búsqueda sobre TODOS los vectores de longitudes admisibles según Kraft - la búsqueda no sabe nada del algoritmo frecuencias iguales: 2(n − 2^k) símbolos reciben el código largo, donde 2^k es la mayor potencia de dos por debajo de n las frecuencias de Fibonacci 1, 1, 2, 3, 5, … dan el árbol más desequilibrado: longitudes n−1, n−1, n−2, …, 1
