Le pathfinding(TIPE 2003/2004 de Math sup)
Livre d'or 
Le codage statistique :
Pour gagner de la place, les méthodes statistiques codent les valeurs les plus récurrentes sur un petit nombre de bits et réservent les grands codes aux valeurs les moins répandues. Cela paraît assez simple mais la mise en oeuvre de cette méthode est plus compliquée qu'il n'y paraît.
Prenons un exemple. Supposons que nous ayons un message avec cinq caractères différents A, B, C, D et E dont les fréquences d'apparition sont les suivantes :
| A : | 56 % |
| B : | 27 % |
| C : | 09 % |
| D : | 05 % |
| E : | 03 % |
On pourrait imaginer coder de la manière suivante : 0=>A, 1=>B, 00=>C, 01=>D et 10=>E.
Ce code, c'est sûr, vous fera gagner de la place, mais comment décoder l'extrait de code 00100110 ?
| AABAABBA ? |
| CBCBBA ? |
| CEABE ? |
| ADCBE ? |
| ADADE ? |
Ce codage pose donc un problème.
Essayons un autre code : 0=>A, 10=>B, 110=>C, 1110=>D et 1111=>E.
Décodons l'extrait de code 00100110. Cela donne AABAC. Cherchez une autre solution de décodage possible. Alors, vous n'en trouvez pas ? C'est normal, cette solution est unique. Nous avons trouvé ce codage par tâtonnement. Il marche, mais est-ce le meilleur code ?
Nous allons voir maintenant une méthode permettant de trouver un codage très efficace (même si elle ne donne pas toujours le codage optimal). Pour cela, prenons un exemple un peu plus complexe. Essayons de coder le message suivant : "JE SUIS, MON CHER AMI, TRES HEUREUX DE TE VOIR". Commençons par compter les occurrences de chaque caractère et de les classer par ordre décroissant du nombre d'apparition de chacun. Cela nous donne la liste suivante :
| _ | E | R | S | U | I | , | M | O | H | T | J | N | C | A | X | D | V |
| 9 | 7 | 4 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
("_" représente les espaces)
Il faut maintenant regrouper les caractères en deux ensembles de telle sorte que le total des nombres d'apparition de chacun des groupes soit le plus homogène possible. Il faut ensuite diviser ces groupes de la même manière jusqu'à obtenir les fréquences de départ. Le schéma suivant montre cette décomposition :
On a numéroté les branches en binaire. Il suffit de parcourir chaque branche pour trouver le code de chaque caractère.
Regardons maintenant l'efficacité de ce codage. Les caractères alphabétiques sont habituellement codés sur 8 bits (code ASCII). Notre message contenant 46 caractères, il serait codé de cette manière sur 46 x 8 = 368 bits. Néanmoins, 5 bits auraient suffi pour coder chaque caractère. On aurait utilisé ainsi 46 x 5 = 230 bits. En suivant notre codage statistique, nous utilisons (9 x 2) + (7 x 3) + (4 x 4) + (3 x 4) + (3 x 4) + (3 x 4) + (2 x 4) + (2 x 5) + (2 x 5) + (2 x 4) + (2 x 5) + (1 x 5) + (1 x 5) + (1 x 6) + (1 x 6) + (1 x 5) + (1 x 6) + (1 x 6) = 176 bits. Le taux de compression par rapport à un codage sur 5 bits est de 230/176 = 1,31.
La méthode utilisée ici pour trouver le codage est appelée algorithme de Shanon-Fano. On utilise plus souvent l'algorithme de Huffman, un peu plus complexe mais qui aboutit au même résultat. C'est ce dernier qui est utilisé dans la compression JPEG.