Compression de données/Introduction

La compression de données traite de la manière dont on peut réduire l'espace nécessaire à la représentation d'une certaine quantité d'information. Elle a donc sa place aussi bien lors de la transmission que lors du stockage des données. Elle fait partie des applications de la théorie de l'information.

On peut classifier les méthodes de compressions en deux types, compression avec perte — également dite non conservative — et compression sans perte.

Compression sans perte

La 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 ). 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 correcteurs d'erreurs).

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. 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)
• KGB
• lzh
• rar
• Z (surtout sous Unix)
• Zip
• zoo

• FLAC (pour les flux audio)

Les standards ouverts les plus courants sont décrits dans plusieurs RFCs :

• RFC 1950 (ZLIB, flux de données compressées)
• RFC 1951 (système de compression par blocs « DEFLATE », utilisé par zip et gz)
• RFC 1952 (format de fichier compressé GZIP)

Sur les limites de la compression sans perte, voir Paradoxe du compresseur.

Codage Huffman

Pour plus de détails voir : 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. En morse le « e », lettre très fréquente, était codé par un simple point, le plus bref de tous les signes.

L'originalité de David A. Huffman est qu'il fournit un procédé d'agrégation objectif permettant de constituer son code dès lors qu'on possède les statistiques d'utilisation de chaque caractère.

Le Macintosh d'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 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).

Codage RLE

Pour plus de détails voir : 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é).

Lempel-Ziv-Welch (LZW)

Pour plus de détails voir : Lempel-Ziv-Welch.

La compression Lempel-Ziv-Welch est dite de type dictionnaire. Elle est basée sur le fait que des successions de caractères se retrouvent plus souvent que d'autres et qu'on peut donc les remplacer par un nouveau caractère. Le dictionnaire est construit dynamiquement d'après les caractères rencontrés.

Transformée de Burrows-Wheeler ou BWT

Pour plus de détails voir : transformée de Burrows-Wheeler.

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.

Compression CCITT

Pour plus de détails voir : compression CCITT.

C'est une compression d'images utilisée pour le fax. Elle peut être de type RLE (on code les suites de pixels 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).

Compression avec pertes

Utilisée pour compresser des photos, des bandes musicales, des films, ...

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

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.

Il y a moins d'information après la compression qu'avant, l'information retranchée étant sélectionnée d'après des critères fixés selon le type de données traitées. La compression d'une image en format jpeg est un exemple de compression avec perte. Puisque l'œil ne perçoit pas nécessairement tous les détails d'une image, il est possible de retrancher des données, dans l'espace des fréquences, de telle sorte que le résultat soit très ressemblant à l'original, voire pareil, pour l'œil. Le tout est de savoir quelles données retrancher. L'image finale n'étant pas, numériquement parlant, identique à l'image initiale, il s'agit d'une compression avec perte.

On peut distinguer trois grandes familles de compression avec perte :

• compression basée sur une version discrète de la transformée de Fourier la DCT (compression JPEG) ;
• compression basée sur la transformée en ondelette discrète utilisée dans le format JPEG 2000 (compression par ondelettes) ;
• 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 (ex: 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.

Récapitulatif

Domaines	sans pertes			avec pertes
	Huffman	Dictionnaire	Autre	DCT	Ondelette	Autre
Général binaires/données		7z, LZW, Z, gzip, bzip2, zip	RLE (Run-Length Encoding)
Audio			FLAC, Wavpack, Monkey's Audio	AAC, MP3, Ogg Vorbis, Speex		ADPCM
Image		GIF, PNG	PCX (RLE), ILBM? (ou IFF), IMG?, CCITT, JPEG-LS, JPEG2000*	JPEG	DjVuPhoto, JPEG2000, ecw, MrSID*, SPIHT
Vidéo			MJPEG2000	MJPEG, MPEG-1, MPEG-2, MPEG-4	MJPEG2000

• Note 1 : Certains algorithmes peuvent être brevetés.
• Note 2 : Le format TIFF 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.

Bibliographie

• Istok Kespret - Compresser vos données avec LHA, PKZIP, ARJ ... - (éd. Micro Application, coll. "Le livre de", 1994) - 348 p. - ISBN 2-7429-0172-8

Voir aussi

• français Polycopié du cours dispensé à l'ENSIMAG

Articles connexes

• Format de données
• Taux de compression
• Quotient de compression
• Quantification vectorielle
• Compression audio
• Compression vidéo
• Compression d'image

Liens externes

• Documentation sur les compressions RLE, RL, HUFFMAN, LZW et JPEG (document PDF)
• Tutorial RLE Explications sur la méthode de compression Run-Leng Encoding (RLE) avec exemple (en Basic).
• Comparaison des logiciels de compressions de données sans perte.
• Comparatif de méthodes de compression de données