Sans pertes

Méthodes basées sur les répétitions Méthodes de type dictionnaire Méthodes statistiques

Avec pertes

La compression JPEG La compression fractale La compression par ondelettes

CONCLUSION

Conclusion Bibliographie

 

 

La première méthode consiste à reconnaître les répétitions et à trouver un alphabet pour recoder l'information. Le format compressé est divisé en 2 parties : la première (avant ##) définit un alphabet de mots séparés par des # qu'on appellera le dictionnaire, la seconde donne l'ordre des mots employés en utilisant leur numéro d'ordre d'apparition dans le dictionnaire.

Reprenons l'exemple ci-dessus, avec la phrase de 94 caractères. On sépare ici les mots par le caractère #, ce qui donne :

#ainsi #font #les petites marionnettes, ##1#2#2#2#3#1#2#2#2#3

La phrase comprend maintenant 60 caractères. Le caractère # ne doit pas faire partie de l'alphabet de départ.

La seconde méthode se nomme LZW, du nom de ses auteurs, Lempel, Ziw et Welch, vise à déceler des suites de bits ou d'octets similaires, autrement dit à identifier des motifs qui se retrouvent dans la succession de valeurs décrivant l'image. Chaque fois qu'une telle suite est rencontrée, l'algorithme la range dans un dictionnaire et lui affecte un identificateur, qui vient la remplacer les données d'origine. Les valeurs isolées sont conservées telles quelles. Les données sont alors communiquées par le dictionnaire accompagnées de la succession de codes d'identification et valeurs isolées.

Etant donné que cette méthode est de type dictionnaire, la compression et la décompression se font instantanément, et n'a pas besoin d'opération intermédiaire, car l'algorithme se réfère directement au dictionnaire. Les algorithmes vont utiliser un dictionnaire. C'est une structure de données dans laquelle nous allons stocker des mots rencontrés dans le texte ainsi que leur code associé. Le principe de l'algorithme de compression est de chercher à former des motifs de plus en plus longs. Dès qu'un motif est trouvé, il est inséré dans le dictionnaire et un code lui est associé.

On doit simplement construire des tables renfermant des centaines de mots courants et utiliser les index de ces tables pour la compression. Ces index sont construits dynamiquement, en examinant les données et en construisant une table basée sur cetexte. Évidemment, moins il y a de répétitions de mots dans le texte, moins efficace sera la compression.

Même si les techniques Huffman et LZW sont habituellement utilisées pour compresser du texte, le même concept peut être appliqué à d'autres structures telles que les graphiques, le son ou les structures composites.

Explication de l'algorithme de compression :

Après initialisation du dictionnaire, l'algorithme pourra lire et traiter les caractères les uns après les autres. Il construit un motif de plus en plus long. Si ce motif existe déjà dans le dictionnaire, il en construit un encore plus long.

Les tableaux ci-dessous, montrent sur la gauche l'évolution du dictionnaire et sur la droite, les codes émis lors de la compression. Le résultat de la compression à une taille de 81 bits. Le caractère "-" indique que pour un caractère lu, il n'y a pas de sortie.

Le taux de compression est donc de 1-118/304 = 61%. L'algorithme LZW est pénalisé par le fait qu'il faut conserver le dictionnaire entre la compression et la décompression (et il peut être relativement gros).
Le codes 111 et 11111 ne sont pas utilisés et sont réservés au changement de taille de codage. Après de code 1111, le codage passe à 5 bits par mot, et 11111 à 6.