« Compression de données/Introduction » : différence entre les versions
Contenu supprimé Contenu ajouté
Aucun résumé des modifications |
Séparation LZ77 et LZW, LZW => motifs à la place de caractères (on ne compresse pas forcément du texte), ajout de PPM et CM |
||
Ligne 46 :
===Compression CCITT===
{{Article détaillé|
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 ("groupe") suivant l'algorithme utilisé et le nombre de couleurs du document (monochrome, niveau de gris, couleur).
Ligne 57 :
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 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 8 bits suivants. Ce système permettait une compression des textes voisine en moyenne de 30 % à une époque où la mémoire était extrêmement chère par rapport aux prix actuels (compter un facteur 1000).
=== Lempel-Ziv
{{Article détaillé|LZ77 et LZ78}}
La compression Lempel-Ziv remplace des motifs récurents 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]]).
=== 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
Le dictionnaire est construit dynamiquement d'après les
===Transformée de Burrows-Wheeler
{{Article détaillé|
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 une 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é|
Le codage arithmétique est assez similaire au codage de Huffman en ceci qu'il associe aux motifs les plus
Contrairement au codage de Huffman qui produit au mieux des codes de 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 systèmes complexes comme des 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 ==
Ligne 144 ⟶ 172 :
*[http://www.compressionmax.fr Comparaison des logiciels de compressions de données sans perte.]
*[http://rlwpx.free.fr/WPFF/comploc.htm Comparatif de méthodes de compression de données]
*[http://cs.fit.edu/~mmahoney/compression
{{Portail informatique}}
| |||