Section courante

A propos

Section administrative du site

Introduction

Les algorithmes de compression sont des techniques permettant de réduire la taille des données en éliminant la redondance, de sorte qu'elles prennent moins d'espace d'entreposage ou de bande passante lors de leur transmission. Ces algorithmes sont largement utilisés pour compresser des fichiers, des images, des vidéos, du texte, et bien plus. Ils sont essentiels dans les domaines du stockage de données, de la transmission de données sur internet, et des systèmes embarqués.

Les algorithmes de compression se divisent en deux grandes catégories :


Voici différents algorithmes en lien avec la compression.

Huffman

En parcourant les normes, la compression de Huffman est une technique vénérable, décrite pour la première fois par D. A. Huffman en 1952. Elle demeure néanmoins une technique de compression importante et utile et est spécifiée par la norme de CCITT Group 3 Facsimile, étant prise en charge par le format d'image TIFF. La norme du Group 3 spécifie en fait une variante de l'algorithme Huffman classique, mais est toujours généralement appelée compression Huffman. La compression Huffman code un flux d'octets en une séquence de codes binaires de longueur variable. Le principe derrière l'algorithme est de déterminer la fréquence statistique des différents symboles dans le flux d'entrée et de coder le message en utilisant des codes de bits courts pour les symboles les plus fréquents et des codes de bits plus longs pour les symboles moins fréquents. À titre d'illustration, considérons un fichier ASCII codé comme une séquence de codes 8 bits de longueur fixe. La lettre A est codée comme 01000001 (41h) et la lettre Z est codée comme 01011010 (5Ah). Cependant, en moyenne, la lettre A apparaît plus fréquemment que la lettre Z. Donc, si nous codons A avec un code court, disons 011, et Z avec un code plus long, disons 0111111, alors nous aurons réduit le nombre de bits nécessaires pour représenter un fichier. La technique, appelée codage de longueur variable comme codage de longueur variable, n'est pas ce que Huffman a réellement décrit. La contribution de Huffman était un algorithme pour déterminer l'ensemble de codes optimal pour un ensemble de données donné à coder. Cette situation se fait en ordonnant les symboles d'entrée par fréquence, puis en construisant un arbre binaire à partir d'eux. Le code bit pour un symbole donné est ensuite déterminé par le chemin d'accès à ce symbole dans l'arborescence. À chaque niveau, une branche gauche contribue 1 bit au codage des symboles et une branche droite contribue 0 bit. Lorsqu'un noeud terminal est atteint, le symbole d'entrée s'y trouvant est codé avec le motif binaire construit à partir du chemin vers ce symbole. Pendant le décodage, les bits sont lus dans le flux d'entrée et sont utilisés pour parcourir l'arborescence. Lorsqu'un noeud terminal est atteint, le symbole associé à ce noeud est émis vers le flux décodé. L'arbre réel, appelé arbre de Huffman, est construit de bas en haut, en commençant par tous les noeuds terminaux ordonnés en augmentant la fréquence. Les deux noeuds avec la fréquence la plus basse sont combinés pour former un noeud parent dont la fréquence est définie comme étant la somme des fréquences de ses deux noeuds enfants. Le processus est répété jusqu'à ce qu'un seul noeud, la racine de l'arbre, soit atteint. Notez que l'arborescence utilisée pour coder un flux de données est requise pour décoder la représentation compressée du flux de données. Deux problèmes avec la compression Huffman sont qu'elle nécessite deux passages sur un fichier, un pour déterminer la fréquence du symbole et un pour le codage réel, et le second problème c'est que la manipulation au niveau du bit requise de la représentation codée est plus coûteuse en calcul que l'octet de manipulation orientée. Le premier problème peut être résolu en supposant une distribution de fréquence de symboles standard et un ensemble de codes binaires, ce qui est le cas avec la norme Group 3 Facsimile Standard.

Algorithme

* Entrée : Liste de symboles avec leurs fréquences d'apparition
* Sortie : Code binaire de Huffman pour chaque symbole

MODULE Huffman(Symboles)
   * Initialiser une file de priorité Q avec tous les symboles et leurs fréquences
   BOUCLE TANT QUE taille de Q > 1 FAIRE
      Extraire le noeud x avec la plus petite fréquence de Q
      Extraire le noeud y avec la plus petite fréquence de Q (après x)
      Créer un nouveau noeud z avec :
         La fréquence de z ← fréquence de x + fréquence de y
         Le noeud x comme enfant gauche
         Le noeud y comme enfant droit
      Ajouter z dans Q
   FIN BOUCLE TANT QUE
   * Le seul noeud restant dans Q est la racine de l'arbre de Huffman

   BOUCLE POUR CHAQUE arbre de Huffman pour générer les codes FAIRE
      Initialiser un dictionnaire vide 'codes'
      BOUCLE POUR CHAQUE feuille (symbole) dans l'arbre FAIRE
         Assigner le code en fonction du chemin (0 pour gauche, 1 pour droite)
         Ajouter le symbole et son code dans 'codes'
      FIN BOUCLE POUR CHAQUE
   FIN BOUCLE POUR CHAQUE
   RETOURNE 'codes'

LZW (Lempel-Ziv-Welch)

L'algorithme de compression de données LZW, tirant son nom de l'abréviation de Lempel - Ziv - Welch, offre la possibilité d'effectuer une compression de données sans perte de données et a été créé par Abraham Lempel, Jacob Ziv et Terry Welch. La compression LZW est basé sur l'une des techniques du dictionnaire adaptatif. Le dictionnaire est créé pendant le codage des données. Donc, l'encodage peut être fait à la volée. Le dictionnaire n'a pas besoin d'être transmis. Le dictionnaire peut être construit à la réception à la volée. Si le dictionnaire déborde, nous devons le réinitialiser et ajouter un bit à chacun des mots de code. Choisir une taille de dictionnaire importante évite les débordements, mais réduit l'efficacité de la compression. Un dictionnaire contenant les symboles source est construit. Pour les images monochromes 8 bits, les 256 premiers mots du dictionnaire sont attribués aux niveaux de gris de 0 à 255 ou des palettes de couleurs RVB comme dans une image de format GIF. La partie restante du dictionnaire est remplie de séquences de niveaux de gris. La compression LZW fonctionne mieux lorsqu'elle est appliquée à des images monochromes et à des fichiers texte contenant du texte et/ou des motifs répétitifs.

Encodage

Pour la compression, un dictionnaire est initialisé pour contenir les chaînes à caractère unique correspondant à tous les caractères d'entrée possibles (et rien d'autre à l'exception des codes d'effacement et d'arrêt s'ils sont utilisés). L'algorithme fonctionne en parcourant la chaîne de caractères d'entrée pour rechercher des sous-chaînes de plus en plus longues jusqu'à trouver une chaîne ne figurant pas dans le dictionnaire. Lorsqu'une telle chaîne de caractères est trouvée, l'index de la chaîne de caractères moins le dernier caractère (c'est-à-dire la plus longue sous-chaîne de caractères du dictionnaire) est extrait du dictionnaire et envoyé à la sortie, et la nouvelle chaîne de caractères (y compris le dernier caractère) est ajoutée au dictionnaire avec le prochain code disponible. Le dernier caractère saisi est ensuite utilisé comme point de départ suivant pour rechercher des sous-chaînes de caractères. De cette manière, des chaînes de caractères de plus en plus longues sont enregistrées dans le dictionnaire et mises à disposition pour un codage ultérieur en tant que valeurs de sortie uniques. L'algorithme fonctionne mieux sur des données avec des modèles répétés, de sorte que les premières parties d'un message verront peu de compression. Cependant, à mesure que le message se développe, le taux de compression tend à atteindre le maximum asymptotiquement. Voici l'algorithme normalement utiliser pour se traitement :

MODULE Encodage(Source,Dictionnaire)
   Chaîne de caractères ← nulle
   I ← 0
   BOUCLE TANT QUE I ≤ LONGUEUR(Source) FAIRE
      C ← Source[I]
      I ← I + 1
      SI Chaîne de caractères + C est présent DANS Dictionnaire ALORS
         Chaîne de caractères ← Chaîne de caractères + C
      SINON
         ÉCRIRE Code de chaîne de caractères
         AJOUTER Chaîne de caractères + C DANS Dictionnaire
         Chaîne de caractères ← C
      FIN SI
   FIN BOUCLE TANT QUE

Décodage

Pour la décompression, l'algorithme de décodage fonctionne en lisant une valeur à partir de l'entrée codée et en sortant la chaîne de caractères correspondante à partir du dictionnaire initialisé. En même temps, il obtient la valeur suivante de l'entrée et ajoute au dictionnaire la concaténation de la chaîne venant d'être affichée et du premier caractère de la chaîne de caractères obtenue en décodant la valeur d'entrée suivante. Le décodeur passe ensuite à la valeur d'entrée suivante (étant déjà lue comme la valeur suivante dans la passage précédente) et répète le processus jusqu'à ce qu'il n'y ait plus d'entrée, la valeur d'entrée finale étant décodée sans ajout supplémentaire au dictionnaire. De cette manière, le décodeur construit un dictionnaire identique à celui utilisé par le codeur et l'utilise pour décoder les valeurs d'entrée ultérieures. Ainsi, le dictionnaire complet n'a pas besoin d'être envoyé avec les données codées; seul le dictionnaire initial contenant les chaînes de caractères uniques est suffisant (et est généralement défini à l'avance dans le codeur et le décodeur au lieu d'être explicitement envoyé avec les données codées).

MODULE Decodage(Source,Dictionnaire)
   Précédent ← Source[0]
   I ← 1
   BOUCLE TANT QUE I ≤ LONGUEUR(Source) FAIRE
      C ← Source[I]
      I ← I + 1
      SI C est présent DANS dictionnaire ALORS
         Chaîne de caractères ← Dictionnaire[C]
      SINON
         Chaîne de caractères ← Dictionnaire[Précédent]
         Chaîne de caractères ← Chaîne de caractères + C
      FIN SI
      ÉCRIRE Chaîne de caractères
      C ← Chaîne de caractères[0]
      AJOUTER Dictionnaire[Précédent] + C DANS Dictionnaire
      Précédent ← C
   FIN BOUCLE TANT QUE

PackBits

La compression PackBits est un schéma de compression de longueur d'exécution simple orienté octet ayant été initialement développé pour être utilisé dans le format de fichier image MacPaint et est l'un des nombreux schémas pris en charge par le format TIFF. L'algorithme PackBits code un flux d'octets en une série de paquets consistant en un octet d'index suivi d'un certain nombre d'octets de données. La façon la plus simple d'expliquer l'algorithme est de décrire le processus de décodage. Voici son algorithme :

BOUCLE JUSQU'A nombre d'octets souhaité a été décodé
   N ← octet suivant de l'entrée
   SI N < 0 ALORS
      Lisez l'octet suivant de l'entrée et répétez-le 1 à N fois.
   SINON
      Lire les N + 1 octets suivants de l'entrée.
   FIN SI
FIN BOUCLE


Dernière mise à jour : Dimanche, le 10 novembre 2024