Compression de données

La compression de données ou codage de source est l'opération informatique qui consiste à transformer une suite de bits A en une suite de bits B plus courte, contenant les mêmes informations, en utilisant un algorithme spécifique.



Catégories :

Compression de données

Recherche sur Google Images :


Source image : datacompression.free.fr
Cette image est un résultat de recherche de Google Image. Elle est peut-être réduite par rapport à l'originale et/ou protégée par des droits d'auteur.

Page(s) en rapport avec ce sujet :

  • utilisent la compression sans perte (RLE, LZW, Huffman).... But : diminuer le nombres de bits utilisés pour le codage des caractères habituels dans un.... La compression de données est nommée à prendre un rôle toujours plus important en ... (source : mp01.free)
  • ... L'éventail des algorithmes de compression de données est particulièrement large.... une compression de données en donnant la possibilité une légère perte d'information.... Pour avoir un bon codage des données, le code doit vérifier les ... (source : revue-eti)
  • données que sont les méthodes de compression sans perte et avec perte.... La compression de données est le processus qui consiste `a convertir des .... Pour déterminer le codage d'une lettre nous partons de la racine de ... (source : candiulb)

La compression de données ou codage de source est l'opération informatique qui consiste à transformer une suite de bits A en une suite de bits B plus courte, contenant les mêmes informations, en utilisant un algorithme spécifique. C'est une opération de codage, c'est-à-dire changer la représentation de l'information, dans l'objectif de rendre la représentation compressée plus courte que la représentation originale. La décompression est l'opération inverse de la compression.

Avec un algorithme de compression sans perte, la suite de bits obtenue après les opérations de compression et de décompression est strictement semblable à l'originale. Les algorithmes de compression sans perte sont utilisés pour de nombreux types de données surtout des documents, des fichiers exécutable ou des fichiers texte.

Avec un algorithme de compression avec pertes, la suite de bits obtenue après les opérations de compression et de décompression est différente de l'originale, mais l'information reste sensiblement la même. Les algorithmes de compression avec perte sont utilisés pour les images, le son et la vidéo.

Les formats de données tels que Zip, RAR, Gzip, ADPCM, MP3 et JPEG utilisent des algorithmes de compression de données.

La théorie de la compression de donnée est issue de la théorie de l'information.

Types de compression

Compression sans perte

La compression est dite sans perte quand il n'y a aucune perte de données sur l'information d'origine. Il y a tout autant d'information après la compression qu'avant, elle est uniquement réécrite d'une manière plus concise (c'est par exemple le cas de la compression gzip pour n'importe quel type de données ou du format PNG pour des images synthétiques destinées au Web[1]). La compression sans perte est dite aussi compactage.

L'information à compresser est vue comme la sortie d'une source de symboles qui produit des textes finis selon certaines règles. L'objectif est de diminuer la taille moyenne des textes obtenus après la compression tout en ayant la possibilité de retrouver précisément le message d'origine (on trouve aussi l'expression codage de source en opposition au codage de canal qui sert à désigner le codage correcteur d'erreurs).

Il n'existe pas de technique de compression de données sans perte universelle, qui pourrait compresser n'importe quel fichier : si une technique sans perte compresse au moins un fichier, alors elle en «grossit» aussi au moins un.

Les formats de fichier de compression sans perte sont connus grâce à l'extension ajoutée à la fin du nom de fichier («nomdefichier. zip» par exemple), d'où leur appellation particulièrement abrégée. Les formats les plus courants sont :

Les standards ouverts les plus courants sont décrits dans plusieurs RFC :

Compression avec pertes

La compression avec pertes ne s'applique qu'aux données «perceptibles», généralement sonores ou visuelles, qui peuvent subir une modification, quelquefois importante, sans que cela ne soit perceptible par un humain. La perte d'information est irréversible, il est impossible de retrouver les données d'origine après une telle compression. La compression avec perte est pour cela quelquefois nommée compression irréversible ou non conservative.

Cette technique est fondée sur une idée simple : seul un sous-ensemble particulièrement faible de l'ensemble des images envisageables (à savoir celles qu'on obtiendrait par exemple en tirant les valeurs de chaque pixel par un générateur aléatoire) possède un caractère exploitable et informatif pour l'œil. Ce sont par conséquent ces images-là qu'on va s'attacher à coder de façon courte. Dans la pratique, l'œil a besoin pour identifier des zones qu'il existe des corrélations entre pixels voisins, c'est-à-dire qu'il existe des zones contiguës de couleurs voisines. Les programmes de compression s'attachent à découvrir ces zones ainsi qu'à les coder de la façon aussi compacte que envisageable. La norme JPEG 2000, par exemple, arrive le plus souvent à coder des images photographiques sur 1 bit par pixel sans perte visible de qualité sur un écran, soit une compression d'un facteur 24 à 1.

Puisque l'œil ne perçoit pas obligatoirement l'ensemble des détails d'une image, il est envisageable de diminuer la quantité de données de telle sorte que le résultat soit particulièrement ressemblant à l'original, ou alors semblable, pour l'œil humain. La problématique de la compression avec pertes est d'identifier les transformations de l'image ou du son qui permettent de diminuer la quantité de données tout en préservant la qualité perceptible.

De même, seul un sous-ensemble particulièrement faible de sons envisageables est exploitable par l'oreille, qui a besoin de régularités génèrant elles-mêmes une redondance (coder avec fidélité un bruit de souffle n'aurait pas grand intérêt). Un codage éliminant cette redondance et la restituant à l'arrivée reste par conséquent acceptable, même si le son restitué n'est pas en tout point semblable au son d'origine.

On peut distinguer trois grandes familles de compression avec perte :

Les formats MPEG sont des formats de compression avec pertes pour les séquences vidéos. Ils incluent à ce titre des codeurs audio, comme les célèbres MP3 ou AAC, qui peuvent idéalement être utilisés indépendamment, et évidemment des codeurs vidéos — le plus souvent simplement référencés par la norme dont ils dépendent (MPEG-2, MPEG-4), mais aussi des solutions pour la synchronisation des flux audio et vidéo, et pour leur transport sur différents types de réseaux.

Compression presque sans perte

Les méthodes de compression sans perte significative sont un sous-ensemble des méthodes de compression avec perte, quelquefois distinguées de ces dernières. La compression sans perte significative peut être vue comme un intermédiaire entre la compression conservative et la compression non conservative, dans le sens ou elle sert à conserver toute la signification des données d'origine, tout en éliminant une partie de leur information.

Dans le domaine de la compression d'image, la distinction est faite entre la compression sans perte (parfaite au bit près ou bit-perfect) et la compression sans perte significative (parfaite au pixel près ou pixel-perfect). Une image compressée presque sans perte (à ne pas confondre avec une image compressée avec peu de pertes) peut être décompressée pour obtenir les pixels de sa version non-compressée comme une copie conforme. Elle ne peut par contre pas être décompressée pour obtenir sa version non compressée totalement comme une copie conforme (les métadonnées peuvent être différentes).

Techniques de compression sans perte

Parmi les algorithmes de compression presque sans perte, on retrouve la majorité des algorithmes de compression sans perte spécifiques à un type de données spécifique. A titre d'exemple, JPEG-LS sert à compresser presque sans perte du Windows bitmap et Monkey's Audio sert à compresser sans perte les données audio du wave PCM : il n'y a pas de perte de qualité, l'image et le morceau de musique sont précisément ceux d'origine.

Les algorithmes tels que Lempel-Ziv ou le codage RLE consistent à remplacer des suites de bits utilisées plusieurs fois dans un même fichier. Dans l'algorithme de codage de Huffman plus la suite de bits est utilisée fréquemment, plus la suite qui la remplacera sera courte.

Les algorithmes tels que la transformée de Burrows-Wheeler sont utilisés avec un algorithme de compression. De tels algorithmes modifient l'ordre des bits de façon à augmenter l'efficacité de l'algorithme de compression, mais sans compresser par eux-mêmes.

Codage par répétition

Codage RLE

Article détaillé : Run-length encoding.

Les lettres RLE signifient run-length encoding. C'est un mode de compression parmi les plus simples : toute suite de bits ou de caractères semblables est remplacée par un couple (nombre d'occurrences ; bit ou caractère répété).
Exemple : AAAAAAAAZZEEEEEER donne : 8A2Z6E1R, ce qui est bien plus court.

Compression CCITT

Article détaillé : Compression CCITT.

C'est une compression d'images utilisée pour le fax, standardisée par des recommandations de l'Union internationale des télécommunications (anciennement nommée CCITT). Elle est de type RLE (on code les suites horizontales de pixels blancs et de pixels noirs) et peut-être bidirectionnelle (on déduit une ligne de la précédente). Il existe plusieurs types de compressions ("groupes") suivant l'algorithme utilisé et le nombre de couleurs du document (monochrome, niveau de gris, couleur).

Deux compressions existent, celle du Groupe 3 (recommandation ITU T. 4) et celle du Groupe 4 (recommandation ITU T. 6), utilisées pour les fax :

Ceci est théorique! En fait plus de symboles seront à transmettre, mais envoyer une page blanche est quand même bien plus rapide en Groupe 4 que en Groupe 3.

Codage entropique

Article détaillé : Codage entropique.

Codage de Huffman

Article détaillé : Codage de Huffman.

L'idée qui préside au codage de Huffman est voisine de celle utilisée dans le code Morse : coder ce qui est habituel sur peu de place, et coder par contre sur des séquences plus longues ce qui revient rarement (entropie). En morse le «e», lettre particulièrement fréquente, est codé par un simple point, le plus bref de l'ensemble des signes.

L'originalité de David A. Huffman est qu'il apporte un procédé d'agrégation objectif servant à former son code par conséquent qu'on possède les statistiques d'utilisation de chaque caractère.

Le Macintosh d'Apple codait les textes dans un dispositif inspiré de Huffman : les 15 lettres les plus habituelles (dans la langue utilisée) étaient codées sur 4 bits, et la 16e combinaison était un code d'échappement indiquant que la lettre était codée en ASCII sur les 8 bits suivants. Ce dispositif permettait une compression des textes voisine en moyenne de 30 % à une époque où la mémoire était extrêmement chère comparé aux prix actuels (compter un facteur 1000).

Le défaut du codage Huffman est qu'il doit connaître la fréquence des caractères utilisés dans un fichier avant de choisir les codes optimaux. Et il doit par conséquent lire tout le fichier avant de comprimer. Une autre conséquence est que pour décomprimer il faut connaître les codes et par conséquent la table, qui est ajoutée devant le fichier, autant pour transmettre que stocker, ce qui diminue la compression, en particulier pour les petits fichiers. Ce problème est éliminé par le codage Huffman adaptatif, qui modifie sa table au fil des choses. Et peut par conséquent démarrer avec une table de base. Habituellement il débute avec les caractères à même probabilité.

Codage arithmétique

Article détaillé : Codage arithmétique.

Le codage arithmétique est assez identique au codage de Huffman en ceci qu'il associe aux motifs les plus probables les codes les plus courts (entropie). Contrairement au codage de Huffman qui produit au mieux des codes de 1 bit, le codage arithmétique peut produire des codes vides. Le taux de compression obtenu est donc meilleur.

Codage par dictionnaire

Lempel-Ziv 1977 (LZ77)

Article détaillé : LZ77.

La compression LZ77 remplace des motifs récurrents par des références à leur première apparition.

Elle donne de moins bons taux de compression que d'autres algorithmes (PPM, CM), mais a le double avantage d'être rapide et asymétrique (c'est-à-dire que l'algorithme de décompression est différent de celui de compression, ce qui peut être exploité pour avoir un algorithme de compression performant et un algorithme de décompression rapide).

LZ77 est surtout la base d'algorithmes répandus comme Deflate (ZIP, Gzip) ou LZMA (7-Zip)

Lempel-Ziv 1978 et Lempel-Ziv-Welch (LZ78 et LZW)

Article détaillé : LZ78.
Article détaillé : Lempel-Ziv-Welch.

LZW est basée sur la même méthode, mais Welch a constaté que, en créant un dictionnaire d'origine de l'ensemble des symboles envisageables, la compression était perfectionnée puisque le décompresseur peut recréer le dictionnaire d'origine et ne doit par conséquent pas le transmettre ni envoyer les premiers symboles. Elle a été brevetée par UNISYS et ne pouvait par conséquent être utilise librement dans l'ensemble des pays jusqu'à l'expiration du brevet en 2003. Elle sert dans les modems, mais UNISYS s'est engagé à vendre une licence à tout fabricant avant d'être acceptée comme norme de compression internationale pour les modems.

La compression Lempel-Ziv-Welch est dite de type dictionnaire. Elle est basée sur le fait que des motifs se retrouvent plus fréquemment que d'autres et qu'on peut par conséquent les remplacer par un index dans un dictionnaire. Le dictionnaire est construit dynamiquement selon les motifs rencontrés.

Codage par modélisation de contexte

Prédiction par reconnaissance partielle (PPM)

La prédiction par reconnaissance partielle se base sur une modélisation de contexte pour évaluer la probabilité des différents symboles. En connaissant le contenu d'une partie d'une source de données (fichier, flux…), un PPM est capable de deviner la suite, avec plus ou moins de précision. Un PPM est parfois utilisé en entrée d'un codage arithmétique par exemple.

La prédiction par reconnaissance partielle donne généralement de meilleurs taux de compression que des algorithmes à base de Lempel-Ziv, mais est sensiblement plus lente.

Pondération de contextes (CM)

Article détaillé : Pondération de contextes.

La pondération de contextes consiste à utiliser plusieurs prédicteurs (par exemple des PPM) pour obtenir l'estimation la plus fiable envisageable du symbole à venir dans une source de données (fichier, flux…). Elle peut être basiquement réalisée par une moyenne pondérée, mais les meilleurs résultats sont obtenus par des méthodes d'apprentissage automatique comme les réseaux de neurones.

La pondération de contextes est particulièrement performante en termes de taux de compression, mais est d'autant plus lente que le nombre de contextes est important.

Actuellement, les meilleurs taux de compression sont obtenus par des algorithmes liant pondération de contextes et codage arithmétique, comme PAQ.

Transformée de Burrows-Wheeler (BWT)

Article détaillé : Transformée de Burrows-Wheeler.

Il s'agit d'un mode de réorganisation des données et non un mode de compression. Il est essentiellement conçu pour favoriser la compression de texte en langue naturelle, mais il est aussi utilisable pour compresser n'importe quelles données binaires. Cette transformation, qui est totalement réversible, effectue un tri sur l'ensemble des rotations du texte source, ce qui tend à regrouper les caractères semblables ensemble en sortie, ce qui fait qu'une compression simple appliquée aux données produites permet fréquemment une compression particulièrement efficace.

Techniques de compression avec pertes

La compression avec pertes ne s'applique que sur des données perceptuelles (audio, image, vidéo), et s'appuie sur les caractéristiques du système visuel ou du système auditif humain pour ses stratégies de réduction de l'information. Les techniques sont par conséquent spécifiques à chaque média. Ces techniques ne sont pas utilisées seules mais sont combinées pour apporter un dispositif de compression performant.

Sous-échantillonnage

En image et en vidéo, il est habituel d'effectuer un sous-échantillonnage spatial des composantes de chrominance. Le dispositif visuel humain étant plus sensible aux variations de luminance que de couleur, la suppression d'une partie importante de l'information couleur n'est que peu visible[2].

Quantification

Article détaillé : Quantification (signal) .

La quantification est l'étape principale dans la réduction de l'information. C'est sur la quantification qu'on joue quand on souhaite atteindre un débit cible, le plus souvent en utilisant un modèle débit-distorsion.

Lors d'un codage par transformation (ondelettes ou DCT par exemple), la quantification s'applique sur les cœfficients dans l'espace transformé, en réduisant leur précision.

Taux de compression

Article détaillé : Taux de compression de données.

Le taux de compression est la différence entre la taille de A et celle de B, exprimée en %, ou le 100% est la taille de A. exemple :

taille A : 550, taille B : 250, différence = 300. taux de compression = 300 / 550 = 54%.

L'algorithme utilisé pour transformer A en B est conçu pour obtenir un résultat B de taille inférieure à A. Il peut paradoxalement produire quelquefois un résultat de taille supérieure.

Codage conjoint source-canal

Article détaillé : Codage conjoint source-canal.

Notes

  1. Ces 2 types de compressions gzip et PNG sont libres et non soumis à un brevet.
  2. Douglas A. Kerr, Chrominance Subsampling in Digital Images 2009.

Bibliographie

Voir aussi

Liens externes

Recherche sur Amazone (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Compression_de_donn%C3%A9es.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 07/04/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu