Original
Économisé

Méthode

Plus d'informations sur la compression

Démonstrateur de compression

Comment un fichier peut-il devenir plus petit sans perdre une seule lettre ? En remarquant qu'il se répète. Collez un texte ou choisissez un exemple, et regardez trois méthodes classiques à l'œuvre : LZ77 renvoie au texte apparu plus tôt, LZW apprend un dictionnaire de chaînes au fil de la lecture, et le codage par plages compte les suites d'un même caractère. Chaque résultat est décompressé à nouveau pour montrer que rien n'a été perdu, et un graphique compare les méthodes avec ZIP et avec la limite d'entropie. Tapez ou collez un texte, ou choisissez un exemple, puis une méthode. LZ77 remplace les répétitions par des références au texte qui précède : cliquez sur une partie surlignée pour voir ce qu'elle copie. LZW construit au fil de la lecture un dictionnaire de chaînes et envoie leurs numéros. RLE comprime les plages d'un même caractère. Le graphique compare chaque méthode avec ZIP et avec la limite d'entropie, et l'application décompresse à nouveau le résultat pour vérifier que rien n'a été perdu.

Comment ça marche

  1. Tapez ou collez un texte, ou choisissez un exemple : un paragraphe, une chanson avec refrain, une ligne de pixels, un tableau de données, des lettres aléatoires ou de l'ADN.
  2. Choisissez LZ77, LZW ou RLE. Pour LZ77, réglez jusqu'où la méthode peut remonter, et cliquez sur une référence surlignée pour voir le texte antérieur qu'elle copie.
  3. Comparez les tailles des tuiles et du graphique avec ZIP et avec la limite d'entropie ; la vérification sous le texte confirme que la décompression redonne l'original.

Les répétitions sont la clé

La compression sans perte fonctionne parce que les données réelles se répètent. LZ77 garde une fenêtre du texte qu'il vient de lire ; chaque fois que les caractères suivants figurent déjà dans cette fenêtre, il écrit une courte référence, « reculer de tant et copier tant de caractères », au lieu des caractères eux-mêmes. Une référence coûte un nombre fixe de bits quelle que soit la longueur de la copie, si bien que ce sont les répétitions longues et fréquentes qui font gagner le plus. LZW obtient le même effet autrement : il construit un dictionnaire de chaque nouvelle chaîne rencontrée et n'envoie plus ensuite que le numéro de la chaîne.

Pourquoi certaines données ne rétrécissent pas

Une méthode qui réduit certains fichiers doit en agrandir d'autres : il y a moins de fichiers courts que de fichiers longs, ils ne peuvent donc pas tous raccourcir. La compression gagne sur des données qui ont des motifs, comme du texte, des tableaux et des images simples, et perd sur celles qui n'en ont pas. Des lettres aléatoires, des données chiffrées et des fichiers déjà compressés n'offrent aux méthodes rien à quoi renvoyer, et le résultat est aussi gros que l'entrée, voire plus. Le codage par plages le montre le plus clairement : sur un texte sans plages, il double la taille.

Questions fréquemment posées

Quelle est la différence entre compression sans perte et compression avec perte ?

La compression sans perte redonne exactement l'original, bit pour bit ; elle est indispensable pour le texte, les programmes et les données, et ce démonstrateur ne montre que des méthodes sans perte. La compression avec perte, comme dans les photos JPEG, la musique MP3 et la vidéo, supprime des détails que l'on remarque à peine et produit des fichiers bien plus petits, mais l'original ne peut pas être retrouvé.

Comment ZIP compresse-t-il les fichiers ?

ZIP et gzip utilisent deflate, qui applique d'abord LZ77 avec une fenêtre de 32 KB, puis écrit les littéraux et les références avec des codes de Huffman : des codes courts pour les valeurs fréquentes et des codes longs pour les valeurs rares. C'est grâce à cette seconde étape que ZIP fait généralement mieux que le LZ77 simple montré ici, qui consacre un nombre fixe de bits à chaque jeton.

LZ77 peut-il descendre sous l'entropie ?

L'entropie affichée compte les caractères un par un, sans contexte. LZ77 et LZW exploitent le contexte, puisqu'une référence copie tout un passage de texte antérieur ; sur un texte répétitif, ils peuvent donc battre largement ce chiffre. Ils ne peuvent jamais battre la véritable entropie de la source, qui tient compte de tout le contexte.

Pourquoi les tailles diffèrent-elles de celles d'un vrai fichier ZIP ?

Le démonstrateur ne compte que les bits des données codées. Un vrai fichier ZIP ajoute des en-têtes, le nom du fichier, une somme de contrôle et les tables de Huffman, ce qui rend les très petits fichiers plus gros au lieu de plus petits.

Mon texte est-il envoyé quelque part ?

Non. Toutes les méthodes, y compris la comparaison avec ZIP, s'exécutent dans votre navigateur, et votre texte reste dans le stockage local de ce navigateur.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Aller à l'éditeur