Compression de données/Codage de Shannon-Fano
Le codage de Shannon-Fano ou codage de Fano-Shannon est un algorithme de compression de données sans perte élaboré par Robert Fano à partir d'une idée de Claude Shannon.
Il s'agit d'un codage entropique produisant un code préfixe très similaire à un code de Huffman, bien que pas toujours optimal, contrairement à ce dernier.
Principe
modifierLa probabilité de chaque symbole à compresser doit être connue. Dans la plupart des cas, des fréquences ou occurrences fixes calculées à partir des données à compresser sont utilisées ; on parle alors de codage de Shannon-Fano semi-adaptatif (qui nécessite deux passes successives sur les données à compresser : la première pour calculer les probabilités, la seconde pour compresser à proprement parler). Il est également possible d'utiliser des probabilités fixes non dépendantes des données à compresser (codage statique) ou des probabilités variant au fur et à mesure de la compression (codage adaptatif).
Le processus est de trier les symboles à compresser par ordre croissant de leurs nombre d’occurrences. Puis l'ensemble trié des symboles est séparé en deux groupes de telle façon que le nombre d'occurrences des deux parties soient égaux ou presque (le nombre d'occurrences d'un groupe étant égale à la somme des occurrences des différents symboles de ce groupe). On réitère le processus jusqu'à obtenir un seul arbre. On associe ensuite par exemple le code 0 à chaque embranchement partant vers la gauche et le code 1 vers la droite.
Comparaison avec le codage de Huffman
modifierL'approche du codage de Shannon-Fano est descendante : l'algorithme part de l'ensemble des symboles et divise cet ensemble récursivement jusqu'à arriver à des parties ne contenant qu'un seul symbole. L'inconvénient de cette approche est que, lorsqu'il n'est pas possible de séparer un ensemble de symboles et deux sous-ensembles de probabilités à peu près égales (c'est-à-dire lorsque l'un des sous-ensembles est beaucoup plus probable que l'autre), les codes produits ne sont pas optimaux.
Le codage de Huffman a une approche ascendante : l'algorithme part des symboles et regroupe ceux ayant la probabilités la plus faible, jusqu'à avoir regroupé tous les symboles. Cette approche permet d'obtenir systématiquement un code optimal au niveau du symbole, dans le pire cas de la même longueur que le code de Shannon-Fano équivalent, dans tous les autres cas plus court.
Les codages de Shannon-Fano et de Huffman souffrent cependant tous les deux du même inconvénient : ils codent les symboles sur un nombre de bits entier. Un codage arithmétique, optimal au niveau du bit, permet de coder des symboles sur un nombre de bits arbitraire (y compris 0), et d'atteindre l'entropie de Shannon.
Principe détaillé
modifierL'algorithme se base sur le nombre d'occurrence de chaque caractère pour établir la table des codes binaires de taille variable.
Supposons que la phrase à coder est « this is an example of a huffman tree ». Il s'agit de la même phrase que pour le chapitre sur le codage de Huffman afin de pouvoir comparer les résultats.
On recherche tout d'abord le nombre d'occurrences de chaque caractère. Dans l'exemple précédent, la phrase contient 2 fois le caractère h et 7 espaces. Chaque caractère constitue une des feuilles de l'arbre à laquelle on associe un poids égal à son nombre d'occurrences.
this is an example of a huffman tree
Occurence de chaque caractère, trié du plus fréquent au moins fréquent :
| Nœud | a | e | f | h | i | m | n | s | t | l | o | p | r | u | x | |
| Occurrence | 7 | 4 | 4 | 3 | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 |
Contrairement à l'algorithme d'Huffman, le tri n'est fait qu'une seule fois. De plus, le code binaire se construit au fur et à mesure, en commençant par diviser le tableau en deux parties auxquelles on associe le bit 0 et le bit 1 respectivement. Chaque division doit produire deux moitiés de poids égaux si possible. Chaque moitié est alors divisée à son tour, jusqu'à ce qu'il ne soit plus possible de diviser.
À chaque étape, on ajoute une ligne au tableau indiquant les divisions effectuées, le bit associé en gras, et le poids en bleu clair :
| Nœud | a | e | f | h | i | m | n | s | t | l | o | p | r | u | x | |
| Occurrence | 7 | 4 | 4 | 3 | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 |
| Étape 1 | 0 (18) | 1 (18) | ||||||||||||||
| Étape 2 | 0 (11) | 1 (7) | 0 (10) | 1 (8) | ||||||||||||
| Étape 3 | 0 (7) | 1 (4) | 0 (4) | 1 (3) | 0 (6) | 1 (4) | 0 (4) | 1 (4) | ||||||||
| Étape 4 | 0 (4) | 1 (2) | 0 (2) | 1 (2) | 0 (2) | 1 (2) | 0 (2) | 1 (2) | ||||||||
| Étape 5 | 0 (2) | 1 (2) | 0 (1) | 1 (1) | 0 (1) | 1 (1) | 0 (1) | 1 (1) | ||||||||
On obtient donc cette table de codage binaire :
| Caractère | Code binaire |
|---|---|
000
| |
| a | 001
|
| e | 010
|
| f | 011
|
| h | 10000
|
| i | 10001
|
| m | 1001
|
| n | 1010
|
| s | 1011
|
| t | 1100
|
| l | 11010
|
| o | 11011
|
| p | 11100
|
| r | 11101
|
| u | 11110
|
| x | 11111
|
La phrase « this is an example of a huffman tree » se code alors sur 136 bits au lieu de 288 bits (si le codage initial des caractères tient sur 8 bits).
t h i s i s a n e x a m p l e 1100 10000 10001 1011 000 10001 1101 000 001 1010 000 010 11111 001 1001 11100 11010 010 000
o f a h u f f m a n t r e e 11011 011 000 001 000 10000 11110 011 011 1001 001 1010 000 1100 11101 010 010
Utilisations
modifierComme le codage de Huffman est très similaire au codage de Shannon-Fano et donne de meilleurs résultats, ce dernier n'est pratiquement plus utilisé aujourd'hui.
Le codage de Shannon-Fano est utilisé après une compression par LZ77, pour le codage entropique de l'algorithme implode, utilisé historiquement dans le format ZIP[1]. L'algorithme implode a été détrôné par l'algorithme deflate, remplaçant le codage de Shannon-Fano par un codage de Huffman.
Voir aussi
modifierBibliographie
modifier- Claude Elwood Shannon, « A Mathematical Theory of Communication », Bell System Technical Journal, vol. 27, pp. 379-423, Modèle:Date-.
- Robert Mario Fano, « The transmission of information », Technical Report No. 65, 1949. Research Laboratory of Electronics, M.I.T., Cambridge, USA.