Compression : Différence entre versions

De Sciencinfolycee
Aller à : navigation, rechercher
(Quelques liens à propos d'algorithmes de compression)
(Quelques liens à propos d'algorithmes de compression)
Ligne 16 : Ligne 16 :
 
**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.  
 
**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 http://www.bzip.org et http://en.wikipedia.org/wiki/Burrows–Wheeler_transform.
+
*→ La méthode de compression BZIP et la [[http://en.wikipedia.org/wiki/Burrows–Wheeler_transform 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 : [[Créer_son_propre_fichier_kmz|les fichiers KMZ]] (Google Earth).
 
*→ Un exemple d'activité impliquant des fichiers compressés : [[Créer_son_propre_fichier_kmz|les fichiers KMZ]] (Google Earth).

Version du 27 novembre 2011 à 23:40

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 :