La compression de fichiers

De Wiki info-lab.fr
Aller à : Navigation, rechercher

Sommaire

Théorie sur la compression des fichiers

La compression de fichiers a pour but de réduire la consommation d'espace de stockage utilisé, de réduire la taille des données transitant sur les réseaux (et de fait leur temps de transmission). De manière indirecte la compression des fichiers peut accélérer le temps de lecture/écriture de ces données compressés : En effet un contrôleur et son support de stockage responsables des lectures/écritures sont souvent beaucoup plus lents qu'un processeur responsable de la compression.
Contrairement à la compression de fichiers audio (vorbis, MP3...) ou à la compression d'images (jpeg) qui peuvent se permettre d'êtres destructives car on sait dans ce cas là quelles informations perdre sans que ce soit trop préjudiciable (en jouant sur la qualité de l'image ou du son) la compression standard de fichiers ne doit pas être destructive. On ne sait pas ce que l'on compresse (du texte, de la photo, un exécutable, des données structurées ?) et donc quelles sont les informations que l'on pourrait se permettre de perdre ou simplifier. Un fichier décompressé doit être conforme à son original avant compression.
Les techniques de compression vont donc consister à:

  • Rechercher dans un fichier la fréquence d'apparition des caractères dans ce fichier, et créer une table des fréquences.
  • Dans cette table, affecter un codage avec le moins de bits possible pour les caractères qui reviennent le plus souvent.
  • Affecter un codage avec un nombre de bits moyen à ceux qui reviennent à fréquence d'apparition moyenne.
  • Affecter un codage avec un nombre de bits élevé à ceux qui reviennent peu souvent.

Différents types et techniques de codage

Le codage de Huffman

Simple à mettre en oeuvre et ayant un bon taux de compression il est mis en oeuvre par nombre d'algorithmes de compression standard. Il est aussi utilisé par des algorithmes de compression destructives, en seconde étape - la norme JPEG par exemple comprend un codage de Huffman en dernière phase.
Le codage de Huffman suit exactement le procédé vu ci-dessus :

  • D'abord comptage de la fréquence d'apparition (occurrence) de chaque caractère (ou de chaque Octet présent dans le fichier). Par exemple la chaîne de caractère COMPRESSIONS
  • Affectation à chaque caractère détecté un nombre (son occurrence) et tri des caractères avec leurs occurrences par ordre décroissant.
(S,3) (O,2) (C,1) (M,1) (P,1) (R,1) (E,1) (I,1) (N,1)
  • On commence par additionner les occurrences faibles [C,M, P, R, E, I et N] 2 par 2 ; en cas de nombre impair, la dernière n'est pas additionnée.
(C+M,2) (P+R,2) (E+I,2) (N,1) 
  • Puis on ajoute à ce résultat les occurrences supérieures et on les additionnes 2 par 2
(C+M+P+R,4) (E+I+N,3) (O,2)
  • Et on continue jusqu'à additionner toutes les occurrences
(C+M+P+R+E+I+N, 7) (O+S,5)
  • Pour au final obtenir
(CMPREINOS,12) 

Ce qui nous donne la table arborescente suivante :
Huffman1.png
On va maintenant coder les occurrences en associant à chaque noeud de droite le bit 1 et à chaque noeud de gauche le bit 0. En parcourant un caractère (ou un octect) de la racine jusqu'à la feuille qui le représente on obtiendra son code binaire.
Huffman2.png
Ainsi le code binaire de S dans cette table est 11, celui de O est de 10 et celui du caractère P est 0010. On voit bien ici que les caractères qui reviennent souvent on un codage plus petit (donc économe en place occupée) que ceux qui reviennent moins souvent.
Pour les algorithmes qui utilisent Huffman, cette table calculée est fournie dans l'archive en complément du fichier compressé pour pouvoir décoder et décompresser le fichier.

Le codage RLE

RLE (Run Lenght Encoding) est en général utilisé en complément d'un autre codage, par exemple avant une passe de Huffman ou juste après. Ce codage est très efficace quand une chaîne de caractères apparaît très souvent : Par exemple de longues suites de zéros, des images comportant de grandes zones continues de la même couleur ...
Il remplace chaque chaîne de caractères par un couple de caractères composé de son occurrence et du caractère associé. Par exemple :

titiiiiiiiiiizaaaaazaaa se transformera en 1t1i1t10i1z5a1z3a  (23 caractères -->  17, compression de 26%)

Le codage LZ77

Variante de LRE, LZ77 parcours le fichier sur une portion de quelques dizaines ou centaines d'octets et va rechercher les occurrences plusieurs fois présentes. Par exemple

CCCCCCCAZERTYCCC va être codé C(1,7)AZERTY(3,13)

Ce qui signifie "copie 7 caractères situés 1 position cette instruction" (soit 7 fois le caractère A) et ensuite "copie 3 caractères situés 13 positions cette instruction" (soit à nouveau 3 fois le caractère A).
Pour augmenter l'efficacité de LZ77 il faut augmenter la fenêtre glissante sur laquelle s'effectue le repérage des chaînes déjà existantes, mais cela augmente aussi l'empreinte mémoire du programme qui met en oeuvre LZ77. Dans les faits, pour des questions d'efficacité et d'empreinte mémoire raisonnable cette fenêtre glissante dépasse rarement quelques kilo-octets ou dizaines de Ko.

Deflate

DEFLATE consiste à effectuer une passe LZ77 afin d'éliminer les grosses redondances dans les chaînes de caractères et de compléter par une passe de Huffman pour coder les symboles les + utilisés sur un nombre réduit de bits. Cette technique ou association de codages est très largement employée.

Algorithmes de compression

ZIP

Format de fichiers et programme permettant l'utilisation, en théorie, de plusieurs algorithmes mais en pratique seul DEFLATE est utilisé. Rapide et moyennement performant.
Souvent utilisé de manière transparente par de nombreux programmes qui compressent ainsi leur données sans que l'utilisateur s'en aperçoive.

GunZip (gzip)

Très proche de ZIP, il utilise comme lui la technique DEFLATE. Associé avec l'utilitaire TAR qui concatène plusieurs fichiers en une seule archive, GunZip est capable dans ce cas de voir les redondances entre tous les fichiers de l'archive - ce que ne sait pas faire ZIP qui traite les différents fichiers séparément. Dans ce cas GunZip est légèrement plus performant que Zip.

BZIP2

Amélioration de GunZip, BZip2 travaille en plusieurs étapes suivant cet ordre :

  • Un codage LRE.
  • Une "transformée de Burrows-Wheeler" [1] qui en permutant le texte rassemble les mêmes caractères.
  • Une transformation "Move To Front" [2] pour augmenter l'efficacité des dernières passes.
  • Un autre codage LRE.
  • Un codage de Huffman.
  • Quelques petites optimisations finales.

Bzip2 bien que très performant est forcement plus lent que Zip ou GunZip.

Programmes utilisation la compression

La compression est utilisée par de très nombreux programmes :

  • Des programmes de compression, forcement.
zip -r monarchive.zip dossier-a-compresser

Zip affiche le taux de compression obtenu :

zip -r livres.zip Books
 adding: Books/la_fontaine_fables_livre1.epub (deflated 0%)
 adding: Books/beatles_complete_lyrics_of_all_songs.epub (deflated 9%)
 adding: Books/jarry_ubu_roi.epub (deflated 3%)
  • Certains programmes tels que WinRAR utilisent un format de compression propriétaire RAR basé sur LZ77 et la PPM [3]
  • Des programmes d'archivage, qui créent une archive puis la compressent à la volée.
tar -czf monarchive.tar.gz dossier-a-compresser/         création d'une archive TAR compressée par GunZip
tar -xzf monarchive.tar.gz        décompression de l'archive
tar -cjf monarchive.tar.bz2 dossier-a-compresser/        création d'une archive TAR compressée par BZip2
tar -xjf monarchive.tar.bz2       décompression de l'archive
  • De nombreux programmes utilisent la compression soit parce que le format de fichier qu'ils utilisent le demande (MP3, JPEG, PDF, fichiers LibreOffice...), soit pour simplement compresser les fichiers qu'ils génèrent (JAVA compresse par Zip tous les fichiers .jar générés, le jeu QUAKE fait de même avec ses fichiers .pk3). De fait de très nombreux formats de fichiers sont déjà naturellement compressés.

Utilité de la compression

Puisse que la taille de nos supports de stockage augmente presque de manière exponentielle tous les 3 ans, pourquoi compresser ? Parce que :

  • Tous nos appareils ne sont pas équipés d'un disque dur de 2 To.
  • Le prix des SSD a tendance à exploser pour les modèles de grande capacité.
  • Une clé USB, une SDCard ou MicroSD d'appareil photo numérique est de bien moindre capacité qu'un disque dur.
  • Nos tablettes, ordiphones, assistants numérique et autres téléphones mobiles évolués possèdent rarement plus de quelques Go ou dizaines de Go d'espace de stockage, parfois non extensibles (pas de port SD ou microSD disponible).
  • Quelques constructeurs malhonnêtes vous vendent des tablettes à soit-disant 32 Go de stockage dont presque la moitié est déjà utilisée par le système et une inutile partition de restauration. Sans compresser vous risquez de vous retrouver à l'étroit sur ce genre de tablettes, à moins bien sûr de ne pas en acheter.
  • Un abonnement 3G possède presque toujours une limite mensuelle de données au delà de laquelle le débit est bridé : compresser permet de repousser cette limite.
  • Il y a encore des limites à la taille des pièces jointes associées aux courriels. Compresser permet parfois d'envoyer une pièce jointe alors que cela aurait été impossible sans le faire.
  • Une ligne ADSL grand public possède en général un débit ascendant (émission) limité, 8 fois moindre (parfois plus) au débit descendant (réception). Compresser des données avant de les envoyer permet de gagner du temps.
  • La sauvegarde de grands volumes de données est beaucoup plus rapide s'ils sont déjà compressés.
  • Les espaces de stockage en ligne sont soit gratuits pour de petites capacités (2 ou 5 Go) soit payants (par tranches de 10, 25, 50 Go...). Dans les 2 cas : "Compresser plus pour stocker plus !" (et payer moins).

Les limites de la compression

Format de fichiers naturellement compressés

Par nature de très nombreux formats de fichiers sont naturellement compressés. Si on essaie de les compresser à nouveau, le gain est soit minime (entre 10 et 2 %) , ridicule (moins de 2 %), nul ou même dans certains cas négatif (augmentation de quelques pour cent).

  • Certains formats de fichiers combinent compression destructive et compression non destructive : JPEG, OGG, MP3, GIF, PNG et presque tous les formats vidéo. Voir l'article sur "La compression audio".
  • JAVA compresse systématiquement tous les fichiers .jar générés.
  • Le jeu QUAKE compresse les fichiers .pk3.
  • Les fichiers .pdf sont compressés.
  • Les fichiers générés par la suite bureautique OpenOffice.org/LibreOffice (.odt, .ods, .odp, .odg, .odb) sont compressés.
  • De nombreux jeux commerciaux ayant tendance à grossir de plus en plus mettent en oeuvre LZ77 pour tous leur fichiers.
  • etc... En général un bon test pour savoir si un fichier est déjà compressé est de lui appliquer une compression et de regarder le taux obtenu. Moins de 5 % ? --> Format déjà compressé.

Dans ces conditions le temps CPU et l'énergie dépensés ne justifient pas un gain d'espace aussi minime.

Fichiers au contenu trop entropique

Un fichier au contenu trop entropique, trop aléatoire, contient en général tellement peu d'occurrences de ses symboles que toute tentative de compression se soldera par un taux de compression obtenu minable ou nul.
De fait tout flux chiffré, aléatoire (Chargen) ou fichier ayant subi le même traitement ne gagnera rien à être compressé. Dans le cas du chiffrement, pour obtenir un gain quelconque il faut compresser les données en clair puis chiffrer le résultat compressé et pas l'inverse. Cela renforcera même la robustesse du flux ou fichier chiffré face aux attaques de type coïncidence et mot probable [4] car la compression change complètement le format et la taille des données qui pourraient "être attendues".

Outils personnels
Espaces de noms

Variantes
Actions
Navigation
Outils