<<< Previous

Exposé DEA/EDIIS - Stockage et compression 4/8

Next >>>

• on cherche la méthode la plus concise possible pour coder l'information
• plus on compresse, plus on a besoin de temps machine et de mémoire vive
• le taux de compression est assez faible (environ 1:1,5 à 1:2 en moyenne)

Méthode 1 : Run Length Encoding (RLE)

• on applique le principe de factorisation : dès que le même code est rencontré de manière successive, on compte les itérations
• avantages : simple et rapide !
• inconvénients : le document compressé peut devenir plus volumineux que l'original (dans le cas d'une implémentation simpliste)

Exemple : ABAACCAAA = 1x1, 1xB, 2xA, 2xC, 3xA

Méthode 2 : codage de Huffman

• dans un flot de données, certains symboles sont plus redondants que d'autres
• on se propose de coder les symboles les plus courants par les codes les plus courts
• avantages et inconvénients : identiques au RLE, avec toutefois la possibilité d'optimiser l'algorithme pour un type de donnée spécifique (texte, image, audio...)

Exemple : code ASCII sur 7 bits. Pourquoi ne pas utiliser 2 ou 3 bits pour les 'e', 'a' et autres lettres courantes dans un document texte ?

Méthode 3 : Lempel-Ziv (LZ77, LZ78)

• l'algorithme exploite les redondances de morceaux de séquence, il s'adapte donc mieux au document que les algorithmes précédents
• avantages : l'implémentation est relativement simple, utilisation généraliste possible
• inconvénients : gourmand en mémoire et temps de calcul