Le codage de Shannon-Fano et Huffman 4

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 :

codage-arrowChaque 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 et Huffman.

Calcul

Bon commençons maintenant avec un peu de concret :

L’entropie est la quantité d’informations contenues dans un message, et se note de la manière suivante :

Entropie : I=log2(z)

z est ici le code décimal du message, et I l’entropie, notée en sh (Shannon) qui est une unité de mesure d’élément binaire.

Exemple : log2(32) = 5 sh, donc l’entropie de ce message est de 5 éléments binaires.

Un message peut contenir plusieurs symboles, la formule pour déterminer l’entropie dans un message à plusieurs symboles est très simple : I=log2(2^n)

Note: On utilise un log() base 2 car cela est adapté aux signaux binaires.

Si maintenant on veut calculer l’entropie moyenne par symbole dans un message nommée H :

H = I / n =- Σ pi * log2(pi) pour Σ allant de i=1 à b. pi étant la probabilité d’apparition d’un symbole.

Dans le cas ou l’apparition de symboles est équiprobable, pi = 1 / b et I = n*log2(b)

Mesurons maintenant la performance du codage de Shannon-Fano et de Huffman, que nous allons comparer. Il faut partir du principe que l’algorithme de Huffman est meilleur en performance de compression car, il est aussi bon que celui de Shannon-Fano, lorsque ce dernier est à son taux de compression maximum. Autrement dit, dans le meilleur des cas, Shannon-Fano sera aussi efficace que Huffman.

Les performances

Codage de Huffman :

Prenons par exemple, un cas ou les probabilités suivantes sont associées à des éléments :

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)

Maintenant nous allons passer à la détermination du code de chaque symbole.

huffman_diagBon, comme ça, on dirait que c’est compliqué, mais ce n’est pas le cas. En fait, on doit additionner les probabilités pour arriver à 1. A chaque fois qu’un branche rejoint l’autre, on lui associe le nombre 1,et quand une branche reste au même niveau, on lui associe le nombre 0.

Ensuite, pour la lecture du code, on part du résultat total de la somme ( notre 1 final ), et on découle jusqu’à arriver vers la probabilité de départ.Exemple : Ici le code du symbole de probabilité a1 sera égal à 00, car il y a deux zéros entre le 1 final et la probabilité a1. Pour a4, ça sera 101, pour a5, 110; etc …

Voici le tableau final trouvé :

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)

Bon, c’est presque fini, maintenant on arrive au calcul de 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 %.

Codage de Shannon-Fano :

Le plus dur est fait :p Le codage de Shannon-Fano ressemble énormément à Huffman, la seule différence réside dans le fait qu’on choisi arbitrairement les codes associés aux probabilités des symboles. Pour être plus clair, 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é.

shannon_diag

 

On choisit arbitrairement deux parties, pour quelles 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é tout les groupes, il suffit de tracer des lignes entre chaque probabilité ( de a1 à a7 ici), et de lire en partant de la droite, la ligne correspondante. Pour a7, on lit 1111.

On remarquera qu’ici on retrouve le même résultat qu’avec la méthode de Huffman, mais ceci, parce que nous avons déterminé à chaque fois les deux blocs étant les plus égaux l’un envers l’autre. Si l’évaluation est mauvaise, on trouvera forcément un résultat inférieur à le méthode de Huffman, qui est donc plus performante.

J’espère que cette petite introduction pourra aider certains à comprendre. Je vous invite à me laisser un commentaire, si vous voyez une erreur, ou tout simplement pour des questions, ou autre.

 

4 thoughts on “Le codage de Shannon-Fano et Huffman

  1. Répondre Batfly mai 12, 2015 15 h 01 min

    Je bloqué dés le premier tableau:
    Comment ces probabilité sont calculé? Je veux dire: j’ai une série de donné (ao,a1,a2,a3….), et je dois avant de commencer Huffman, calculer la « probabilité » de ces symboles?

    Ça veux dire quoi? la probabilité de trouver un symbole « a0″ si on pioche au hasard un symbole dans la base de donné? Je trouve ça absurde car l’ordre des symboles est important et il n’y a donc pas lieu d’y mettre de l’aléatoire! Mais si ça marche, il doit y avoir une raison, et une méthode très particulière pour le calculer.

    J’ai beau chercher, même dans les sites anglophone, je ne trouve rien!

    Merci!

    • Répondre Alexandre mai 13, 2015 8 h 15 min

      Bonjour,

      La probabilité associée à chaque élément est son estimation de fréquence d’apparition dans le message (on remarque que la somme de toutes les probabilités font 1). Après, j’imagine qu’elle est calculée selon le langage du message, le type de message, etc … je n’ai fait qu’appliquer ce principe et j’ai donc choisi arbitrairement ces poids. (ici associés à la probabilité).

      Ici l’ordre n’a rien à voir, puisqu’on s’intéresse aux symboles qui le composent un par un.

      Par contre l’ordre dans le déroulement de l’arbre se fait normalement de bas en haut (des plus petites probabilités aux plus grandes), en associant deux à deux les symboles, jusqu’à n’en avoir plus qu’un. Puis on lit les branches en partant de ce symbole final et on compose les codes binaires associés (0 pour les branches stagnantes, et 1 pour les branche de jonctions). Ce n’est pas tout à fait ce que j’ai fait dans mon exemple.

  2. Répondre Glen nov 24, 2017 16 h 42 min

    Merci pour les méthodes, l’article est clair et bien expliqué !

  3. Répondre Mohamed fév 9, 2018 19 h 12 min

    Bonjour
    Jai besoin script matlab pour shannon fano
    Symbol=[x1 x2 x3 x4 x5 x6]
    P=[0.3 0.25 0.2 0.12 0.08]
    Merci

Laisser un commentaire