> 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.
// Exemple détaillé
| Symbol | Freq | Code | Bits |
|---|---|---|---|
| A | 15 | 00 | 2 |
| B | 7 | 01 | 2 |
| C | 6 | 10 | 2 |
| D | 6 | 110 | 3 |
| E | 5 | 111 | 3 |
// Exemples de code
Frequencies A=15 B=7 C=6 D=6 E=5 (39 symbols)
1. Sort symbols by frequency (descending).
2. Split the list where the two halves' totals are closest:
{A,B}=22 | {C,D,E}=17 -> first bit 0 / 1
3. Recurse on each half until single symbols remain:
{A}|{B} -> 00, 01 {C}|{D,E} -> 10, 11.. then {D}|{E} -> 110, 111
Total 15*2 + 7*2 + 6*2 + 6*3 + 5*3 = 89 bits
Huffman on the same data: A=1 bit, others 3 bits -> 87 bits
>> Autres questions
Q : En quoi Shannon-Fano diffère-t-il de Huffman ?
R : Shannon-Fano divise la liste triée de haut en bas en deux moitiés de fréquences aussi égales que possible ; Huffman construit l’arbre de bas en haut en fusionnant les symboles les plus rares. Huffman est prouvé optimal, pas Shannon-Fano.
Q : Shannon-Fano est-il toujours optimal ?
R : Non. Dans l’exemple il faut 89 bits contre 87 pour Huffman. Les deux donnent des codes sans préfixe, mais la règle de partage de Shannon-Fano peut choisir de mauvaises coupes.
Q : Où utilise-t-on Shannon-Fano ?
R : Surtout comme méthode historique et pédagogique (Claude Shannon et Robert Fano, 1948/49). Une variante existe dans l’algorithme IMPLODE du format ZIP ; les compresseurs modernes emploient Huffman ou le codage arithmétique.