Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Classe de première SI Codage de Huffman Table des matières 1. Le principe......

Classe de première SI Codage de Huffman Table des matières 1. Le principe........................................................................................................................................2 2. L'Algorithme de compression de Huffman......................................................................................2 2.1. Convention de codage binaire...................................................................................................2 2.2. Codage à taille fixe, à taille variable.........................................................................................3 2.3. Le codage à taille variable........................................................................................................4 3. L'algorithme de Huffman..................................................................................................................4 3.1. Les arbres binaires....................................................................................................................5 3.2. Implémentation de l'algorithme de Huffman............................................................................5 3.3. Exemple....................................................................................................................................6 3.4. Code source...............................................................................................................................9 Le codage de Huffman est une méthode de compression statistique de données qui permet de réduire la longueur du codage d'un alphabet. Le code de Huffman (1952) est un code de longueur variable optimal, c'est-à-dire tel que la longueur moyenne d'un texte codé soit minimale. On observe ainsi des réductions de taille de l'ordre de 20 à 90%. 5-huffman.odt 1 Classe de première SI 1. Le principe Le principe de l'algorithme de Huffman consiste à recoder les octets rencontrés dans un ensemble de données source avec des valeurs de longueur binaire variable. L'unité de traitement est ramenée au bit. Huffman propose de recoder les données qui ont une occurrence très faible sur une longueur binaire supérieure à la moyenne, et recoder les données très fréquentes sur une longueur binaire très courte. Ainsi, pour les données rares, nous perdons quelques bits regagnés pour les données répétitives. Par exemple, dans un fichier ASCII le "w" apparaissant 10 fois aura un code très long: 0101000001000. Ici la perte est de 40 bits (10 x 4 bits), car sans compression, il serait codé sur 8 bits au lieu de 12. Par contre, le caractère le plus fréquent comme le "e" avec 200 apparitions sera codé par 1. Le gain sera de 1400 bits (7 x 200 bits). On comprend l'intérêt d'une telle méthode. De plus, le codage de Huffman a une propriété de préfixe : une séquence binaire ne peut jamais être à la fois représentative d'un élément codé et constituer le début du code d'un autre élément. Si un caractère est représenté par la combinaison binaire 100 alors la combinaison 10001 ne peut être le code d'aucune autre information. Dans ce cas, l'algorithme de décodage interpréterait les 5 bits comme une succession du caractère codé 100 puis du caractère codé 01. Cette caractéristique du codage de Huffman permet une codification à l'aide d'une structure d'arbre binaire. 2. L'Algorithme de compression de Huffman Cet algorithme est "non-destructif", c'est à dire qu'il compresse les données sans introduire de perte d'information, de sorte que le fichier décompressé est une copie conforme de l'original. Le codage employé est dit "entropique", c'est à dire qu'il se base sur les statistiques d'apparition des différents octets du fichier, et "à taille variable", c'est à dire que chaque octet est codé selon une suite de bits, dont la taille diffère selon l'octet. Pour comprendre en quoi un codage "entropique" peut nous permettre de compresser un fichier, nous commençons cette présentation par un rappel sur le principe du stockage d'informations en binaire. 2.1. Convention de codage binaire On code un nombre entier compris entre 0 et 255 par une séquence de 8 chiffres binaires (binary digits, ou "bits" en anglais, valant 0 ou 1), encore appelée octet. A priori, il suffit pour cela de se donner une table de correspondance du genre: ... ... 138 10001010 139 10001011 ... ... La correspondance peut être quelconque, du moment qu'à chaque entier entre 0 et 255 est affecté un code binaire et un seul. Une fois une correspondance fixée, il suffit de la prendre comme convention. 5-huffman.odt 2 Classe de première SI En pratique, la convention qui a été choisie est celle de la représentation en base 2 qui a le mérite d'être naturelle et logique. Dans la table ci dessus, 10001010 est la représentation en base 2 de 138. C'est la manière de noter les chiffres que nous aurions adoptée si nous n'avions que deux doigts au lieu de dix. L'octet défini selon cette convention est l'unité de base de stockage des données. Tout fichier informatique est une suite d'octets rangés selon un ordre bien défini. La taille du fichier est simplement le nombre d'octets qui le constituent. Le kilo-octet (Ko) correspond à 1024 ( et non pas 1000) octets, le méga-octet (Mo) à 1024*1024 octets. 2.2. Codage à taille fixe, à taille variable La problématique de la compression "entropique" de données repose sur une AUTRE manière de coder les chiffres, peut-être moins logique mais plus judicieuse, de telle manière que la taille du même fichier recidé selon la nouvelle convention, serait MOINS GRANDE? Dans les textes longs, les lettres n’apparaissent pas avec la même fréquence. Ces fréquences varient suivant la langue utilisée. En français, les lettres les plus rencontrées sont dans l’ordre : E S A I N T R U L O D C P M V Q G F H B X J Y Z K W avec les fréquences (souvent proches et dépendant de l’échantillon utilisé) : E S A I N T R U L O D 14.69% 8.01% 7.54% 7.18% 6.89% 6.88% 6.49% 6.12% 5.63% 5.29% 3.66% A titre d'exemple, voici l'analyse d'un contenu d'octets du fichier Wordpad.exe. Dans ce tableau, en abscisse comme en ordonnée sont portées les valeurs possibles d'un octet donné (donc 0 ... 255). Sur la diagonale, à l'abscisse et ordonnée correspondante la taille du cercle est proportionnelle au nombre d'octets ayant cette valeur dans le fichier. Valeur Nombre Fréquence 0 71891 34.4% 2 1119 0.53% 128 1968 0.94% 130 79 0.038% 255 10422 4.99% On voit clairement que les valeurs 0, 128 et 255 sont nettement plus fréquentes que les autres! L'idée générale du codage entropique est la suivante: On va décider d'une convention de codage "à taille variable", qui représente une valeur fréquente PAR UN PETIT NOMBRE DE BITS, et une valeur peu fréquente par un grand nombre de bits. 5-huffman.odt 3 Classe de première SI Par exemple, 0 sera maintenant représenté par la séquence "11" (anciennement "00000000"), 128 par "1011010" (anciennement "10000000"), 255 par "0100" (anciennement "11111111"), etc... Étant donné que 0 représente à lui seul un tiers du fichier, on a gagné une place considérable en le codant sur deux bits au lieu de huit ! Et idem pour les autres valeurs fréquentes... 2.3. Le codage à taille variable Comment décoder le fichier compressé ? Supposons que nous décidons d'une convention de code à taille variable, qui fait correspondre, entre autres, les valeurs suivantes : 0 "11" 2 "11010" 12 "00" 127 "0111100" 255 "0100" Supposons alors que nous ayons à décoder la séquence : 1101000111100 Plusieurs interprétations sont possibles : 1101000111100 = 11 0100 0111100 = 0 255 127 1101000111100 = 11010 00 11 11 00 = 2 12 0 0 12 Avec plusieurs possibilités équivalentes, on est incapable de retranscrire le code initial. Le problème qui s'est posé ici est que CERTAINS CODES sont le DEBUT D'AUTRES CODES. Ici, "11" est le code du nombre 0, mais c'est aussi le début de "11010", code du nombre 2. D'où l'ambiguïté. On appelle "code-préfixe" un codage dans lequel aucun code n'est le début d'un autre. Pour qu'il n'y ait aucune ambiguïté au moment du décodage, il nous faut absolument un code- préfixe. 3. L'algorithme de Huffman L'algorithme de Huffman génére un code-préfixe à taille variable, à partir de la table des fréquences d'une suite de valeurs. 5-huffman.odt 4 Classe de première SI 3.1. Les arbres binaires On appelle arbre binaire une collection d'éléments (les "nœuds") dans laquelle chaque nœud est connecté à 0 ou 2 autres nœuds. A chaque nœud on peut associer une ou plusieurs valeurs. Voici un exemple d'arbre binaire: L’élément supérieur de l'arbre (le "9") est la racine; tandis que les nœuds terminaux sont les feuilles. 3.2. Implémentation de l'algorithme de Huffman Soit un fichier à compresser. Au préalable, dresser la table des fréquences (Clé / Valeur) ci- contre. Dans ce tableau, Fréquence(i) désigne le nombre d'octets du fichier ayant la valeur i. Clé Valeur 0 Fréquence(0) 1 Fréquence(1) ... 255 Fréquence(255) Pour chaque Clé associée à une fréquence non-nulle, créer un nœud terminal, et affectez lui le couple (Clé, Valeur). Chaque nœud terminal créé représente autant d'arbre binaire à élément unique. Itérer : 1. Classer chaque arbre binaire par Valeur croissante; 2. Retirer de la liste les deux arbres binaires ayant les Valeurs les plus faibles. Insérer, à la place, un nouvel arbre binaire dont la racine pointe sur les racines des deux arbres binaires supprimés. A ce nouvel arbre binaire, affectez lui pour Valeur, la somme des Valeurs des deux arbres précédents. Inutile de lui affecter une Clé. 3. Recommencer en 1 jusqu'à ce qu'il ne reste plus qu'un arbre binaire unique. On construit ainsi un arbre binaire dans lequel les nœuds terminaux sont les éléments de notre table des fréquences. Pour connaître le Code de Huffman associé à chaque Clé, il suffit de descendre l'arbre, en partant de la racine, pour rejoindre la Clé voulue. A chaque embranchement, on compte "0" si l'on est passé à gauche, et "1" si l'on est passé à droite. 5-huffman.odt 5 Classe de première SI 3.3. Exemple Supposons que notre uploads/S4/ 5-huffman.pdf