L'algorithme de Huffman
Il s'agit de l'algorithme le plus optimisé pour compresser des données. Il est souvent représenté sous forme d'arbre. On appelle cet arbre "arbre binaire" car il est composé de nœuds ayant chacun 2 embranchements.
Cette configuration nous arrange bien car elle nous permet de nous servir de nos chiffres préférés 1 et 0 pour donner le chemin de chaque lettre.
L'arbre utilisé pour le langage morse utilise le même système. Au lieu d'utiliser des 1 et des 0 on utilise des traits et des points ou des longs et des courts.
Cet algorithme est utilisé quasiment partout où l'on trouve de la compression. D'autres algorithmes de compression existent mais celui de Huffman garde le meilleur rapport facilité d'implémentation / efficacité.
Quelques exemples qui utilisent cet algorithme: JPEG, PNG, ZIP ou encore MP3.
Tout d'abord, il faut compter le nombre d'occurrence de chaque lettre (il peut s'agir de n'importe quoi mais prenons des lettres pour l'exemple) dans la chaîne de caractères. Nous avons donc une fois chaque lettre avec un nombre d'occurrences associé, appelons ce nombre le poids.
Nous pouvons appeler ces lettres des feuilles pour utiliser un terme générique. En effet dans notre exemple, il s'agit de lettres. Ces feuilles peuvent très bien être des pixels, voir même des nombres premiers et j'en passe. Nous les appelons feuilles car elles se trouveront forcément au bout de l'arbre en utilisant l'algorithme de Huffman.
Pour construire l'arbre nous devons commencer par la racine (le bas de l'arbre). Nous prenons les deux lettres (feuilles) ayant le poids le plus faible et les associons pour créer un nœud. Ce nœud n'aura aucune lettre mais aura 2 branches au bout desquelles se trouveront des feuilles (lettres). Le poids de ce nœud sera la somme du poids des feuilles.
Maintenant que ces deux feuilles sont "rangées", nous ne prendront en compte plus que le nœud qui les contient. Nous allons utiliser ce nœud comme s'il s'agissait d'une feuille avec un poids et des branches mais aucune lettre.
En réalité, dans le code, nous feront l'inverse: nous utiliserons les feuilles comme si c'était des nœuds sans branche car nous aurons bien plus de nœuds que de feuilles.
Nous recommençons cette opération jusqu'à n'avoir plus qu'un seul nœud qui contient tous les autres nœuds. Au bout de l'arbre se trouveront les feuilles qui auront chacune une "adresse" ou "signature" unique.
