Principe de l'entropie:
L’objectif à ce stade est de comprimer et stocker toute l’information dans le minimum de symboles, donc de place mémoire des ordinateurs. C’est une phase de compression conservatrice. Le codage proprement dit fait correspondre à un symbole ou à un ensemble de symboles un certain code. Il s’accompagne d’un modèle statistique calculant, de manière plus ou moins complexe, la probabilité d’apparition du symbole à coder. Ainsi, un symbole ayant une grande probabilité d’occurrence sera codé sur très peu de bits et inversement.
Algorithme d'Huffmann:
Il a été prouvé que l'algorithme d'Huffman est une des meilleures méthodes de codage à codes de longueur fixée(aujourd'hui, une méthode arithmétique dérivant d'Huffmann a été trouvée, mais cette méthode-ci est la plus simple à expliquer).
L’algorithme de Huffman consiste à construire progressivement un arbre binaire en partant des nœuds terminaux (vous comprendrez d'après les schémas).
- On sélectionne les deux symboles les moins probables, on crée deux branches dans l’arbre et on les étiquette par les deux symboles binaires 0 et 1.
- On actualise les deux listes en rassemblant les deux symboles utilisés en un nouveau symbole et en lui associant comme probabilité la somme des deux probabilités sélectionnées.
- On recommence les deux étapes précédentes tant qu’il reste plus d’un symbole dans la liste.
Théorème: « aucun mot du code ne doit être un préfixe d’un autre mot du code ». (explication dans l'exemple ci-dessous).
Prenons l’exemple d’une source ne pouvant prendre que six valeurs différentes et supposons connues les probabilités. Elles sont données dans le tableau suivant :
L’algorithme de Huffman fournit l’arbre binaire schématisé ci dessous :
On peut donc y remarquer qu'à chaque noeud (points d'intersections de chaques branches de l'arbre), est associé un nombre (ici 0.5 ; 0.32 ; 0.18 ; 0.1).
On peut observer que: 0.5=0.18+0.32 ; 0.32=0.17+0.15 ; 0.18=0.08+0.1 ; 0.1=0.06+0.04 ; comme le principe de l'algorithme l'explique.
Le bilan de l'arbre est:
Le schéma respecte bien le théorème des préfixe: le décodage des symboles se fait sans référence aux mots de code futurs.
C'est à dire que si le logiciel lit la séquence suivante: 11001110101110 ; il pourra en déduire quelle suite de symboles lui est associée sans ambiguïtés.
Nous ne développerons pas plus sur le sujet et préferons en revanche parler succintement du système de décompression.