 |
|
|
 |
TPE 2002 |  |
Site optimisé pour Internet Explorer 5 et
pour une résolution de 1024 x 768
|
 |
 |
 |
 |
 |
 |
|
D.A. Huffman a inventé en 1952, un algorithme de compression capable, à partir d'une analyse statistique des données, d'associer à celles les plus souvent présentes les codes les plus courts. Inversement, les données les plus rares se verront attribuer les codes les plus longs. Cet algorithme permet d'obtenir de bons résultats, mais il faut conserver entre la compression et la décompression, le dictionnaire des codes utilisés. La méthode Reprenons l'exemple précédant:
Cette image contient 30 pixels. Si l'on considère
qu'ils sont codés sur 3 octet, la taille de ce texte est de 30
x 3= 90 octet soit 720 bits. La table ci-dessous indique les fréquences
des valeurs du pixel de notre exemple. Nous pouvons remarquer que certaines
valeurs définissant un pixel apparaissent plus fréquemment
que d'autres.
Réalisation de l'algorithme suivant une méthode manuelle
Pour réaliser cet algorithme, on commence avec une nouvelle table, similaire à la précédente, on place les valeurs dans une première colonne et leur fréquence dans la seconde. Les données sont triées par ordre de fréquence décroissante. On construit ensuite le tableau, colonne par colonne, de gauche à droite. On effectue d'abord la somme des 2 fréquences les plus faibles. On reporte dans la colonne suivante toutes les fréquences en supprimant les deux plus faibles. Et en les remplaçant par leur somme. Ce nombre doit être positionné dans la colonne de sorte à respecter l'ordre décroissant. Chaque paire de l'ancienne colonne est annotée avec 0 pour la valeur la plus élevée et 1 pour la plus faible. On procède ainsi jusqu'à ce qu'il ait plus qu'un élément dans la colonne.
Légende : Fréq = Fréquance Cette première étape permet de constituer un arbre. L'arbre est constitué de nœuds et de feuilles. Tous les nœuds ont deux liens vers d'autres nœuds ou des feuilles. On dit qu'il est le père de deux fils. Le lien de gauche est étiqueté 0 et celui de droite 1. Ce type d'arbre s'appelle un arbre binaire car tous les nœuds ont deux fils. Le nœud le plus élevé s'appelle la racine. On trouve alors le code d'une lettre en partant de sa position dans l'arbre, en remontant vers la racine tout en notant de droite à gauche les 1 et 0 rencontrés. Cet algorithme revient donc à construire un arbre binaire. On note sur chaque nœud les sommes des fréquences des fils. Les feuilles représentent les valeurs avec leurs fréquences. La racine indique donc la somme des valeurs du texte. Chaque branche correspond soit à 0, soit à 1. Pour compresser l'image, il suffit pour chaque valeurs de parcourir l'arbre en partant de la feuille correspondant à la valeur voulue, et de remonter jusqu'à la racine. Une fois arrivé, on émet les bits 1 ou 0 correspondant au chemin parcouru.
Dans un fichier, les bits sont représentés par groupe de huit et forment des octets. Le résultat de la compression de notre exemple est donc le suivant :
|
|
