Voir le flux RSS

fbonhomm

[Actualité] Comprendre l'algorithme de compression LZ77

Noter ce billet
par , 07/09/2020 à 09h00 (614 Affichages)
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.



Nom : sliding-window.gif
Affichages : 69
Taille : 355,2 Ko


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.

Nom : fonctionnaliter.fr.png
Affichages : 66
Taille : 119,7 Ko

​Le but de cet algorithme est d'encoder une récurrence par l'emplacement déjà vu.

Nom : encodage.png
Affichages : 67
Taille : 65,1 Ko

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])

Nom : fonctionnement.gif
Affichages : 66
Taille : 1,33 Mo

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é comme les misérables de Victor Hugo (tome 1):
  • Fichier original: 710 kilobytes
  • Fichier compressé: 420 kilobytes


Soit 40% de compression.

Nom : fonctionnement2.png
Affichages : 62
Taille : 89,3 Ko

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.

Nom : binary.png
Affichages : 62
Taille : 62,4 Ko

Utilisation

Le LZ77 n'est plus utilisée, la forme LZSS sera privilégié.

Pseudo-Code

Voici un pseudo pour la partie compression:

Nom : pseudo-code-compression.fr.png
Affichages : 61
Taille : 150,2 Ko

Et la partie décompression:

Nom : pseudo-code-decompression.fr.png
Affichages : 60
Taille : 118,4 Ko

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.

Envoyer le billet « Comprendre l'algorithme de compression LZ77 » dans le blog Viadeo Envoyer le billet « Comprendre l'algorithme de compression LZ77 » dans le blog Twitter Envoyer le billet « Comprendre l'algorithme de compression LZ77 » dans le blog Google Envoyer le billet « Comprendre l'algorithme de compression LZ77 » dans le blog Facebook Envoyer le billet « Comprendre l'algorithme de compression LZ77 » dans le blog Digg Envoyer le billet « Comprendre l'algorithme de compression LZ77 » dans le blog Delicious Envoyer le billet « Comprendre l'algorithme de compression LZ77 » dans le blog MySpace Envoyer le billet « Comprendre l'algorithme de compression LZ77 » dans le blog Yahoo

Mis à jour 07/09/2020 à 13h59 par fbonhomm

Catégories
Sans catégorie

Commentaires