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

Contenu supprimé Contenu ajouté
imported>Silex6
intro + réorganisation
Bandeau recyclage sur le tableau : attention, il est complètement incohérent + modifs mineures
Ligne 3 :
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]].
 
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)|ZIPZip]], [[Gzip|GZgz]], [[ADPCM]], [[MP3|MP3]] et [[JPEG]] utilisent des algorithmes de compression de données.
 
La compression de données est une application de la [[théorie de l'information]].
 
== Le tauxTaux de compression ==
 
{{article détaillé|taux de compression de données}}
Ligne 18 :
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]].
 
== Les formatsFormats de données ==
 
{{À recycler}}
 
{| class="wikitable"
Ligne 49 ⟶ 51 :
*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 ==
 
=== Compression sans perte ===
Ligne 65 ⟶ 69 :
* [[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]]
Ligne 77 ⟶ 80 :
Les standards ouverts les plus courants sont décrits dans plusieurs [[RFC]] :
* RFC 1950 (ZLIB, flux de données compressées)
* RFC 1951 (système de compression par blocs « DEFLATEDeflate », utilisé par zipZip et gz)
* RFC 1952 (format de fichier compressé GZIPgzip)
 
Sur les limites de la compression sans perte, voir [[Paradoxe du compresseur]].
 
=== Compression àavec pertepertes ===
 
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'''.
Ligne 109 ⟶ 112 :
Parmi les algorithmes de compression presque sans perte, on retrouve la plupart des algorithmes de compression sans perte spécifiques à un type de données particulier, lorsqu'ils sont utilisés pour compresser un autre format de données. Par exemple, [[JPEG-LS]] permet de compresser presque sans perte du [[Windows_bitmap|bitmap]] et [[Monkey's Audio]] permet de compresser presque sans perte du [[wav|wave PCM]] : il sera possible de décompresser les fichiers obtenus pour obtenir des fichiers bitmap ou wave PCM sans la moindre perte de qualité, mais ces fichiers seront malgré tout différents des fichiers non compressés d'origine. On y retrouve aussi les algorithmes de recompression.
 
== Les algorithmesAlgorithmes ==
 
Les algorithmes tels que [[LZ77 et LZ78|Lempel-Ziv]] ou le [[run-length encoding|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 souvent, plus la suite qui la remplacera sera courte.
 
desLes algorithmes tels que la [[transformée de Burrows-Wheeler]] sont utilisés avec un algorithme de compression. deDe tels algorithmes modifient l'ordre des bits de manière à augmenter l'efficacité de l'algorithme de compression, mais sans compresser par eux-même.
 
=== 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.
 
=== Compression CCITT ===
{{Article détaillé|Compression CCITT}}
C'est une compression d'images utilisée pour le [[télécopieur|fax]], standardisée par des recommandations de l'[[Union internationale des télécommunications]] (anciennement appelée CCITT). Elle est de type RLE (on code les suites horizontales de [[pixel]]s 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).
Ligne 129 ⟶ 132 :
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 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 169 ⟶ 172 :
 
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===