« 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 |
ré-organisation |
||
Ligne 1 :
La '''compression de données''' ou '''codage de
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
==
{{...}}
{{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]].▼
== 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
{{article détaillé|Codage entropique}}
{{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 ==
|