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

Contenu supprimé Contenu ajouté
m Révocation des modifications de 88.186.161.112 (retour à la dernière version de Salebot)
imported>Micbot
m Bot : Correction : lien interne commençant par une minuscule → Gzip, Wikisyntaxe; changement de type cosmétique
Ligne 5 :
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 [[format de données|formats de données]] tels que [[ZIP (format de fichier)|Zip]], [[RAR (format de fichier)|RAR]], [[Gzipgzip]], [[Adaptive Differential Pulse Code Modulation|ADPCM]], [[MPEG-1/2 Audio Layer 3|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]].
Ligne 13 :
=== 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_GraphicsPortable 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).
Ligne 78 :
==== 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é).<br />
'''Exemple''': <code>AAAAAAAAZZEEEEEER</code> donne : <code>8A2Z6E1R</code>, ce qui est beaucoup plus court.
 
Ligne 98 :
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_ASCIICode 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.
Ligne 104 :
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]]).
Ligne 117 :
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 (format de fichier)|ZIP]], [[Gzipgzip]]) ou [[LZMA]] ([[7-Zip]])
 
==== Lempel-Ziv 1978 et Lempel-Ziv-Welch (LZ78 et LZW) ====
Ligne 129 :
 
=== Codage par modélisation de contexte ===
==== 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.
Ligne 137 :
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.
 
==== 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 possible du symbole à venir dans une source de données (fichier, flux…).
Ligne 146 :
Actuellement, les meilleurs taux de compression sont obtenus par des algorithmes liant pondération de contextes et codage arithmétique, comme [[PAQ (logiciel)|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 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.