> shannon | fano | entropie <
// Shannon-Fano – Codage entropique descendant pour la compression de données
Basé sur l’entropie
Utilise la théorie de l’information pour construire des codes efficaces à longueur variable.
Approche descendante
Divise récursivement les symboles en groupes de probabilité similaire.
Algorithme historique
Méthode pionnière qui a inspiré de nombreux algorithmes de compression modernes.
>> informations techniques
Comment fonctionne Shannon-Fano:
Le codage Shannon-Fano trie les symboles par fréquence, puis les divise récursivement en deux groupes de probabilité totale la plus proche possible. Chaque division ajoute un bit au code (0 à gauche, 1 à droite). Le résultat est un code préfixe à longueur variable.
Processus d’encodage:
Texte : "AAABBCD" Fréquences : A:3, B:2, C:1, D:1 Division : [A] | [B,C,D] Codes : A : 0 B : 10 C : 110 D : 111 Codé : 0 0 0 10 10 110 111
Pourquoi utiliser Shannon-Fano:
- >Simple à implémenter
- >Bon taux de compression
- >Intérêt historique
- >Utile pour l’enseignement
- >Codes préfixes
>> questions fréquentes
Qu’est-ce que le codage Shannon-Fano ?
Le codage Shannon-Fano est une technique de codage entropique développée dans les années 1940 par Claude Shannon et Robert Fano. C’est l’un des premiers algorithmes à utiliser des codes de longueur variable basés sur la probabilité des symboles.
Shannon-Fano ou Huffman ?
Les deux produisent des codes à longueur variable, mais Huffman est optimal et minimise la longueur moyenne des codes. Shannon-Fano est plus simple mais peut produire des codes légèrement plus longs. Huffman construit l’arbre de bas en haut, Shannon-Fano de haut en bas.
Comment se fait la division des symboles ?
Les symboles sont triés par fréquence puis divisés en deux groupes de probabilités totales aussi proches que possible. L’opération se répète récursivement jusqu’à ce qu’il ne reste plus qu’un symbole par groupe.
Shannon-Fano est-il encore utilisé ?
Shannon-Fano est aujourd’hui surtout utilisé comme référence historique et pédagogique. En pratique, il a été supplanté par le codage de Huffman, qui garantit l’optimalité. Il reste néanmoins précieux pour comprendre les bases de la compression.