|
La compression de données - Compression Huffman |
| Article posté par serioussam Ce chapitre a pour but d?expliquer précisément le fonctionnement de la compression de Huffman semi-adaptatif et d?expliquer brièvement la compression adaptative. 1-Introduction : David A. Huffman en 1952 publie le résultat de ses recherches dans un article intitulé "A method for the construction of minimum redundancy codes" son algorithme qui permet de compresser les données sans perte. Son étude se fonde sur l'idée que certains caractères sont susceptibles d'apparaître plus souvent que d'autres dans un fichier, laissant la possibilité de les coder sur un nombre de bits plus restreint. Le codage Huffman est désormais un standard en matière de compression. Créé à la base pour des fichiers de texte, cette méthode a su séduire les concepteurs et est désormais adaptée à tout types de fichiers. L'algorithme de Huffman est une solution au problème de l'élaboration des codes comme il a été posé pour les algorithmes de codage statistique. 2-Principe : La compression de Huffman consiste à attribuer un nouveau code à chaque caractère. La taille de ce code va varier selon la fréquence d?apparition du caractère dans le fichier. Le codage de Huffman est un codage entropique (probabilités d?apparition d?un caractère) qui a la propriété d'être optimal car il donne la plus petite moyenne de longueur de code de toutes les techniques de codage statistique. Pour compresser, il va falloir choisir comme unité de codage le bit; car les caractères sont codés sur un octet qui lui-même est constitué de 8 bits. Donc pour pouvoir compresser, on devra pouvoir coder les caractères sur moins de 8 bits. D?où l?unité choisie. Pour que la compression soit efficace on se propose de recoder les caractères qui ont une occurrence très faible avec un grand nombre de bits et les caractères très fréquents seront codés sur une longueur binaire très courte (moins de 8 bits). En effet, certains caractères n?apparaissant que peu de fois auront un code plus long que la normale (8 bits) ce qui n?empêche pas la compression car ces caractères à « codes longs » (fréquence d?apparition basse) représentent par définition une petite partie du fichier, tandis que les caractères qui se verront attribuer un « code court » représentent eux une plus grande partie du fichier car leur fréquence d?apparition est forte. Ce qui signifie bien que cet algorithme soit basé sur la redondance des caractères dans un fichier, c?est à dire que le fait que certains caractères se répètent plus de fois que d?autres. Il va de soi que le code de chaque caractère doit être unique. Mais il faut de plus qu?un code ne soit pas le début d?un autre sinon il serait impossible de savoir à quel caractère appartient ce code. C?est pour cela que le codage de Huffman est « instantané », ce qui signifie qu'aucun code n'est le préfixe d'un autre. Cette propriété s'assure de l'unicité de décodage de chaque code. Par exemple : il ne peut avoir les codes ?100? et ?1001? en même temps, sinon dans ce cas faudra t-il décoder ?100? puis ?1? ou ?1001?. Sans cette propriété le système de codage ne serait pas fonctionnel. Toutes ces caractéristiques du codage de Huffman montrent qu?il faudra utiliser un système basé sur une structure arborescente appelée « arbres binaires ». 3- Algorithme de compression. Etapes de création d?un arbre de Huffman : -On calcule avec une première passe sur le fichier, les fréquences d?apparition des caractères. -On trie la table des fréquences par ordre croissant. -On réalise l?arbre binaire. -On codifie l?arbre en attribuant à chaque caractère un code binaire variable VCL (Variable Code Length). -On écrit une table de référence des codes de chaque caractère dans le fichier de sortie. -On compresse le fichier source en attribuant à chaque caractère un code binaire variable. Nous allons détailler chaque étape en compressant la phrase « LE PRESIDENT EST ENTRE DANS LA SALLE » (Pour plus de simplicité nous utiliserons que les majuscules). Voir le document huffman.ppt. Pour coder une lettre on part de celle-ci et on remonte jusqu?à la racine en relevant le « chemin », et pour décoder on part de la branche et on choisit son « chemin » en suivant les 0 ou 1 du code pour finalement arriver à la lettre décodée. Ainsi la lettre E la plus fréquente est codée sur 2 bits : 00, le caractère P le moins fréquent est codé sur 5 bits : 11111. On constate qu?ainsi on n?a pas besoin de dire quand le code est terminé puisqu?il est impossible de descendre plus bas quand on est arrivé à une feuille (code préfixé). La phrase compressée occupe alors (7*2 + 6*3 + 4*3 + 4*3 + 3*4 + 3*4 + 3*4 + 2*4 + 2*4 + 1*5 + 1*5) = 118 bits, au lieu de (36 * 8 ) = 288 bits, pour un gain de compression de ((288 ? 118 ) / 288 ) = 59%. Ce taux de compression diminue faiblement à cause de la table des codes de Huffman, indispensable pour la décompression. 5-Algorithme de décompression. Le programme va lire dans le fichier la table contenant le code de Huffman de chaque caractère ASCII, à partir des codes binaire, l?arbre de Huffman sera reconstruit en respectant notre conversion, 0 pour branche gauche et 1 pour branche droite et ce à partir de la racine. Après la lecture de la table, le contenu du fichier sera lu bit à bit en parcourant en parallèle l?arbre binaire, lorsque nous arrivons à une feuille, nous avons décodé un caractère, il suffit de regarder dans la table à quoi correspond le code de Huffman comme code ASCII. 6-Variante de la compression de Huffman : - Non adaptative : l?arbre est élaboré à partir d?une table des fréquences fixe ce qui fait qu?il est adapté à un seul type de donnée. - Semi adaptative : comme dans l?exemple, on lit une fois le fichier à compresser pour créer la table des fréquences, puis on s?en sert pour compresser le fichier. C?est la méthode la plus efficace mais elle présente l?inconvénient de nécessiter l?arbre que l?on devra introduire dans un en-tête (il est plus économique d?introduire les codes plutôt que l?arbre). - Adaptative : la table des fréquences est élaborée au fur et à mesure de la lecture du fichier et l?arbre est reconstruit à chaque fois. On réalise l?arbre avec les premiers caractères (que l?on ne compresse pas) et on s?en sert pour compresser les caractères suivants que l?on utilise aussi pour actualiser l?arbre etc. Elle est un peu moins efficace que la méthode semi adaptative mais le résultat final est souvent meilleur car elle ne nécessite pas le stockage de l?arbre, et de plus elle ne nécessite qu'une seule lecture du fichier. 7-Avantages et inconvénients. Inconvénients : La méthode de Huffman que nous avons étudiée demande d?effectuer deux passes de lecture sur le fichier à compresser, une passe pour établir la table des fréquences et une autre pour coder les caractères avec le code de Huffman. Sur des ordinateurs ou des appareils embarqués (appareils photo numérique?) de faible puissance, le temps de compression n?est pas négligeable. Cette variante de Huffman semi-adaptif possède ce gros inconvénient. Cette variante n?est pas optimale en taux de compression, en effet il est obligatoire de conserver sous différentes forme dans l?en-tête du fichier l?arbre de Huffman, pour des fichiers de faibles taille, il arrive que l?en-tête plus les données compressées dépassent la taille du fichier original. Cette variante peut être encore améliorée car il arrive que certains caractères soient très récurrents dans une partie du fichier et inexistant dans un autre partie, c?est le cas des fichiers exécutables. Néanmoins, la méthode de Huffman ne peut coder les données que sur un nombre entier de bits, alors qu'il est nécessaire, dans la plupart des cas, de coder sur un nombre fractionnaire de bits ( les fréquences ne sont généralement pas des puissances de 2), pour avoir une compression optimale. De plus la méthode de Huffman, utilisée avec des données de n bits, ne permet pas d'atteindre taux de compression supérieur à n/1 (chaque donnée de est au minimum codée sur 1 bit), donc pour les algorithmes habituels (les données sont des octets) un taux de 8/1. Ainsi, il est peu efficace sur les données présentant de grandes séquences d'éléments identiques, telles celles qui sont optimales pour le RLE. (en effet une image de 255 pixels blancs ne prendra que 16 bits (2 octets) en RLE, mais 256 bits avec Huffman) Enfin, il est aussi relativement gourmand en puissance de calcul, imposant au processeur de nombreuses manipulations sur un seul bit (n'utilisant pas la plus grande partie des capacités du processeur, qui fonctionne au moins en 8 bits). Avantages : Grâce à sa relative facilité d'utilisation et ses performances honorables, l'algorithme de Huffman est devenu un grand standard dans le domaine de la compression de données, et il est souvent utilisé dans les formats d'images compressées et, avec quelques améliorations, dans les programmes de compression (Zip, Arj, etc...). Avec Huffman on est presque sûr et certain de diminuer la taille d?un fichier. |
>> Vos commentaires [0]
|