Cours de Compression de données en PDF (Intermédiaire)
Compression de données : Le codage de source réduit la taille des informations pour optimiser le stockage et accélérer la transmission. Ce document couvre les principes fondamentaux, les métriques (entropie, ratio de compression) et des méthodes classiques utilisées en algorithmique. Ce cours a été rédigé par PEREIRA Vincent, LEPRETTE Franck et HACAULT Vincent, auteurs spécialisés en algorithmique et traitement de l'information.
🎯 Ce que vous allez apprendre
- Définition et intérêt de la compression : Bases, métriques et cas d'usage pour le stockage et la transmission.
- Classification des algorithmes de compression : Distinction entre méthodes sans perte et avec perte, et critères de choix.
- Compression de type statistique : codage de Huffman : Principe, lien avec l'entropie et performances en codage de source.
- Compression de type Dictionnaire : Principes des algorithmes basés sur un dictionnaire, comme LZW.
- Applications pratiques : Exemples concrets d'utilisation et évaluation du ratio de compression.
Pourquoi compresser : Stockage et Transmission
Réduire le volume stocké permet d'économiser de l'espace disque et d'améliorer l'efficacité des transferts. Un meilleur ratio se traduit par une augmentation du débit effectif perçu sur un réseau et une diminution de la latence pour les flux contraints. Sur des liens saturés, la réduction du volume facilite la gestion des files d'attente et diminue le risque de perte de paquets.
Exemple de calcul du ratio de compression
Formule : (Taille originale / Taille compressée). Exemple simple : un fichier de 10 000 octets compressé à 2 500 octets donne un ratio de 4 (10 000 / 2 500). Le gain relatif peut se mesurer aussi en pourcentage : ((Taille originale − Taille compressée) / Taille originale) × 100.
Les méthodes de codage : Huffman et LZW
Dans le modèle de source, l'alphabet Σ définit l'ensemble des symboles possibles ; la distribution sur Σ influence directement l'entropie et la redondance exploitable par un algorithme. La connaissance du modèle de source est donc centrale pour évaluer les performances théoriques (Entropie de Shannon) et les limites du codage de canal.
Le terme « codage » désigne ici les techniques qui représentent l'information avec moins de bits. Le codage de Huffman est une method statistique liée à l'entropie de Shannon : il construit des codes optimaux pour un modèle de source donné et appartient aux techniques sans perte. En pratique, l'entropie fournit une borne inférieure sur la longueur moyenne d'un code; Huffman approche cette borne lorsqu'on connaît bien la distribution des symboles. LZW, méthode par dictionnaire, remplace des séquences répétées par des références dans un dictionnaire construit dynamiquement. Ces approches se comparent sur la complexité, la mémoire et le ratio obtenu selon le type de données (texte, binaire, flux).
Pour Huffman, la génération des codes repose sur la construction d'un arbre binaire de poids minimal : les symboles fréquents obtiennent des codes courts, tandis que les symboles rares reçoivent des codes plus longs. Ce mécanisme aboutit à un codage de longueur variable adapté aux distributions observées et permet d'approcher la limite fixée par l'entropie de Shannon.
Compression avec perte vs sans perte
La compression sans perte permet la récupération bit à bit des données (ex. ZIP, GZIP). La compression avec perte sacrifie des détails non essentiels pour atteindre des ratios plus élevés, adaptée aux contenus perceptuels (image, audio, vidéo).
- Sans perte : ZIP, GZIP, PNG
- Avec perte : JPEG, MP3, MPEG
Recommandation technique : privilégier la compression sans perte pour les données nécessitant intégrité complète (archives, bases de données, formats chiffrés) ; opter pour une compression avec perte pour médias perceptuels lorsque le compromis qualité/poids est acceptable. Ajustez les paramètres (taux d'échantillonnage, coefficient de quantification, niveau de qualité) pour obtenir le meilleur rapport entre qualité visuelle/sonore et taille selon la contrainte de bande passante ou de stockage.
Applications sur images et documents : pour les images photographiques, le standard JPEG offre un bon compromis taille/qualité en sacrifiant des détails peu perceptibles. Les graphiques à palettes et animations peuvent tirer parti du GIF ou de PNG selon qu'on privilégie la perte ou la conservation de chaque pixel. Les documents PDF incorporent souvent des flux compressés (Flate/ZIP pour le texte et la structure, JPEG pour les images embarquées) : le choix des méthodes influe donc à la fois sur la lisibilité et sur la taille finale du document.
Applications concrètes : ZIP, JPEG et flux multimédia
ZIP et GZIP sont couramment employés pour l'archivage et l'échange de fichiers ; ils utilisent des techniques sans perte adaptées aux données binaires et textuelles. JPEG reste le standard pour la photographie et le web, avec des réglages de qualité permettant d'optimiser le poids des images tout en conservant une perception visuelle satisfaisante. Pour les flux multimédia en temps réel, les codecs MPEG et variantes adaptent la compression aux contraintes de latence et de bande passante; ils combinent souvent compression spatiale et temporelle pour réduire le débit nécessaire sans altérer excessivement l'expérience utilisateur.
Calculer l'efficacité : Ratio et gain de compression
Le ratio mesure combien de fois la donnée a été réduite ; le gain exprime la réduction en pourcentage. Outre la formule de base, il est important de distinguer taille compressée avec métadonnées (en-têtes, tables de codes, dictionnaires) et taille strictement utile. Pour comparer méthodes, calculez le ratio moyen sur un corpus représentatif, la variance des résultats et le coût en temps et mémoire. Une méthode peut produire un meilleur ratio mais nécessiter davantage de mémoire ou de temps CPU, ce qui la rend inadaptée selon la contrainte opérationnelle.
Optimisation de la transmission
Réduire le volume à transférer diminue la bande passante nécessaire et la congestion. Pour les flux en temps réel, une compression adaptée minimise le buffering et la latence. Dans des architectures distribuées, combiner codage efficace et protocoles (récupération d'erreurs, segmentation adaptée) améliore le débit utile et la robustesse des échanges.
Algorithmes de décompression et réversibilité
Le rôle du décompresseur
Tout algorithme nécessite un décompresseur pour restaurer les données : il reconstruit les symboles à partir du flux compressé en utilisant les métadonnées (tables de codes, dictionnaire initial, en-têtes). La réversibilité dépend de la méthode : les algorithmes sans perte exigent que le décompresseur reproduise exactement l'état nécessaire pour inverser chaque étape du codage.
Comparatif des algorithmes
| Critère | Huffman (statistique) | LZW (dictionnaire) |
|---|---|---|
| Principe | Codage de longueur variable basé sur les fréquences des symboles. | Remplacement de séquences récurrentes par des références vers un dictionnaire. |
| Complexité (temps / mémoire) | Construction de l'arbre typiquement O(n log n) pour n symboles distincts ; encodage linéaire en la taille du flux, mémoire faible pour la table de fréquences. | Encodage/décodage en temps proche de linéaire amorti ; mémoire variable selon la taille du dictionnaire et l'implémentation. |
| Types de fichiers cibles | Données avec distribution de symboles bien connue (texte, logs, certains flux binaires). | Données contenant motifs répétés et séquences redondantes (texte, certaines images indexées, flux structurés). |
📑 Sommaire du document
- Introduction
- Généralités sur la compression
- Compression de type statistique : codage de Huffman
- Compression de type Dictionnaire
- Conclusion
👤 À qui s'adresse ce cours ?
- Public cible : Étudiants et professionnels en Informatique et Algorithmique souhaitant approfondir les techniques classiques de compression.
- Prérequis : Connaissances de base en algorithmique et structures de données ; niveau intermédiaire requis.
❓ Foire Aux Questions (FAQ)
Qu'est-ce que la compression de données ?
Il s'agit d'un ensemble de techniques de codage visant à réduire la taille des fichiers pour faciliter stockage et transmission. Les notions d'entropie et de codage de source permettent d'évaluer les limites théoriques de réduction.
Quels sont les types de compression ?
On distingue la compression sans perte et la compression avec perte. Théoriquement, l'entropie de la source fixe une borne inférieure sur la longueur moyenne des codes et la redondance exploitable par l'algorithme.
Quel est le meilleur algorithme pour du texte ?
Pour des données textuelles, Huffman et LZW sont souvent privilégiés. Huffman est efficace lorsque la distribution des symboles est connue, tandis que LZW exploite des motifs répétitifs via un dictionnaire ; les deux préservent intégralement le contenu.
