Compression de données/Techniques de compression sans perte

La compression sans perte permet la reconstitution exacte des données d'origine lors de la décompression. C'est celle utilisée pour les fichiers de données.

Types de compression

Codage par répétition

Les algorithmes tels que Lempel-Ziv ou le 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.

Codage par répétition

Codage RLE

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

Exemple : AAAAAAAAZZEEEEEER donne : 8A2Z6E1R, ce qui est beaucoup plus court.

Voir le chapitre « Run-length encoding » qui détaille l'algorithme.

Compression CCITT

C'est une compression d'images utilisée par les télécopieurs (ou fax), standardisée par des recommandations de l'Union internationale des télécommunications (UIT, anciennement appelée CCITT). Elle est de type RLE : on code les suites horizontales de pixels 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).

Deux compressions existent, celle du Groupe 3 (recommandation ITU T.4) et celle du Groupe 4 (recommandation ITU T.6), utilisées pour les fax :

Le Groupe 3 utilise comme indiqué une compression RLE, mais les symboles représentant les longueurs sont définis par le CCITT en fonction de leur fréquence probable et ceci pour diminuer la taille des messages à transmettre par les fax.
La compression du Groupe 4, elle, représente une ligne par les différences avec la ligne précédente. Ainsi un carré noir sur une page blanche n'aura que la première ligne du carré à transmettre, les suivantes étant simplement la « différence », c'est-à-dire rien. Et la page complète revient à envoyer 3 lignes et un symbole de « répéter la précédente » pour toutes les autres.

Ceci est théorique : en pratique, il faudra transmettre plus de symboles, mais envoyer une page blanche est tout de même beaucoup plus rapide avec le Groupe 4 qu'avec le Groupe 3.

Codage entropique

Voir le chapitre « Codage entropique » pour plus de détails.

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). En morse le « e », lettre très fréquente, est 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^ème 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).

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

Voir le chapitre « Codage de Huffman » qui détaille l'algorithme.

Code Baudot

Table de caractère du code Baudot

Le code Baudot est un exemple de compression concret, simple et représentatif. Ce code utilise une base de 5 bits pour coder les caractères alors que la table des caractères, étalée sur 6 bits, contient $2^{6}=64$ éléments. Cette dernière est séparée en deux jeux de $2^{5}=32$ éléments et deux caractères Inversion Lettres (code 31) et Inversion Chiffres (code 27) permettent de commuter entre les deux ensembles. Si les caractères étaient utilisés de manière aléatoire, ce système n'aurait aucun intérêt et entraînerait même un surplus de données avec une moyenne de $(1/2)*5+5=7,5$ bits par caractère. Cependant, les lettres sont codées sur le premier jeu de caractère tandis que les chiffres et caractères spéciaux sur le second. Or la nature des caractères utilisés n'est pas aléatoire. En effet, lorsque l'on écrit un texte cohérent, les chiffres sont séparés des lettres et les ponctuations sont rares.

Ainsi, on écrira :

le prix moyen d'une encyclopédie est de 112,45 euros (52 caractères)

L E [SP] P R I X [SP] M O Y E N [SP] D [FIGS] ' [LTRS] U N E [SP] E N C Y C L O P E D I E [SP] E S T [SP] D E [SP] [FIGS] 1 1 2 , 4 5 [SP] [LTRS] E U R O S

( $56*5=280$  bits)

Alors qu'il est peu probable que l'on ait à taper :

1e pr1 m0yen d'une en5yc10p3d1 e5t 2 cent12,45 eur0s (52 caractères)

[FIGS] 1 [LTRS] E [SP] P R [FIGS] 1 [SP] [LTRS] M [FIGS] 0 [LTRS] Y E N [SP] D [FIGS] ' [LTRS] U N E [SP] E N [FIGS] 5 [LTRS] Y C [FIGS] 1 0 [LTRS] P [FIGS] 3 [LTRS] D [FIGS] 1 [SP] [LTRS] E [FIGS] 5 [LTRS] T [SP] [FIGS] 2 [SP] [LTRS] C E N T [FIGS] 1 2 , 4 5 [SP] [LTRS] E U R [FIGS] 0 [LTRS] S

( $74*5=370$  bits)

Sans compression, c'est-à-dire en codant chaque caractère sur 6 bits, ces chaînes de caractère auraient le même poids de $52*6=312$ bits.

Ici on remarque qu'en utilisant le code Baudot le premier texte a été compressé de manière bénéfique contrairement au second. En effet, alors que la première chaîne était prévisible, la seconde ne l'était clairement pas.

Le code Baudot joue donc sur la probabilité de la répartition des caractères au sein d'un texte intelligible.

Codage arithmétique

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

Codage par dictionnaire

Lempel-Ziv 1977 (LZ77)

Pour plus de détails voir : LZ77.

La compression LZ77 remplace des motifs récurrents 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, xz)

Lempel-Ziv 1978 et Lempel-Ziv-Welch (LZ78 et LZW)

Pour plus de détails voir : LZ78.

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

LZW est basée sur la même méthode, mais Welch a constaté que, en créant un dictionnaire initial de tous les symboles possibles, la compression était améliorée puisque le décompresseur peut recréer le dictionnaire initial et ne doit donc pas le transmettre ni envoyer les premiers symboles. Elle a été brevetée par UNISYS et ne pouvait donc être utilisée librement dans tous les pays jusqu'à l'expiration du brevet en 2003. Elle sert dans les modems, mais UNISYS s'est engagé à vendre une licence à tout fabricant avant d'être acceptée comme norme de compression internationale pour les modems.

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

Codage par modélisation de contexte

Prédiction par reconnaissance partielle (PPM)

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

Pondération de contextes (CM)

Pour plus de détails voir : 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…). Elle peut être basiquement réalisée par une moyenne pondérée, mais les meilleurs résultats sont obtenus par des méthodes d'apprentissage automatique comme les 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.

Transformée de Burrows-Wheeler (BWT)

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.

La technique est détaillée dans le chapitre Transformée de Burrows-Wheeler.

Limites de la compression sans perte

Il n'existe pas de technique de compression universelle qui puisse réduire la taille de toutes les données possibles. Si cela existait, on commencerait par réduire les données originales, puis on réapplique la compression aux données compressées, et on réapplique, jusqu'à aboutir au résultat absurde de 0 octet. Cette succession de compressions aboutit en fait à une perte d'information à chaque étape, ce qui est contradictoire avec le caractère sans perte de cet algorithme.

Cela signifie que chaque algorithme compresse bien certains cas de données (Par exemple, les répétitions successives de caractères sont bien gérées par RLE), mais que d'autres cas de données non traitables par l'algorithme génèrent une quantité de données compressées supérieure à l'originale.

Une démonstration détaillée est donnée dans la section « Fichiers non-compressibles » du chapitre sur le taux de compression.

L'algorithme utilisé doit donc être adapté aux données à compresser.