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

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 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.

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 manière à augmenter l'efficacité de l'algorithme de compression, mais sans compresser par eux-mêmes.

 

{{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.

 

{{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).

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.

 

{{Article détaillé|LZ77 et LZ78}}

 

LZ77 est notamment la base d'algorithmes répandus comme [[Deflate]] ([[ZIP (format de fichier)|ZIP]], [[Gzip]]) ou [[LZMA]] ([[7-Zip]])

 

{{Article détaillé|Lempel-Ziv-Welch}}

 

Le dictionnaire est construit dynamiquement d'après les motifs rencontrés.

 

{{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.

 

 

{{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…).

 

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 ==