Compression

Quelques liens à propos d'algorithmes de compression

La compression des données numériques est aujourd'hui universellement employée, qu'il s'agisse d'images, de sons, de programmes exécutables ou de données de toutes sortes. Sans elle, nous ne pourrions pas utiliser de téléphone portable ni recevoir d'images provenant des sondes interplanétaires. La compression commença par l'analyse des répétitions dans les images numériques (format TIFF, voir une illustration amusante dans http://castor-informatique.fr/plaquette.pdf, page 8); ce procédé, nommé RLE (Run Length Encoding) montra vite ses limites face aux images bruitées et en millions de couleurs et céda la place à des procédés plus efficaces qui sont présentés ci-dessous.

• → L'algorithme de compression de Huffman
  • Présentation très simple et progressive du code de Huffman, permettant une première approche du sujet. Le codage dit « entropique » gagne de la place en codage les caractères (ou mots, signes, peu importe) les plus fréquents par des suites de bits les plus courtes possibles, le reste par des suites plus longues, et en créant un « dictionnaire » des codages des différents caractères rencontrés. L'inconvénient est d'une part la lenteur du travail au niveau des bits et d'autre part la nécessité de gérer/sauver/charger le dictionnaire. Le code de Huffman est l'un des algorithmes requis pour la compression d'images au format JPEG.
  • La simplicité des explications proposées dans ce texte permet d'envisager de soumettre ces pages à un groupe d'élèves cherchant à compresser des données de manière un tant soit peu efficace.
  • Voir aussi http://tcharles.developpez.com/Huffman et Stratégies gloutonnes).

• → La compression LZW (pour Lempel-Ziv-Welch)
  • Il s'agit d'un autre mécanisme très répandu de compression de données sans perte, ici traitées au niveau du caractère; on trouve cette compression comme base commune de toutes les variantes des compressions « ZIP ». Il s'agit d'une amélioration de l'algorithme LZ78 inventé par Abraham Lempel et Jacob Ziv en 1978. LZW fut créé en 1984 par Terry Welch, d'où son nom.
  • L'article référencé présente l'algorithme de compression en pseudo-code suivi d'un exemple détaillé.
  • Les documents référencés peuvent servir de base pour des projets d'élèves autour de la compression de données.

• → Notions de communication numérique (voir le chapitre sur la compression).
  • Cours destiné à des étudiants non spécialistes qui souhaiterait avoir des connaissances en transmission numérique des données. Parmi les sujets abordés figurent la représentation en fréquences, les effets du bruit et leur corrections, la compression des données, et le codage des sons, images fixes et animées.

• → La méthode de compression BZIP et la [transformation de Burrows-Wheeler]
  • donnent l'exemple d'un domaine plus récent (années 1990) et d'un algorithme de compression original, basé sur des rotations de chaînes suivies d'un tri faisant apparaitre les redondances inhérentes au langage. Voir aussi les pages de Wikipedia en français et en allemand (elles se complètent) ainsi que le site http://www.bzip.org.

• → Un exemple d'activité impliquant des fichiers compressés : les fichiers KMZ (Google Earth).

À un niveau plus théorique, nous pouvons proposer de jeter un coup d'œil sur :

• → Théories et théorie de l’information

• → et sur l'article historique The mathematical Theory of communication de Claude Shannon.

Comparer des logiciels de compression

Comparer des logiciels de compression La comparaison peut se faire selon plusieurs points de vue :

• - le taux de compression moyen (selon le genre de fichiers à compresser : images, textes, sons, exécutables, etc.)
• - la vitesse de compression moyenne (idem, valeur moyenne du temps de compression divisé par la taille de fichier)
• - la vitesse de décompression moyenne (idem)
• - le prix d'achat s'il y a lieu.

Comparaison de compresseurs de fichiers (Wikipedia en anglais)

• Tableau comparatif très détaillé des capacités de toutes sortes de programmes d'archivage et de compression; ne s'occupe pas de comparer leurs performances.

Une autre comparaison de compresseurs (en anglais)

• Page proposant un test de huit logiciels de compression selon quatre critères avec mesure de taux de compression : la compression de texte, la compression binaire, la compression d'images et la compression des codes sources (date de 2004)