Le codage de Huffman est un algorithme de compression de données sans perte utilisant un arbre binaire et un code à longueur variable basé sur des probabilités d'apparition.
Le programme est limité aux caractères alphabétiques, il utilise un algorithme semi-adaptatif : il calcule la fréquence d'apparition des lettres et propose la solution optimale.
Le dictionnaire proposé est un exemple, il optimise les lettres les plus fréquentes de la langue française : E, A, R, S, T, L, N...
Le programme calcule la fréquence d'apparition des lettres. Exemple : DCODEMOI, 2*D, 2*O, 1*C, 1*E, 1*M, 1*I.
On créé un arbre ayant pour feuilles les lettres et leur poids (leur nombre d'occurrence).
Pour ce faire on associe à chaque couple composé des deux noeuds de plus faibles poids pour créer un nouveau noeud, de poids de leur somme des poids jusqu'à arriver à la racine.
On convient de la notation : 0 pour la branche gauche et 1 pour la branche droite.
Le code binaire de chaque caractère est alors obtenu en parcourant la racine jusqu'à la feuille et en notant le parcours (0 ou 1) à chaque noeud.
DCODEMOI entraine la création d'un arbre tel que le D et le O, présent le plus souvent auront un code court. D = 00, O = 01, I = 111, M = 110, E = 101, C = 100. soit 0010001101110111 (16 bits).
Il suffit de parcourir le code obtenu avec l'arbre jusqu'à obtenir une feuille existante. Soit : 0010001101110111, on recherche 0 (n'existe pas), puis 00 (D), puis 1 (n'existe pas), puis 10 (n'existe pas), puis 100 (C), etc.
dCode ne propose pas encore la création d'un arbre automatiquement, mais le site Huffman Tree Generator peut vous y aider ici
© 2012 dcode.fr — Le site indispensable pour résoudre les énigmes, les jeux et les chasses au trésor. dCode