Algorithme de Shannon-Fano

Sommaire :

  • I- Une histoire de codage
  • II- Principe de codage
    • II.1- Codes entropiques
    • II.2- Codes préfixes
  • III- Algorithme de Shannon-Fano
  • IV- Exemple d'application
  • V- Efficacité de l'algorithme
    • V.1- Shannon-Fano VS Huffman
  • VI- Bibliographie

I- Une histoire de codage

Tous nos données (Vidéo, image, Base de données …) qui existe sur nos supports de stockage y compris les Datacenter et Internet sont conservées sous format de suites de bits. Les tailles de ces données sont souvent de taille colossale qui rendent les opérations de transfert et d’archivage, des procédés pénible et longues à réaliser. Très vite ce casse-tête a intrigué beaucoup de savant qui se sont penché sur le sujet.

On peut citer la méthode développée par Claude Shannon et Robert Fano en 1949 s’agissant du processus de codage ou de conversion des données de manière à consommer plus d’espace mémoire, en se basant sur le la théorie de l’information de Claude Shannon publié dans l’article ‘’ A Mathematical Theorie of Communication ‘’ en 1948.

Dans ce blog on définira le principe de codage de données et le codage préfixe. Ensuite, l’algorithme de Shannon-Fano. Enfin, on comparera cette avec un algorithme de codage naïf et l'algorithme de Huffman .

II- Principe de codage

Pour commencer, on doit définir d'abord quelques notions.
Soit un alphabet (fini) X .
Définition : Un code de X est une application  \phi  :   X  \rightarrow  \{0,1\}  .
Définition : Un mot de code est un élément de  \phi(X ) .
Définition : Un codage de X est une application  \psi : X^*  \rightarrow   {0, 1}^*  , qui à toute séquence finie de lettres de X associe une séquence binaire.

II.1- Codes entropiques

L'entropie d'une source est la quantité moyenne d'information contenue dans cette source . Cette mesure a été introduite par Shannon. Cette quantité notée H égale à la somme des espérances des quantités d'information telle que la quantité d'information notée H(i) est calculée par :
 H(i) =log(1/P(i))  donc pour l'entropie on obtient :  H =  $\sum _{i}  H_{i} P(i)$  .

l'entropie permit à Shannon d'évaluer la limite d'information à transmettre dans un canal donné. Il a également montré qu'en utilisant le codage adéquat il était possible de transmettre les informations de façon que le récepteur soit en mesure de restaurer la donnée original sans perte d'information , Où on introduit la notion de codage entropique qui est une méthode de codage basé sur le concept de l'entropie . Le codage entropique utilise des statistiques sur les données d'entrées (la source) pour construire un code. L'information à coder est représentée par une variable aléatoire de \Omega = \{a,b,...\} ,  \Omega l'ensemble des symboles de source, à valeur dans un alphabet de taille finie.

II.2- Codes préfixes

On rappelle qu’un code est dit à décodage unique si son codage associé est non ambigu, c’est-à-dire que si deux lettres (mot) distinctes sont codées par des mots distincts. Autrement dit, une séquence binaire finie donnée correspond au plus à une séquence de lettres de la source.

Condition d’un code Préfixe :
« Aucun mot de code n’est le début d’un autre »

Arbre d’un code : pour tout code préfixe on peut associer un arbre dont les feuilles sont les feuilles.

Exemple :
a : 0
b : 10
c : 110
d : 111


Un code est dit irréductibles si les nœuds de son arbre associé ont soit zéro ou deux fils. il existe plusieurs types de codes préfixe :
Codage de Shannon-Fano, Codage de Huffman, Codage arithmétique.

III- Algorithme de Shannon-Fano

l'algorithme de codage de Shannon-Fano est un algorithme récursif consiste à faire :

  1. Créer une liste (une map) qui associe à chaque caractère sa fréquence d'apparition.
  2. Trier la liste on ordre décroissant par rapport à la fréquence d'apparition.
  3. découpez la liste en deux partitions \l_{i}, l_{j} tel que  $\sum _{c_{i} }  f_{i}  $  \approx  $\sum _{c_{j}} f_{j}  $,     c_{i}  $ \in $  l_{i}  et     c_{j}  $ \in $  l_{j}
    La taille des deux partitions doivent être proche en matière de somme d’apparition de chaque caractère
  4. Affecter 0 aux éléments de la liste \l_{i} et 1 aux éléments de la liste \l_{j}
  5. répéter l'étape 3 et 4, jusqu'à chaque caractère est contenu dans une liste à part (chaque liste contient qu'un seul caractère).

Pseudo Code :

  1.  Début
  2.        Construire liste « L » décroissante par rapport aux nombres d’apparition de chaque caractère ;
  3.        ShanonFanon (L) ;
  4.        Ecrire L ;
  5.   Fin

  6.  Fonction ShanonFanon(L)
  7.  Début
  8.        SI (|L| > 1)
  9.        DSI
  10.               Diviser L en L1 et L2 avec à peu près le même nombre d’apparition ;
  11.               Ajouter 0 à L1 ;
  12.               Ajouter 1 à L2 ;
  13.               ShanonFanon (L1) ;
  14.               ShanonFanon (L2) ;
  15.        FSI
  16.  End

IV- Exemple d'application

Pour mieux illustré le fonctionnement de l'algorithme, nous vous proposons de le dérouler sur des exemples de votre choix dans notre programme :


V- Efficacité de l'algorithme

Calculant la compression maximale obtenue en utilisant ce codage par rapport à un codage naïf . Prenant un exemple "KAIZOKOU NI ORE WA NARU" , On a les alphabets K,A,I,Z,O,U,N,R,E,W . Pour un codage naïf On attribue le code 0 à K , 1 à A , 10 à I,11 à Z ,100 à O,101 à U,110 à N,111 à R,1000 à E,1001 à W , on a utilisé 4 bits pour ce codage . En utilisant le codage Shannon-Fano on obtient la résultat suivant pour Z:111111,E:111110,W:11110,K:1110,I:110,U:101,N:100,R:011,A:010,O:00 on a utilisé 6 bits .

On conclut qu'en utilisant le codage de Shannon-Fano,On obtient une capacité des bits plus grande par rapport à un codage naïf .

V.1- Shannon-Fano VS Huffman

  • Dans l'encodage de Huffman, les sont construits de bas en haut en combinant de manière répétée les deux entrées communes dans la liste d’occurrence jusqu'à ce qu'il n'en reste plus que deux.
  • Dans l'algorithme de Shannon-Fano, la liste d’occurrence des caractères triés dans l'ordre décroissant, cette liste est divisée de manière récursive en deux liste.
  • Il a été prouvé que Huffman produisait toujours un code préfixe optimal alors que Shannon-Fano est légèrement moins efficace. Shannon-Fano, en revanche, est plus simple à implémenter.

VI- Bibliographie

https://fr.wikipedia.org/wiki/Codage_de_Shannon-Fano https://fr.wikipedia.org/wiki/Codage_entropique https://en.wikipedia.org/wiki/Information_theory https://fr.wikipedia.org/wiki/Compression_de_donn%C3%A9es https://www.youtube.com/watch?v=DSdTiFc3Aws
https://www.rocq.inria.fr/secret/Jean-Pierre.Tillich/enseignement/X2015/cours2.pdf

0 Cliquer pour recommander cet article