🧩 Projet d'Algorithmique Avancée - Compression de données LZW & RLE

📚 Contexte

Projet réalisé dans le cadre du cours "Algorithmique Avancée" (Premier semestre 2024-2025) à l'Université Paris 8, sous la direction de BD. Ce projet explore et compare deux algorithmes de compression sans perte : Lempel-Ziv-Welch (LZW) et Run-Length Encoding (RLE), avec une application particulière aux images.

📋 Structure du projet

Le projet est divisé en deux parties principales, chacune implémentant un algorithme de compression différent:

• LZW (Lempel-Ziv-Welch)

  • compress_txt/lzw.c: Implémentation de la compression/décompression LZW pour du texte
  • Images/img_lzw.c: Application à la compression d'images

• RLE (Run-Length Encoding)

  • compress_txt/rle.c: Implémentation de la compression/décompression RLE pour du texte
  • Images/modif.c: Fonctions pour la compression/décompression d'images utilisant RLE

🛠️ Comment compiler et exécuter

Pour tester la compression sur du texte:

# Compiler et exécuter LZW sur du texte
cd compress_txt/
gcc lzw.c -o lzw_compression_txt
./lzw_compression_txt

# Compiler et exécuter RLE sur du texte
gcc rle.c -o rle_compression_txt
./rle_compression_txt

Pour tester la compression sur des images:

# Accéder au dossier Images et compiler
cd Images/
make clean
make

# Exécuter sur une image PPM
./palette requin_leopard.ppm

🖼️ Manipulation des images

Après avoir lancé l'application avec une image:

Pour LZW:

1. Cliquer sur le bouton gauche de la souris
2. Sélectionner "Trier image LZW"
3. Les composantes RGB seront triées dans le dossier tri_lzw/ (rouge.txt, vert.txt, bleu.txt)

Pour RLE:

1. Cliquer sur le bouton droit de la souris
2. Sélectionner "Compresser image RLE"
3. Les composantes compressées seront dans le dossier compress_rle/ (rouge.ppm, vert.ppm, bleu.ppm)

Pour décompresser (RLE):

1. Cliquer sur le bouton gauche de la souris
2. Sélectionner "Décompresser image RLE"
3. L'image reconstruite sera dans decompress_rle/image_reconstituee.ppm
4. Visualiser avec ./palette decompress_rle/image_reconstituee.ppm

🔍 Algorithmes implémentés

LZW (Lempel-Ziv-Welch)

Structure de données:

• Dictionnaire dynamique (Dico_Entree)
• Table de hachage pour optimiser les recherches

Fonctions principales:

• LZW: Compression
• LZWD: Décompression
• Fonctions auxiliaires: initDico, findDico, addDico, etc.

RLE (Run-Length Encoding)

Fonctions principales:

• RLE: Compression
• RLED: Décompression
• Pour les images: tri_color_rle, compress_color_rle, decompress_rle, etc.

📊 Résultats et comparaison

Les tests montrent que:

• LZW est plus efficace pour les données avec des motifs variés et complexes

  • Ex: "ababcbababaaaaaaa" → 41.18% de compression
  • Avantages: Bonne performance générale, adaptabilité aux motifs
  • Inconvénients: Plus complexe à implémenter, gestion du dictionnaire

• RLE excelle avec les longues séquences de caractères identiques

  • Ex: "aaaaaaaaaaaaaaaaaaaaaaaaabc" → 74.07% de compression
  • Avantages: Simple, rapide, très efficace sur séquences répétitives
  • Inconvénients: Peut augmenter la taille des données sans répétitions

• Sur les images, RLE s'est révélé inefficace car les pixels varient constamment, conduisant à une augmentation de taille (de 2.3Mo à 11.9Mo pour l'image "requin_leopard.ppm")

👨‍💻 Auteur

Bademba SANGARE - L3 Informatique - Université Paris 8