L’algorithme de Huffman et l’un des algorithmes les plus connus dans le domaine de la compression de données comme ceux utilisés dans Winzip ou Winrar, il représente principalement l’un des premiers algorithmes de compression textuel. Le plus drôle dans la naissance de cet algorithme est qu’il a été inventé par Huffman lorsqu’il était encore étudiant à MIT, leur enseignant à cette époque leur a donné le choix de choisir entre faire l’examen ou de rédiger un rapport sur un sujet donné, Huffman a choisi d’écrire le rapport qui a ensuite en 1952 produit ce célèbre algorithme de compression.
L’algorithme se base sur le principe de donner un code binaire réduit pour les caractères les plus répandus dans un texte, et inversement de données un code plus long pour les caractères les moins fréquents. D’autre part, l’algorithme de Huffman, permet indirectement de conceptualiser les principes de la théorie de l’information créer par Shannon, une partie de la théorie stipule que l’information la plus importante est celle qui a la probabilité ou (la fréquence) la plus basse, et inversement, l’information la moins importante possède la probabilité la plus élevée dans un texte ou un bloc de données.
On peut clairement distinguer sur la vidéo en haut l’utilisation d’un arbre binaire, qui permet principalement la synthèse des codes binaires pour chaque caractère. Cet arbre va être créé, premièrement, en affectant la fréquence d’apparition de chaque caractère dans le texte, où chaque caractère va représenter les feuilles de l’arbre, les feuilles avec les fréquences les plus basses vont composer les nœuds avec une fréquence égale à la somme des fréquences des 2 feuilles, d’une manière récursive et ascendante les nouveaux nœuds créent dans l’arbre vont aussi être créés par la somme des 2 nœuds (ou feuilles) avec la plus basse fréquence, jusqu’à ce que tout l’arbre soit construit.
Cet algorithme est très important à maîtriser pour les étudiants en informatique, ça permet premièrement de comprendre les principes de la compression, et deuxièmement, d’assimiler les concepts de la théorie de l’information. La première vidéo en haut et celle de l’excellente chaîne YouTube de Tom Scott, une chaîne principalement destinée à la science. Et la deuxième vidéo pour mieux expliquer la création de l’arbre de l’algorithme de Huffman.