Codage Shannon–Fano

Dans le domaine de la compression de données , le codage Shannon-Fano , nommé d'après Claude Shannon et Robert Fano , est l'une des deux techniques apparentées permettant de construire un code de préfixe basé sur un ensemble de symboles et leurs probabilités (estimées ou mesurées).

• La méthode de Shannon consiste à choisir un code de préfixe où un symbole source reçoit la longueur du mot de code . Une méthode courante de choix des mots de code utilise le développement binaire des probabilités cumulatives. Cette méthode a été proposée dans « A Mathematical Theory of Communication » (1948) de Shannon, son article introduisant le domaine de la théorie de l'information .
• La méthode de Fano divise les symboles sources en deux ensembles (« 0 » et « 1 ») avec des probabilités aussi proches que possible de 1/2. Ensuite, ces ensembles sont eux-mêmes divisés en deux, et ainsi de suite, jusqu'à ce que chaque ensemble ne contienne qu'un seul symbole. Le mot de code de ce symbole est la chaîne de « 0 » et de « 1 » qui enregistre la moitié des divisions sur laquelle il est tombé. Cette méthode a été proposée dans un rapport technique ultérieur (imprimé) de Fano (1949).

Les codes Shannon–Fano sont sous-optimaux dans le sens où ils n'atteignent pas toujours la longueur de mot de code attendue la plus petite possible, comme le fait le codage Huffman . Cependant, les codes Shannon–Fano ont une longueur de mot de code attendue à 1 bit de la valeur optimale. La méthode de Fano produit généralement un codage avec des longueurs attendues plus courtes que la méthode de Shannon. Cependant, la méthode de Shannon est plus facile à analyser théoriquement.

Le codage Shannon-Fano ne doit pas être confondu avec le codage Shannon-Fano-Elias (également connu sous le nom de codage Elias), le précurseur du codage arithmétique .

Concernant la confusion entre les deux codes différents désignés par le même nom, Krajči et al. écrivent :

Vers 1948, Claude E. Shannon (1948) et Robert M. Fano (1949) ont tous deux proposé indépendamment deux algorithmes de codage de source différents pour une description efficace d'une source discrète sans mémoire. Malheureusement, malgré leurs différences, les deux schémas sont devenus connus sous le même nom de codage Shannon–Fano .

Plusieurs raisons peuvent expliquer cette confusion. D'une part, dans la discussion de son schéma de codage, Shannon mentionne le schéma de Fano et le qualifie de « sensiblement identique » (Shannon, 1948, p. 17 [réimpression]). D'autre part, les schémas de codage de Shannon et de Fano sont similaires dans le sens où ils sont tous deux efficaces, mais sous-optimaux , sans préfixe et ont des performances similaires.

La méthode de Shannon (1948), qui utilise des longueurs de mots prédéfinies, est appelée codage Shannon-Fano par Cover et Thomas, Goldie et Pinch, Jones et Jones, et Han et Kobayashi. Elle est appelée codage Shannon par Yeung.

La méthode de Fano (1949), utilisant la division binaire des probabilités, est appelée codage Shannon–Fano par Salomon et Gupta. Elle est appelée codage Fano par Krajči et al.

La méthode de Shannon commence par décider des longueurs de tous les mots de code, puis choisit un code de préfixe avec ces longueurs de mots.

Étant donné une source avec des probabilités, les longueurs de mots de code souhaitées sont . Ici, est la fonction plafond , c'est-à-dire le plus petit entier supérieur ou égal à .

Une fois les longueurs des mots de code déterminées, nous devons choisir les mots de code eux-mêmes. Une méthode consiste à choisir les mots de code dans l'ordre des symboles les plus probables aux moins probables, en choisissant chaque mot de code comme étant le premier mot lexicographiquement de la longueur correcte qui conserve la propriété sans préfixe.

Une deuxième méthode utilise les probabilités cumulatives. Tout d'abord, les probabilités sont écrites dans l'ordre décroissant . Ensuite, les probabilités cumulatives sont définies comme

ainsi de suite. Le mot de code pour symbole est choisi pour être le premier chiffre binaire dans le développement binaire de .

Cet exemple montre la construction d'un code Shannon–Fano pour un petit alphabet. Il existe 5 symboles sources différents. Supposons que 39 symboles au total ont été observés avec les fréquences suivantes, à partir desquelles nous pouvons estimer les probabilités des symboles.

Cette source contient des bits d'entropie .

Pour le code Shannon-Fano, nous devons calculer les longueurs de mots souhaitées .

Nous pouvons choisir les mots de code dans l'ordre, en choisissant le premier mot lexicographique de la longueur correcte qui conserve la propriété sans préfixe. Clairement, A obtient le mot de code 00. Pour conserver la propriété sans préfixe, le mot de code de B ne peut pas commencer par 00, donc le premier mot lexicographiquement disponible de longueur 3 est 010. En continuant ainsi, nous obtenons le code suivant :

Alternativement, nous pouvons utiliser la méthode de probabilité cumulative.

Notez que bien que les mots de code des deux méthodes soient différents, les longueurs des mots sont les mêmes. Nous avons des longueurs de 2 bits pour A et de 3 bits pour B, C, D et E, ce qui donne une longueur moyenne de

qui est à un bit près de l'entropie.

Pour la méthode de Shannon, les longueurs de mots satisfont

Par conséquent, la longueur de mot attendue satisfait

Ici, l' entropie est , et le théorème de codage source de Shannon dit que tout code doit avoir une longueur moyenne d'au moins . Nous voyons donc que le code Shannon–Fano est toujours à un bit près de la longueur de mot optimale attendue.

Dans la méthode de Fano, les symboles sont classés par ordre décroissant de probabilité, puis divisés en deux ensembles dont les probabilités totales sont aussi proches que possible de l'égalité. Tous les symboles se voient alors attribuer les premiers chiffres de leurs codes ; les symboles du premier ensemble reçoivent « 0 » et les symboles du second ensemble reçoivent « 1 ». Tant qu'il reste des ensembles comportant plus d'un élément, le même processus est répété sur ces ensembles, afin de déterminer les chiffres successifs de leurs codes. Lorsqu'un ensemble a été réduit à un seul symbole, cela signifie que le code du symbole est complet et ne formera pas le préfixe du code d'un autre symbole.

L'algorithme produit des codages à longueur variable assez efficaces ; lorsque les deux ensembles plus petits produits par un partitionnement ont en fait une probabilité égale, le bit d'information utilisé pour les distinguer est utilisé le plus efficacement. Malheureusement, le codage Shannon-Fano ne produit pas toujours des codes de préfixe optimaux ; l'ensemble de probabilités {0,35, 0,17, 0,17, 0,16, 0,15} est un exemple d'ensemble auquel des codes non optimaux seront attribués par le codage Shannon-Fano.

La version de Fano du codage Shannon-Fano est utilisée dans la IMPLODEméthode de compression, qui fait partie du ZIPformat de fichier .

Un arbre Shannon–Fano est construit selon une spécification conçue pour définir une table de codes efficace. L'algorithme réel est simple :

1. Pour une liste donnée de symboles, développez une liste correspondante de probabilités ou de fréquences d'occurrence afin que la fréquence relative d'occurrence de chaque symbole soit connue.
2. Triez les listes de symboles selon leur fréquence, avec les symboles les plus fréquents à gauche et les moins courants à droite.
3. Divisez la liste en deux parties, le nombre total de fréquences de la partie gauche étant aussi proche que possible du total de la partie droite.
4. La partie gauche de la liste est affectée au chiffre binaire 0 et la partie droite au chiffre 1. Cela signifie que les codes des symboles de la première partie commenceront tous par 0 et que les codes de la deuxième partie commenceront tous par 1.
5. Appliquez de manière récursive les étapes 3 et 4 à chacune des deux moitiés, en subdivisant les groupes et en ajoutant des bits aux codes jusqu'à ce que chaque symbole soit devenu une feuille de code correspondante sur l'arbre.

Nous continuons avec l’exemple précédent.

Tous les symboles sont classés par fréquence, de gauche à droite (voir la figure a). En plaçant la ligne de démarcation entre les symboles B et C, on obtient un total de 22 dans le groupe de gauche et un total de 17 dans le groupe de droite. Cela minimise la différence de totaux entre les deux groupes.

Avec cette division, A et B auront chacun un code qui commence par un bit 0, et les codes C, D et E commenceront tous par un 1, comme le montre la figure b. Par la suite, la moitié gauche de l'arbre reçoit une nouvelle division entre A et B, qui place A sur une feuille avec le code 00 et B sur une feuille avec le code 01.

Après quatre procédures de division, un arbre de codes est obtenu. Dans l'arbre final, les trois symboles avec les fréquences les plus élevées ont tous été affectés de codes à 2 bits, et deux symboles avec des nombres inférieurs ont des codes à 3 bits comme indiqué dans le tableau ci-dessous :

Cela donne des longueurs de 2 bits pour A, B et C et de 3 bits pour D et E, ce qui donne une longueur moyenne de

Nous voyons que la méthode de Fano, avec une longueur moyenne de 2,28, a surpassé la méthode de Shannon, avec une longueur moyenne de 2,62.

Il est démontré par Krajči et al que la longueur attendue de la méthode de Fano a une longueur attendue limitée au-dessus par , où est la probabilité du symbole le moins commun.

Aucun des algorithmes de Shannon-Fano ne garantit la génération d'un code optimal. Pour cette raison, les codes de Shannon-Fano ne sont presque jamais utilisés ; le codage de Huffman est presque aussi simple en termes de calcul et produit des codes de préfixe qui atteignent toujours la longueur de mot de code attendue la plus faible possible, sous la contrainte que chaque symbole soit représenté par un code formé d'un nombre entier de bits. Il s'agit d'une contrainte qui est souvent inutile, car les codes seront empaquetés de bout en bout dans de longues séquences. Si nous considérons des groupes de codes à la fois, le codage de Huffman symbole par symbole n'est optimal que si les probabilités des symboles sont indépendantes et sont une puissance de demi, c'est-à-dire . Dans la plupart des situations, le codage arithmétique peut produire une compression globale plus importante que le codage de Huffman ou de Shannon-Fano, car il peut coder en nombres fractionnaires de bits qui se rapprochent plus étroitement du contenu d'information réel du symbole. Cependant, le codage arithmétique n’a pas remplacé Huffman de la même manière que Huffman remplace Shannon-Fano, à la fois parce que le codage arithmétique est plus coûteux en termes de calcul et parce qu’il est couvert par de multiples brevets.

Quelques années plus tard, David A. Huffman (1952) a proposé un algorithme différent qui produit toujours un arbre optimal pour toutes les probabilités de symboles données. Alors que l'arbre Shannon-Fano de Fano est créé en divisant de la racine vers les feuilles, l'algorithme de Huffman fonctionne dans le sens inverse, en fusionnant des feuilles vers la racine.

1. Créez un nœud feuille pour chaque symbole et ajoutez-le à une file d’attente prioritaire , en utilisant sa fréquence d’occurrence comme priorité.
2. Lorsqu'il y a plus d'un nœud dans la file d'attente :
   1. Supprimez les deux nœuds de probabilité ou de fréquence la plus faible de la file d'attente
   2. Ajoutez respectivement 0 et 1 à tout code déjà attribué à ces nœuds
   3. Créez un nouveau nœud interne avec ces deux nœuds comme enfants et avec une probabilité égale à la somme des probabilités des deux nœuds.
   4. Ajoutez le nouveau nœud à la file d’attente.
3. Le nœud restant est le nœud racine et l’arbre est complet.

Nous utilisons les mêmes fréquences que pour l’exemple Shannon–Fano ci-dessus, à savoir :

Dans ce cas, D et E ont les fréquences les plus basses et se voient donc attribuer respectivement 0 et 1 et sont regroupés avec une probabilité combinée de 0,282. La paire la plus basse est maintenant B et C, ils se voient donc attribuer 0 et 1 et sont regroupés avec une probabilité combinée de 0,333. Cela laisse BC et DE avec les probabilités les plus basses, donc 0 et 1 sont ajoutés au début de leurs codes et ils sont combinés. Il ne reste alors que A et BCDE, qui ont respectivement 0 et 1 ajoutés au début et sont ensuite combinés. Cela nous laisse avec un seul nœud et notre algorithme est terminé.

Les longueurs de code pour les différents caractères sont cette fois de 1 bit pour A et de 3 bits pour tous les autres caractères.

Cela donne des longueurs de 1 bit pour A et de 3 bits pour B, C, D et E, ce qui donne une longueur moyenne de

Nous constatons que le code Huffman a surpassé les deux types de code Shannon-Fano, dont les longueurs attendues étaient de 2,62 et 2,28.