Math
Code de Huffman
Une file de fréquences triées devient un arbre de codes préfixes. Choisir un symbole pour suivre ses bits et chaque fusion.
Ce qui se passe
Chaque étape fusionne les deux poids minimaux. Les branches 0 et 1 donnent le code de la racine au symbole. Choisir une lettre met son chemin en évidence. L est la longueur moyenne du code et H son entropie. Huffman minimise L parmi les codes préfixes binaires de symboles individuels, même si L > H. Les probabilités 2^(-k) donnent une égalité. Le nombre de bits exclut la table de codes et les en-têtes.
Équations du module
Équations construction : fusionner les deux nœuds les plus légers, n−1 fois ; le code d'un symbole est son chemin depuis la racine, gauche 0, droite 1 L = Σ p(i)·l(i) (bits par symbole) ; H = −Σ p(i)·log₂ p(i) ; la longueur de code l(i) est la profondeur de la feuille Kraft : tout code préfixe vérifie Σ 2^(−l(i)) ≤ 1, et tout vecteur de ce genre est un arbre ; l'arbre de Huffman est plein, donc la somme vaut exactement 1 H ≤ L < H + 1 toujours ; L = H exactement quand chaque p(i) est une puissance de deux l'optimalité est vérifiée par une recherche sur TOUS les vecteurs de longueurs admissibles au sens de Kraft - la recherche ne sait rien de l'algorithme fréquences égales : 2(n − 2^k) symboles reçoivent le code long, où 2^k est la plus grande puissance de deux inférieure à n les fréquences de Fibonacci 1, 1, 2, 3, 5, … donnent l'arbre le plus déséquilibré : longueurs n−1, n−1, n−2, …, 1
