« Compression de données/Introduction » : différence entre les versions

Contenu supprimé Contenu ajouté
imported>Salebot
bot : révocation de 83.192.151.26 (modification suspecte : -61), retour à la version 45960998 de Lilyu
Sylenius (discussion | contributions)
ré-organisation
Ligne 1 :
La '''compression de données''' ou '''codage de donnéessource''' est l'opération [[informatique]] qui consiste à transformer une suite de bits A en une suite de bits B plus courte, et qui contientcontenant les mêmes informations, en utilisant un [[algorithme]] particulier. Il s'agit d'une opération de [[codage]], c'est à dire changer la représentation de l'information, dans le but 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 identique à l'originale. Les algorithmes de compression sans perte sont utilisés pour de nombreux types de données notamment des documents, des [[fichier exécutable|fichiers exécutable]] ou des [[fichier texte|fichiers texte]].
Ligne 7 :
Les [[format de données|formats de données]] tels que [[Zip (format de fichier)|Zip]], [[Gzip|gz]], [[ADPCM]], [[MP3|MP3]] et [[JPEG]] utilisent des algorithmes de compression de données.
 
La théorie de la compression de donnéesdonnée est une applicationissue de la [[théorie de l'information]].
 
== Taux de compressionThéorie ==
{{Articlearticle détaillé|Codage arithmétiquede source}}
 
{{...}}
{{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:
 
<code>taille A: 550, taille B: 250, différence = 300. taux de compression = 300 / 550 = 54%.</code>
 
L'algorithme utilisé pour transformer A en B est destiné à obtenir un résultat B de taille inférieure à A. Il peut paradoxalement produire parfois un résultat de taille supérieure. voir [[paradoxe du compresseur]].
 
== Formats de données ==
 
{{À recycler}}
 
{| class="wikitable"
|----- bgcolor="#aaddaa"
| rowspan="2" |Usage || colspan="3" | <center>sans pertes</center>
| colspan="3" | <center>avec pertes</center>
|----- bgcolor="#aaaaaa"
| <center>Huffman</center> || <center>Dictionnaire</center> || <center>Autre</center> || <center>[[Transformée en cosinus discrète|DCT]]</center> || <center>Ondelette</center> || <center>Autre</center>
|-----
| Général ||
| [[7z]], [[LZW]], [[Z]], [[gzip]], [[bzip2]], [[RAR (format de fichier)|RAR]], [[ZIP (format de fichier)|zip]], [[XZ (format de fichier)|XZ]]
| [[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), [[Interchange file format#ILBM|ILBM]] , [[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]], [[Snow (codec)|Snow]]
|}
 
*Note 1 : Certains algorithmes peuvent être brevetés.
*Note 2 : Le format [[Tagged Image File 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.
 
== Types de compression ==
Ligne 132 ⟶ 93 :
Ceci est théorique! En fait plus de symboles seront à transmettre, mais envoyer une page blanche est quand même beaucoup plus rapide en Groupe 4 que en Groupe 3.
 
=== Codage de Huffmanentropique ===
{{article détaillé|Codage entropique}}
==== Codage arithmétiquede 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.
Ligne 140 ⟶ 103 :
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é.
 
====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.
 
 
=== Lempel-Ziv 1977 (LZ ou LZ77) ===
Ligne 173 ⟶ 142 :
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.
 
===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)===
Ligne 186 ⟶ 151 :
 
Actuellement, les meilleurs taux de compression sont obtenus par des algorithmes liant pondération de contextes et codage arithmétique, comme [[PAQ (logiciel)|PAQ]].
 
== 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:
 
<code>taille A: 550, taille B: 250, différence = 300. taux de compression = 300 / 550 = 54%.</code>
 
L'algorithme utilisé pour transformer A en B est destiné à obtenir un résultat B de taille inférieure à A. Il peut paradoxalement produire parfois un résultat de taille supérieure. voir [[paradoxe du compresseur]].
 
== Notes ==