IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

Vous êtes nouveau sur Developpez.com ? Créez votre compte ou connectez-vous afin de pouvoir participer !

Vous devez avoir un compte Developpez.com et être connecté pour pouvoir participer aux discussions.

Vous n'avez pas encore de compte Developpez.com ? Créez-en un en quelques instants, c'est entièrement gratuit !

Si vous disposez déjà d'un compte et qu'il est bien activé, connectez-vous à l'aide du formulaire ci-dessous.

Identifiez-vous
Identifiant
Mot de passe
Mot de passe oublié ?
Créer un compte

L'inscription est gratuite et ne vous prendra que quelques instants !

Je m'inscris !

Comprendre l'algorithme de compression LZ77
Un billet de fbonhomm

Le , par fbonhomm

0PARTAGES

Avant-propos

Pour plus d’information et un code source, vous pouvez aller sur mon dépôt git: https://github.com/fbonhomm/LZ77

Sommaire
  • Définition
  • Fonctionnalités
  • Fonctionnement
  • Représentation binaire
  • Utilisation
  • Pseudo-Code


Définition

L'algorithme LZ77 est un algorithme de compression sans perte utilisant une fenêtre glissante.

On peut le retrouver sous différent nom comme Lempel Ziv 77 ou LZ1.

  • Une compression sans perte est une méthode de compression qui restitue après la décompression la même donnée que l’original.
  • Une compression par fenêtre glissante utilise une zone mémoire de recherche qui peut se mouvoir, cela évite à l'algorithme d'être trop gourmand en ressources.




Fonctionnalités

Comme on l'a vue précédemment, l’algorithme LZ77 utilise une fenêtre glissante comme l’a majorité des algorithmes de la famille LZ.
Cette fenêtre glissante est coupée en deux parties, une partie qui est le tampon et une autre qui le dictionnaire.
Le tampon est la partie lecture et le dictionnaire est la partie recherche.



Le but de cet algorithme est d’encoder une récurrence qui se trouve dans le tampon et le dictionnaire par la combinaison position/taille.



Fonctionnement

Le fonctionnement est simple, trouver le plus grand motif du tampon dans le dictionnaire.

Dans le tampon = "AABBCC"
Dans le dictionnaire = "RRYYIIAANNMMXX"

On commence à chercher:
  1. AABBCC
    NOT FOUND
  2. AABBC
    NOT FOUND
  3. AABB
    NOT FOUND
  4. AAB
    NOT FOUND
  5. AA
    FOUND RRYYIIAANNMMXX


On calcule la distance du motif trouvé jusqu'au tampon de lecture.
RRYYIIAANNMMXX” = 8

La longueur du motif trouvé est 2 (AA) et le prochain caractère du motif dans le tampon est B alors pour l'encodage on obtient (8, 2, B).

Si aucun motif est trouvé, l'encodage sera comme ça (0, 0, [premier caractère du tampon]), alors si aucun motif est trouvé dans l'exemple précédent, l’encodage sera (0, 0, A).

Pour résumer, si on trouve un motif ([distance], [taille], [prochain caractère]) et si aucun motif est trouvé (0, 0, [premier caractère du tampon])



Sur de la petite donnée, la partie encodée peut être plus grande que la donnée originale.

Mais sur de la grande donnée comme les misérables de Victor Hugo (tome 1):
  • Fichier original: 710 kilobytes
  • Fichier compressé: 420 kilobytes


Soit 40% de compression.



Représentation binaire

Pour la représentation binaire, les valeurs communément utilisées sont:
  • Dictionnaire: 12 bits soit 4095.
  • Tampon: 4 bits soit 15.


Soit encodé sur 2 octets.



Utilisation

Le LZ77 n'est plus utilisé, la forme LZSS sera privilégiée qui est une grande amélioration au niveau du taux de compression mais aussi au niveau rapidité compression/décompression.

Pseudo-Code

Voici un pseudo pour la partie compression:



Et la partie décompression:



Merci d’avoir lu cet article sur l’algorithme LZ77 qui est la première pierre à la construction d’une série d’algorithmes qui ne cessera d’optimiser la compression par dictionnaire.

Une erreur dans cette actualité ? Signalez-nous-la !