Compression de données
14665
31492707
2008-07-11T12:53:54Z
JAnDbot
127921
robot Ajoute: [[fa:فشردهسازی دادهها]], [[tr:Veri sıkıştırma]], [[uk:Стиснення даних]]
La '''compression de données''' traite de la manière dont on peut réduire l'espace nécessaire à la représentation d'une certaine
[[Théorie de l'information#Mesure de la quantité d'information|quantité d'information]]. Elle a donc sa place aussi bien lors de la transmission que lors du stockage des données. Elle fait partie des applications de la [[théorie de l'information]].
On peut classifier les méthodes de compressions en deux types, '''compression avec perte''' — également dite ''non conservative'' — et '''compression sans perte'''.
== Compression sans perte ==
La compression est dite ''sans perte'' lorsqu'il n'y a aucune perte de données sur l'information d'origine. Il y a autant d'information après la compression qu'avant, elle est seulement 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 [[Portable_Network_Graphics|PNG]] pour des images synthétiques destinées au [[World Wide Web|Web]]<ref>Ces 2 types de compressions gzip et PNG sont libres et non soumis à un brevet.</ref>). 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. Le but est de réduire la taille moyenne des textes obtenus après la compression tout en ayant la possibilité de retrouver exactement le message d'origine (on trouve aussi la dénomination ''codage de source'' en opposition au ''codage de canal'' qui désigne le codage correcteur d'erreurs).
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 dénomination très abrégée. Les formats les plus courants sont :
<!-- Tri par ordre alphabétique -->
* [[7z]]
* [[ACE (format de fichier)|ace]]
* [[ARC (format de fichier)|arc]]
* [[ARJ (logiciel)|arj]]
* bz, [[bzip2|bz2]] ([[Tar (informatique)|tar]] peut être utilisé pour créer les archives de ce type)
* [[CAB (format de fichier)|CAB]], utilisé par Microsoft
* [[gzip]], gz (qui est un fichier à une seule entrée, [[Tar (informatique)|tar]] peut être utilisé pour créer les archives de ce type)
* [[KGB Archiver|KGB]]
* [[lzh]]
* [[RAR (format de fichier)|rar]]
* [[Compress|Z]] (surtout sous [[Unix]])
* [[ZIP (format de fichier)|Zip]]
* [[zoo]]
* [[FLAC]] (pour les flux audio)
Les standards ouverts les plus courants sont décrits dans plusieurs [[RFC]]s :
* RFC 1950 (ZLIB, flux de données compressées)
* RFC 1951 (système de compression par blocs « DEFLATE », utilisé par zip et gz)
* RFC 1952 (format de fichier compressé GZIP)
Sur les limites de la compression sans perte, voir [[Paradoxe du compresseur]].
===Codage RLE===
{{Article détaillé|run-length encoding}}
Les lettres '''RLE''' signifient ''run-length encoding''. Il s'agit d'un mode de compression parmi les plus simples : toute suite de bits ou de caractères identiques est remplacée par un couple (nombre d'occurrences ; bit ou caractère répété).
===Compression CCITT===
{{Article détaillé|Compression CCITT}}
C'est une compression d'images utilisée pour le [[télécopieur|fax]]. Elle peut être de type RLE (on code les suites de [[pixel]]s blancs et de pixels noirs) et 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 de Gr2 et de Gr3, utilisée pour les fax. le groupe2 utilise comme indiqué une compression RLE, mais les symboles représentant les longueurs sont définis par le CCITT en fonction de leur fréquence probable et ceci pour diminuer la taille des messages à transmettre par les fax.
La compression de Gr3, elle, représente une ligne par les différences avec la ligne précédente. Ainsi un carré noir sur une page blanche n'aura que la première ligne du carré à transmettre, les suivantes étant simplement la "différence", c'est-à-dire rien. Et la page complète revient à envoyer 3 lignes et un symbole de "répéter la précédente" pour toutes les autres.
Ceci est théorique! En fait plus de symboles seront à transmettre, mais envoyer une page blanche est quand même beaucoup plus rapide en Gr3 que en Gr2
===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 fréquent sur peu de place, et coder en revanche sur des séquences plus longues ce qui revient rarement ([[Entropie de Shannon|entropie]]). En morse le « e », lettre très fréquente, est codé par un simple point, le plus bref de tous les signes.
L'originalité de [[David A. Huffman]] est qu'il fournit un ''procédé d'agrégation objectif'' permettant de constituer son code dès lors qu'on possède les statistiques d'utilisation de chaque caractère.
Le [[Macintosh]] d'[[Apple, Inc.|Apple]] codait les textes dans un système inspiré de Huffman : les 15 lettres les plus fréquentes (dans la langue utilisée) étaient codées sur {{unité|4|bits}}, et la 16{{e}} combinaison était un code d'échappement indiquant que la lettre était codée en [[Code_ASCII|ASCII]] sur les {{unité|8|bits}} suivants. Ce système permettait une compression des textes voisine en moyenne de {{unité|30|%}} à une époque où la mémoire était extrêmement chère par rapport 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 donc '''lire tout le fichier''' avant de comprimer!
Une autre conséquence est que pour décomprimer il faut connaître les codes et donc la table, qui est ajoutée devant le fichier, aussi bien pour transmettre que stocker, ce qui diminue la compression, surtout pour les petits fichiers.
Ce problème est éliminé par le '''codage Huffman adaptatif''', qui modifie sa table au fil des choses. Et peut donc démarrer avec une table de base. En principe il commence avec les caractères à même probabilité.
=== Lempel-Ziv 1977 (LZ ou LZ77) ===
{{Article détaillé|LZ77 et LZ78}}
La compression Lempel-Ziv 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 notamment la base d'algorithmes répandus comme [[Deflate]] ([[Zip]], [[Gzip]]) ou [[LZMA]] ([[7-Zip]])
LZW. Est basée sur la même méthode. Mais Welch a constaté que en créant un dictionnaire initial de tous les symboles possibles la compression était améliorée puisque le décompresseur peut recréer le dictionnaire initial et ne doit donc pas le transmettre ni envoyer les premiers symboles. Elle a été brevetée par UNISYS et ne peut donc être utilise librement. 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.
=== Lempel-Ziv 1978 et Lempel-Ziv-Welch (LZ78 et LZW) ===
{{Article détaillé|Lempel-Ziv-Welch}}
La compression Lempel-Ziv-Welch est dite de type dictionnaire. Elle est basée sur le fait que des motifs se retrouvent plus souvent que d'autres et qu'on peut donc les remplacer par un index dans un dictionnaire.
Le dictionnaire est construit dynamiquement d'après les motifs rencontrés.
===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 principalement destiné à faciliter la compression de texte en langue naturelle, mais il est également utilisable pour compresser n'importe quelles données binaires. Cette transformation, qui est complètement réversible, effectue un tri sur toutes les rotations du texte source, ce qui tend à regrouper les caractères identiques ensemble en sortie, ce qui fait qu'une compression simple appliquée aux données produites permet souvent une compression très efficace.
=== Prédiction par reconnaissance partielle (PPM)===
{{Article détaillé|Prédiction par reconnaissance partielle}}
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 peut être utilisé en entrée d'un codage arithmétique par exemple.
La prédiction par reconnaissance partielle donne en général de meilleurs taux de compression que des algorithmes à base de Lempel-Ziv, mais est sensiblement plus lente.
Note : PPM est également utilisé pour l'autocomplétion des commandes dans certains systèmes Unix.
===Codage arithmétique===
{{Article détaillé|Codage arithmétique}}
Le codage arithmétique est assez similaire au codage de Huffman en ceci qu'il associe aux motifs les plus probables les codes les plus courts ([[Entropie de Shannon|entropie]]).
Contrairement au codage de Huffman qui produit au mieux des codes de {{unité|1|bit}}, le codage arithmétique peut produire des codes vides. Le taux de compression obtenu est par conséquent meilleur.
===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 PPMs) pour obtenir l'estimation la plus fiable possible 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 très 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 (logiciel)|PAQ]].
== Compression avec pertes ==
La compression avec pertes ne s'applique qu'aux données « perceptuelles », en général sonores ou visuelles, qui peuvent subir une modification, parfois 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 parfois appelée '''compression irréversible''' ou '''non conservative'''.
Cette technique est fondée sur une idée simple : seul un sous-ensemble très faible de toutes les images possibles (à savoir celles que l'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 donc 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 et à les coder de la façon aussi compacte que possible. La norme [[JPEG 2000]], par exemple, arrive généralement à 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 nécessairement tous les détails d'une image, il est possible de réduire la quantité de données de telle sorte que le résultat soit très ressemblant à l'original, voire identique, 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 réduire la quantité de données tout en préservant la qualité perceptuelle.
De même, seul un sous-ensemble très faible de sons possibles est exploitable par l'oreille, qui a besoin de ''régularités'' engendrant 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 donc acceptable, même si le son restitué n'est pas en tout point identique au son d'origine.
On peut distinguer trois grandes familles de compression avec perte :
* par prédiction, par exemple l'[[Adaptive Differential Pulse Code Modulation|ADPCM]] ;
* par transformation. Ce sont les méthodes les plus efficaces et les plus utilisées. ([[compression JPEG|JPEG]], [[JPEG 2000]], l'ensemble des normes [[MPEG]]…) ;
* compression basée sur la récurrence fractale de motifs ([[Compression fractale]]).
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 [[Advanced Audio Coding|AAC]], qui peuvent parfaitement être utilisés indépendamment, et bien sûr des codeurs vidéos — généralement simplement référencés par la norme dont ils dépendent (ex: MPEG-2, MPEG-4), ainsi que des solutions pour la synchronisation des flux audio et vidéo, et pour leur transport sur différents types de réseaux.
==Récapitulatif==
{| class="wikitable"
|----- bgcolor="#aaddaa"
| rowspan="2" |Domaines || colspan="3" | <center>sans pertes</center>
| colspan="3" | <center>avec pertes</center>
|----- bgcolor="#aaaaaa"
| <center>Huffman</center> || <center>Dictionnaire</center> || <center>Autre</center> || <center>DCT</center> || <center>Ondelette</center> || <center>Autre</center>
|-----
| Général<br />binaires/données ||
| [[7z]], [[LZW]], [[Z]], [[gzip]], [[bzip2]], [[ZIP (format de fichier)|zip]]
| [[Run-length encoding|RLE]] (Run-Length Encoding) || ||
|
|-----
| Audio || || || [[FLAC]], [[Wavpack]], [[Monkey's Audio]], Lossless Audio (LA)
| [[Advanced Audio Coding|AAC]], [[MP3]], [[Vorbis|Ogg Vorbis]], [[Speex]]
| || [[Adaptive Differential Pulse Code Modulation|ADPCM]]
|-----
| Image ||
| [[Graphics Interchange Format|GIF]], [[Portable Network Graphics|PNG]]
| [[PCX]] (RLE), [[ILBM]]? (ou [[IFF]]), [[IMG]]?, CCITT, [[JPEG-LS]], [[JPEG2000]]<sup>*</sup>
| [[JPEG]] || [[DjVuPhoto]], [[JPEG2000]], [[Enhanced_Compression_Wavelet|ECW]], [[MrSID]]<sup>*</sup>, [[SPIHT]] ||
|-----
| Vidéo || ||
| [[MJPEG2000]] || [[MJPEG]], [[MPEG-1]], [[MPEG-2]], [[MPEG-4]]
| [[MJPEG2000]], [[Tarkin (codec)|Tarkin]]
|}
*Note 1 : Certains algorithmes peuvent être brevetés.
*Note 2 : Le format [[TIFF]] ''[[Encapsulation (programmation)|encapsule]]'' un mode de codage de l'image, qui peut être compressée ou non, avec l'un des algorithmes sus-cités.
*Note 3 : [[JPEG 2000]] possède un mode sans perte (utilisant une transformée en ondelettes réversible) en plus du mode standard avec pertes, d'où sa présence dans les 2 parties du tableau.
== Notes ==
<references/>
== Bibliographie ==
* Istok Kespret - ''[[Référence:Compresser vos données avec LHA, Pkzip, Arj|Compresser vos données avec LHA, PKZIP, ARJ …]]'' - <small>(éd. [[Micro Application]], coll. "Le livre de", 1994) - 348 p. </small>- ISBN 2-7429-0172-8
=== Articles connexes ===
* [[Format de données]]
* [[Taux de compression de données]]
* [[Quotient de compression]]
* [[Quantification vectorielle]]
* [[Compression audio]]
* [[Compression vidéo]]
* [[Compression d'image]]
=== Liens externes ===
* {{fr}} [http://webfractales.free.fr/site_fractale/fichier/rapport-images.pdf Documentation sur les compressions RLE, RL, HUFFMAN, LZW et JPEG]{{pdf}}
* {{fr}} [http://www.calvat.com/index.php?Menu=TUT&SMenu=RLE Tutorial RLE] Explications sur la méthode de compression Run-Leng Encoding (RLE) avec exemple (en Basic).
* {{fr}} [http://www.compressionmax.fr Comparaison des logiciels de compressions de données sans perte.]
* {{fr}} [http://rlwpx.free.fr/WPFF/comploc.htm Comparatif de méthodes de compression de données]
* {{en}} [http://cs.fit.edu/~mmahoney/compression Codage arithmétique et pondération de contexte]
{{Portail informatique}}
[[Catégorie:Compression de données]]
[[als:Datenkompression]]
[[ar:ضغط بيانات]]
[[be-x-old:Сцісканне дадзеных]]
[[bs:Sažimanje podataka]]
[[ca:Compressió de dades]]
[[cs:Komprese dat]]
[[da:Datakomprimering]]
[[de:Datenkompression]]
[[en:Data compression]]
[[es:Compresión de datos]]
[[et:Andmete pakkimine]]
[[fa:فشردهسازی دادهها]]
[[fi:Tiedonpakkaus]]
[[he:דחיסת נתונים]]
[[hr:Sažimanje podataka]]
[[hu:Adattömörítés]]
[[id:Kompresi data]]
[[it:Compressione dei dati]]
[[ja:データ圧縮]]
[[ko:데이터 압축]]
[[lt:Glaudinimas]]
[[ms:Mampatan data]]
[[nl:Datacompressie]]
[[pl:Kompresja (informatyka)]]
[[pt:Compressão de dados]]
[[ru:Сжатие данных]]
[[simple:Data compression]]
[[sk:Kompresia dát]]
[[sv:Datakompression]]
[[th:การบีบอัดข้อมูล]]
[[tr:Veri sıkıştırma]]
[[uk:Стиснення даних]]
[[zh:数据压缩]]