Compression de données/Types de compression
Un algorithme de compression sans perte restitue après les opérations successives de compression et de décompression une suite de bits strictement identique à l'originale. Les algorithmes de compression sans perte sont utiles pour les documents, les archives, les fichiers exécutables ou les fichiers texte.
Pour la compression de données sans pertes, on distingue principalement deux types de codage : le codage entropique et le codage algorithmique.
Dans la première catégorie on retrouve entre autres le codage de Huffman. Le codage entropique se base sur des à priori sur la source. On est par exemple obligé pour le codage de Huffman de transmettre la table de probabilités pour les symboles de la source contrairement au codage algorithmique. Le codage algorithmique n’a en effet pas besoin de transmettre des informations autres que le résultat du codage. On peut prendre l’exemple des codages par dictionnaire comme LZ77, LZ78 et LZW.
Avec un algorithme de compression avec perte, 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 restituée est en revanche voisine. Les algorithmes de compression avec perte sont utiles pour les images, le son et la vidéo qui occupent beaucoup d'espace de stockage. L'altération des données par la compression avec perte dégrade la qualité de manière sensoriellement imperceptible pour un humain.
Les formats de données tels que Zip, RAR, gzip, ADPCM, MP3 et JPEG utilisent des algorithmes de compression de données.
Gagner 5% en efficacité de compression par rapport aux grands algorithmes courants peut typiquement multiplier par 100 le temps nécessaire à la compression[1].
La théorie de la compression de données utilise une considération venant de la théorie de l'information : celle d'entropie au sens de Claude Shannon.
Compression sans perte
modifierLa 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 PNG pour des images synthétiques destinées au Web[2]). 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).
Il n'existe pas de technique de compression de données sans perte universelle, qui pourrait compresser n'importe quel fichier : si une technique sans perte compresse au moins un fichier, alors elle en « grossit » également au moins un.
Les formats de fichier de compression sans perte sont connus grâce à l'extension ajoutée à la fin du nom de fichier (« nomdefichier.zip » par exemple), d'où leur dénomination très abrégée. L'extension de nom de fichier peut servir au système d'exploitation pour trouver le programme qui gère le format, mais l'identification formelle du format est faite par le programme en vérifiant que les premiers octets du fichiers représentent une certaine séquence fixe. Les formats les plus courants sont :
- 7z
- ace
- arc
- arj
- bz, bz2 (tar peut être utilisé pour créer les archives de ce type)
- CAB, utilisé par Microsoft
- gzip, gz (qui est un fichier à une seule entrée, tar peut être utilisé pour créer les archives de ce type)
- lzh
- rar
- RK
- uha
- xz
- Z (surtout sous Unix)
- Zip : extension .zip en général. Ce format est également utilisé par certains langages de programmation pour regrouper les fichiers d'une application, mais avec une extension différente. Par exemple Java l'utilise avec l'extension .jar (Java ARchive) le plus souvent, ou pour la plateforme JEE avec les extensions .war (Web Application aRchive), .ear (Enterprise Application aRchive), .rar (Resource Application aRchive)...
- zoo
Les standards ouverts les plus courants sont décrits dans plusieurs RFC :
Compression avec pertes
modifier
La compression avec pertes ne s'applique qu'aux données « perceptibles », en général sonores ou visuelles, qui peuvent subir une modification, parfois importante, sans que cela 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.
Cette technique est fondée sur une idée simple : seul un sous-ensemble très faible de toutes les images possibles (à savoir celles que l'on obtiendrait par exemple en tirant les valeurs de chaque pixel par un générateur aléatoire) possède un caractère exploitable et informatif pour l'œil. Ce sont donc ces images-là qu'on va s'attacher à coder de façon courte. Dans la pratique, l'œil a besoin pour identifier des zones qu'il existe des corrélations entre pixels voisins, c'est-à-dire qu'il existe des zones contiguës de couleurs voisines. Les programmes de compression s'attachent à découvrir ces zones et à les coder de la façon aussi compacte que possible. La norme JPEG 2000, par exemple, arrive généralement à coder des images photographiques sur 1 bit par pixel sans perte visible de qualité sur un écran, soit une compression d'un facteur 24 à 1.
Puisque l'œil ne perçoit pas nécessairement tous les détails d'une image, il est possible de réduire la quantité de données de telle sorte que le résultat soit très ressemblant à l'original, voire identique, pour l'œil humain. L'enjeu de la compression avec pertes est de réduire la quantité de données d'un fichier tout en préservant la qualité perceptible et en évitant l'apparition d'artefacts.
De même, seul un sous-ensemble très faible de sons possibles est exploitable par l'oreille, qui a besoin de régularités engendrant elles-mêmes une redondance (coder avec fidélité un bruit de souffle n'aurait pas grand intérêt). Un codage éliminant cette redondance et la restituant à l'arrivée reste donc acceptable, même si le son restitué n'est pas en tout point identique au son d'origine.
On peut distinguer trois grandes familles de compression avec perte :
- par prédiction, par exemple l'ADPCM ;
- par transformation. Ce sont les méthodes les plus efficaces et les plus utilisées. (JPEG, JPEG 2000, l'ensemble des normes MPEG…) ;
- compression basée sur la récurrence fractale de motifs (Compression fractale).
Les formats MPEG sont des formats de compression avec pertes pour les séquences vidéos. Ils incluent à ce titre des codeurs audio, comme les célèbres MP3 ou AAC, qui peuvent parfaitement être utilisés indépendamment, et bien sûr des codeurs vidéos — généralement simplement référencés par la norme dont ils dépendent (MPEG-2, MPEG-4), ainsi que des solutions pour la synchronisation des flux audio et vidéo, et pour leur transport sur différents types de réseaux.
Compression presque sans perte
modifierLes méthodes de compression sans perte significative sont un sous-ensemble des méthodes de compression avec perte, parfois distinguées de ces dernières. La compression sans perte significative peut être vue comme un intermédiaire entre la compression conservative et la compression non conservative, dans le sens où elle permet de conserver toute la signification des données d'origine, tout en éliminant une partie de leur information.
Dans le domaine de la compression d'image, la distinction est faite entre la compression sans perte (parfaite au bit près ou bit-perfect) et la compression sans perte significative (parfaite au pixel près ou pixel-perfect). Une image compressée presque sans perte (à ne pas confondre avec une image compressée avec peu de pertes) peut être décompressée pour obtenir les pixels de sa version non-compressée à l'identique. Elle ne peut en revanche pas être décompressée pour obtenir sa version non compressée intégralement à l'identique (les métadonnées peuvent être différentes).
Notes et références
modifier- ↑ Algorithme zopfli : https://code.google.com/p/zopfli/
- ↑ Ces 2 types de compressions gzip et PNG sont libres et non soumis à un brevet.