Le codage de Shannon-Fano

Tout comme le codage de Huffman le codage de Shannon-Fano est un codage statistique à longueur variable (VLC=Variable Length Coding) utilisé pour la compression sans pertes de données. Il a été mis au point par Robert Fano d'après une idée de Claude Shannon.

Ce code s'obtient par l'algorithme suivant :

1. Classer les symboles de la séquence par nombre d'occurences croissants,
2. Séparer les symboles en deux sous-groupes de sorte que le total des nombres d'occurences soient sensiblement égaux dans les deux sous-groupes
3. Concaténer 0 à gauche de tous les symboles du sous-groupe de gauche et 1 à ceux du sous-groupe de droite,
4. Recommencer pour chacun des sous-groupes, jusqu'à ce qu'ils n'aient plus qu'un seul élément.

L'animation ci-après construit un code de Shannon-Fano a partir d'un texte. Pour simplifier le graphe, les caractères sont traduits en majuscules non accentuées et seuls les caractères alphabétiques sont codés. Vous pouvez saisir le texte dans la zone ci-dessous :

Zut ! Je crois que le chien Sambuca préfère le whisky revigorant au doux porto.