Algorithme de Shannon-Fano

Sommaire

  1. Introduction
  2. Présentation de l’algorithme de Shannon-Fano
  3. Comparaison de l’algorithme avec un algorithme naïf
  4. Algorithme de Shannon-Fano
  5. Comparaison de l’algorithme avec l’algorithme d’Huffman
  6.  Conclusion
  7.  Bibliographie

Introduction:

     Lorsque l’on transporte une image ou un son, il faut passer du format analogique (réel) au format numérique (virtuel). Il faut donc un conditionnement et un codage. Puis il faut transporter ces informations par un « tunnel », autrement appelé « canal de transmission ». En partant du signal de base, on passe par plusieurs étapes, représentées par ce petit schéma :

Chaque message envoyé sous la forme d’un signal, peut se représenter par une courbe. Exemple, un message binaire peut être représenté par un signal carré. Ce signal peut être unipolaire ou NRZ, c’est à dire qu’il peut varier respectivement de +0 a +x ou de -x à +x.

Un signal peut être perturbé par des bruits (des parasites) qui peuvent êtres d’origines différentes. Les éléments inductifs sont ceux qui produisent le plus de parasites (moteurs électriques, transformateurs, …). Mais un message non compressé peut prendre beaucoup de place, alors qu’on peut, via plusieurs algorithmes, compresser ce message tout en gardant le même contenu. C’est l’utilité d’un codage de Shannon-Fano.

Pour donner une définition du codage de Shannon-Fano, c'est un système de codage suivant un dictionnaire donné comme tout autre système, mais ce qui différencie vraiment ce système d'un autre, c'est qu'il permet de minimiser l'espace (utiliser moins de bits qu'un système classique) et donc comprimer l'information tout en gardant un message facilement lisible.

Présentation de l’algorithme Shannon-Fano :

L’idée du codage de Shannon-Fano est d’utiliser moins de bits que pour un système normal et donc économiser des bits et utiliser moins d’espace (comprimer l’information). Diviser l’ensemble de lettre possible  en deux parties suivant le nombre d’occurrence des lettres, tout en obtenant un message lisible.

On va à chaque fois découper en deux parties les plus égales, et attribuer à chaque partie un 0 et un 1. Le schéma ci-dessous représente l’arborescence des codes de chaque probabilité.

On choisit arbitrairement deux parties, pour qu’elles aient à chaque fois la valeur la plus approchante l’une de l’autre, et tant que les parties sont divisibles, on continue ainsi. Dans le tableau, on prend ici a1 et a2, (dont la somme fait 0.62) et tout le reste, (dont la somme fait 0.38). On les sépare en deux, on met le zéro dans la partie du dessus, et les 1 dans la partie du bas. Puis on recommence pour chaque morceau de probabilité, on sépare le groupe du dessus en 2, et celui du dessous entre a3 et a4 pour le chiffre 0, et a5, a6 et a7 pour 1. Lorsqu'on a séparé tous les groupes, il suffit de tracer des lignes entre chaque probabilité (d’a1 à a7 ici), et de lire en partant de la droite, la ligne correspondante. Pour a7, on lit 1111.

Comparaison de ce codage avec un codage naïf :

Un exemple peut être plus explicite : appliquons ce codage sur la phrase suivante : MICHEL CHARMA RACHEL, RACHEL CHERCHA MICHELLE. (Dans L’exemple qui suit les espaces et la virgule n’entre pas en compte).

On remarque que ces mots utilisent en tout et pour tout 8 lettres qui sont : A, C, E, H, I, L, M, R.

Donc si on voulait reproduire cette séquence en un nouveau code binaire vu que nous avons 8 lettres ça reviendrait à remplacer chaque lettre par un code à trois chiffres (de 0 et de 1 bien sûr). Par exemple : A -> 000, E-> 001 … etc. Et donc puisque notre exemple est constitué de 39 lettres le nombre total de bit qu’on aurait est 39 x 3 = 117 bits.

Pour le codage de Shannon-Fano il faut classer les symboles de la séquence par nombre d'occurrences croissantes et on obtient {I=2, M=3, R=4, A=5, L=5, E=6, C=7, H=7}. Puis séparer les symboles en deux groupes de sorte que le total des nombres d'occurrences soit sensiblement égal dans les deux sous-groupes (sans changer l’ordre dans le qu'elle elle se trouve). Ce qui va nous donner G1= {C, E, H} pour un total de 20 répétitions et G2= {A, I, L, M, R} pour un total de 19 répétitions. Après ça on va concaténer un 1 à toutes les lettres du groupe qui était droite et un zéro à l’autre ce qui va nous donner par exemple (Lettre, codage)= {(C, 1) ;(A, 0)}. Et on continue la même chose avec tous les sous-groupes tant que cela aura plus de deux éléments une fois arrivés à cette étape on finit notre code par un 1 pour le symbole qui est et un 0 ou un 1 seulement si le sous-groupe contient un seul élément par exemple le sous-groupe G1 va donner deux nouveaux groupes G11= {C} et G12= {E, H} ce qui va donner (C, 11) et pour le deuxième groupe (H, 101) et (E, 100) et en continuant ainsi on obtient à la fin :

C -> 11 (utiliser 7 fois)                          H -> 101 (utiliser 7 fois)

E -> 100 (utiliser 6 fois)                         L -> 011 (utiliser 5 fois)

A -> 010 (utiliser 5 fois)                        R -> 001 (utiliser 4 fois)

M -> 0001 (utiliser 3 fois)                      I   -> 0000 (utiliser 2 fois)

Enfin on vérifie son total de bit et on obtient (7x2) + (27x3) + (4x5)= 115  fois et effectivement il est meilleur qu’un code standard et donc il reste très efficace utilisant moins de mémoire (bien qu’il ne soit pas optimal). Quant à la lisibilité elle reste simple car il suffit de lire un ensemble de 0 et de 1 jusqu’à obtenir une séquence se trouvant dans notre dictionnaire.

Algorithme de Shannon-Fano :

1-PSEUDO Code :

  • On commence par décomposer notre chaîne de caractère en tableau de caractère ou chaque case contient le caractère ainsi que son nombre d'occurrences
  • Classer les symboles de la séquence par nombre d'occurrences croissantes;
  • Séparer les symboles en deux sous-groupes de sorte que les totaux des nombres d'occurrences soient sensiblement égaux dans les deux sous-groupes
  • Concaténer 0 à gauche de tous les symboles du sous-groupe de gauche et 1 à ceux du sous-groupe de droite;
  • Recommencer pour chacun des sous-groupes, jusqu'à ce qu'ils n'aient plus qu'un seul élément.

procedure SF-Decomoposer(S)

begin

if (|S|>1) then

begin

diviser S en 2 sections (S1 et S2) ayant un nombre plus ou moins égale de caracteres

ajouter 1 aux codes de S1

ajouter 0 aux codes de S2

SF-Decomoposer(S1)

SF-Decomoposer(S2)

End

End

2-ANIMATION :

Différence entre le codage de Shannon-Fano et le codage d’Huffman :

Pour clôturer nous allons comparer cet algorithme avec celui de Huffman. L’algorithme d’Huffman est meilleur en performance (niveau de compression) que celui de Shannon Fano. Mais dans le meilleur des cas, Shannon-Fano sera aussi efficace que Huffman.

Pour mesurer le taux de compression, On calcule l’entropie (mesuré en Shannon/seconde) :

a1 a2 a3 a4 a5 a6 a7
0.38 0.24 0.1 0.1 0.1 0.05 0.03

On commence par calculer H, la moyenne par symbole :

H = -Σ pi*log2 (pi) H = -[( 0.38*log2(0.38) ) + ( 0.24*log2(0.24) ) + 3*( 0.1*log2(0.1) ) + ( 0.05*log2(0.05) ) + ( 0.03*log2(0.03) )] H = 2.39 sh/s (Shannon/ seconde)

Si Pi Code Li
a1 0.38 00 2
a2 0.24 01 2
a3 0.1 100 3
a4 0.1 101 3
a5 0.1 110 3
a6 0.05 1110 4
a7 0.03 1111 4

Petite explication :

Si est le nom de la probabilité associée au symbole transmis Pi la probabilité d’apparition du symbole associée Code le code binaire qui représente le symbole Li la longueur du code (le nombre de chiffres du code)

Maintenant on calcule l’efficacité de compression du message, qui se traduit par : Ec = H / Σ (Pi*Li) Dans notre cas, Ec donne donc : Ec = 2.39 / (0.38*2 + 0.24*2 + 3*(0.1*3) + 0.05*4 + 0.03*4) <=> Ec = 2.39 / 2.46 = 97.6 % Notre efficacité sera donc de 97.6 %

Exemple : prenons en exemple la phrase : HOURRA HOURRA HOURRRRA Avec le codage Huffman on aura 46 bits au total, là où avec le codage Shannon-Fano on en aura 49 bits (à titre d’information un codage naïf demandé 20 x 3 = 60 bits).

Conclusion :

Le codage de Shannon-Fano est l'un des meilleurs systèmes de codage de par sa quasi-optimalité et facilité de lecture. Il a été utilisé historiquement dans la compression (sans perte de données) dans le format ZIP mais il a été remplacé au fur et à mesure par le codage d'Huffman qui donne de meilleurs résultats ce qui a poussé a sa non-utilisation de nos jours.

Bibliographie :

https://fr.wikipedia.org/wiki/Codage_de_Shannon-Fano

http://lwh.free.fr/pages/algo/compression/ShannonFano.html

https://www.fortisfio.com/le-codage-de-shannon-fano-et-huffman/

http://boowiki.info/art/theorie/codage-shannon-fano.html

1 Cliquer pour recommander cet article