Algorithme de Lempel-Ziv-Welch
Lycée Thiers
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 1 / 26
Algorithme de Lempel-Ziv-Welch
Lycée Thiers
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 2 / 26
1 Compression
2 Décompression
3 Taille des entiers de codage
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 3 / 26
Crédits
Un cours de Marc de Falco.
Wikipedia
Informatique -Cours et exercices corrigés- (MP2I-MPI) (ellipse)
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 4 / 26
Présentation
L’algorithme de Lempel-Ziv-Welch (LZW)est un algorithme de
compression de données sans perte.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 5 / 26
Présentation
L’algorithme de Lempel-Ziv-Welch (LZW)est un algorithme de
compression de données sans perte.
Ses inventeurs sont Abraham Lempel, Jakob Ziv qui l’ont proposé en
1977 et Terry Welch qui l’a finalisé en 1984.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 5 / 26
Présentation
L’algorithme de Lempel-Ziv-Welch (LZW)est un algorithme de
compression de données sans perte.
Ses inventeurs sont Abraham Lempel, Jakob Ziv qui l’ont proposé en
1977 et Terry Welch qui l’a finalisé en 1984.
LZW a été utilisé dans des modems aujourd’hui obsolètes mais on le
trouve encore dans la compression des images GIFF ou
TIFF et les fichiers audio MOD . Il est à la base de la
compression ZIP .
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 5 / 26
Présentation
L’algorithme de Lempel-Ziv-Welch (LZW)est un algorithme de
compression de données sans perte.
Ses inventeurs sont Abraham Lempel, Jakob Ziv qui l’ont proposé en
1977 et Terry Welch qui l’a finalisé en 1984.
LZW a été utilisé dans des modems aujourd’hui obsolètes mais on le
trouve encore dans la compression des images GIFF ou
TIFF et les fichiers audio MOD . Il est à la base de la
compression ZIP .
Facile à coder (c’est son principal avantage) il n’est souvent pas
optimal car il n’effectue qu’une analyse sommaire des données à
compresser.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 5 / 26
Compression
1 Compression
2 Décompression
3 Taille des entiers de codage
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 6 / 26
Compression
Principe
Rechercher dans le texte à compresser des répétitions de sous-chaı̂nes
identiques et leur donner une forme compacte dans le texte
compressé.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 7 / 26
Compression
Principe
Rechercher dans le texte à compresser des répétitions de sous-chaı̂nes
identiques et leur donner une forme compacte dans le texte
compressé.
L’algorithme LZW procède en une seule passe, en maintenant, au fur
et à mesure de la compression, l’ensemble des facteurs qu’il a déjà
rencontrés.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 7 / 26
Compression
Principe
Rechercher dans le texte à compresser des répétitions de sous-chaı̂nes
identiques et leur donner une forme compacte dans le texte
compressé.
L’algorithme LZW procède en une seule passe, en maintenant, au fur
et à mesure de la compression, l’ensemble des facteurs qu’il a déjà
rencontrés.
Cette caractéristique est adaptée à la compression d’un texte qu’on
découvre à la volée comme lorsque le texte est transmis via un canal
de communication.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 7 / 26
Compression
Préfixe, suffixe
Définition
Le mot x est appelé un préfixe du mot m si il existe un mot y tel que
m = x · y.
Exemple
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 8 / 26
Compression
Préfixe, suffixe
Définition
Le mot x est appelé un préfixe du mot m si il existe un mot y tel que
m = x · y.
Le mot x est appelé un suffixe du mot m si il existe un mot y tel que
m = y · x.
Exemple
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 8 / 26
Compression
Préfixe, suffixe
Définition
Le mot x est appelé un préfixe du mot m si il existe un mot y tel que
m = x · y.
Le mot x est appelé un suffixe du mot m si il existe un mot y tel que
m = y · x.
Exemple
ε, langage et lang sont des préfixes de langage,
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 8 / 26
Compression
Préfixe, suffixe
Définition
Le mot x est appelé un préfixe du mot m si il existe un mot y tel que
m = x · y.
Le mot x est appelé un suffixe du mot m si il existe un mot y tel que
m = y · x.
Exemple
ε, langage et lang sont des préfixes de langage,
ε, langage et gage sont des suffixes de langage,
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 8 / 26
Compression
Préfixe, suffixe
Définition
Le mot x est appelé un préfixe du mot m si il existe un mot y tel que
m = x · y.
Le mot x est appelé un suffixe du mot m si il existe un mot y tel que
m = y · x.
Exemple
ε, langage et lang sont des préfixes de langage,
ε, langage et gage sont des suffixes de langage,
Si xu = m et xv = m alors, par régularité, u = v .
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 8 / 26
Compression
Facteurs
Définition
On dit qu’un mot x est facteur d’un mot m s’il existe u, v , deux mots tels
que m = uxv .
Le mot x = x1 . . . xn où les xi sont des caractères est un sous-mot de m s’il
existe n − 1 mots u1 , . . . , un−1 tels que x1 u1 x2 u2 . . . xn−1 un−1 xn est un
facteur de m.
Exemple
Le mot sol est facteur de insolent. ilet est un sous-mot de insolent.
Pour plus d’informations sur la théorie des mots, voir par exemple ce cours.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 9 / 26
Compression
Table des correspondances facteurs/encodage
L’algorithme de compression construit une table de traduction des
facteurs du texte en parcourant le texte à compresser.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 10 / 26
Compression
Table des correspondances facteurs/encodage
L’algorithme de compression construit une table de traduction des
facteurs du texte en parcourant le texte à compresser.
Cette table relie des codes de taille (le plus souvent) fixée
(généralement à 12 bits) aux chaı̂nes de caractères. Certaines
implémentations avec taille d’encodage variable existent aussi.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 10 / 26
Compression
Table des correspondances facteurs/encodage
L’algorithme de compression construit une table de traduction des
facteurs du texte en parcourant le texte à compresser.
Cette table relie des codes de taille (le plus souvent) fixée
(généralement à 12 bits) aux chaı̂nes de caractères. Certaines
implémentations avec taille d’encodage variable existent aussi.
La table est initialisée avec tous les caractères (256 entrées dans le
cas de caractères codés sur 8 bits). C’est une injection qui associe une
valeur numérique à tout caractère de l’alphabet.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 10 / 26
Compression
Table des correspondances facteurs/encodage
L’algorithme de compression construit une table de traduction des
facteurs du texte en parcourant le texte à compresser.
Cette table relie des codes de taille (le plus souvent) fixée
(généralement à 12 bits) aux chaı̂nes de caractères. Certaines
implémentations avec taille d’encodage variable existent aussi.
La table est initialisée avec tous les caractères (256 entrées dans le
cas de caractères codés sur 8 bits). C’est une injection qui associe une
valeur numérique à tout caractère de l’alphabet.
Il est malin d’utiliser un dictionnaire (facteur, encodage). Les seules
clés du dictionnaires qui ne sont pas des facteurs du texte sont les
caractères de l’alphabet non utilisés par le texte.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 10 / 26
Compression
Table des correspondances facteurs/encodage
L’algorithme de compression construit une table de traduction des
facteurs du texte en parcourant le texte à compresser.
Cette table relie des codes de taille (le plus souvent) fixée
(généralement à 12 bits) aux chaı̂nes de caractères. Certaines
implémentations avec taille d’encodage variable existent aussi.
La table est initialisée avec tous les caractères (256 entrées dans le
cas de caractères codés sur 8 bits). C’est une injection qui associe une
valeur numérique à tout caractère de l’alphabet.
Il est malin d’utiliser un dictionnaire (facteur, encodage). Les seules
clés du dictionnaires qui ne sont pas des facteurs du texte sont les
caractères de l’alphabet non utilisés par le texte.
L’algorithme LZW exploite et modifie à la volée le dictionnaire des
facteurs. Il renvoie une liste de clés de ce dictionnaire (c’est à dire une
liste d’entiers), chacune codant un facteur du texte.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 10 / 26
Compression
Algorithme
Listing 1 – Algorithme LZW
1 /∗L ’ a l p h a b e t Σ e s t s u p p o s é connu ∗/
2 f o n c t i o n lzw compress (t : t e x t e ) :
3 i n i t i a l i s e r d a v e c Σ /∗ d i c t i o n n a i r e ( f a c t e u r , c o d e ) ∗/
4 w ← ε ; /∗ l e f a c t e u r c o u r a n t ∗/
5 t 0 ← ε ; /∗ l e t e x t e c o m p r e s s é ∗/
6 n ← |Σ| ; /∗ nombre de f a c t e u r s dé j à c o m p r e s s é s ∗/
7 tant que t n ’ e s t pas v i d e f a i r e :
8 c ← t[0] ; /∗ 1 e r e l e t t r e de t ∗/
9 t ← t[1 :]/∗ s u p p r i m e r l a 1 e r e l e t t r e de t ∗/
10 p ← w + c ; /∗ a j o u t e r une l e t t r e à w ∗/
11 s i p e s t une c l é de d :
12 w ← p;
13 sinon :
14 d[p] ← n ; /∗ a j o u t e r l ’ a s s o c i a t i o n (p, n)∗/
15 n++;/∗ i n c r é m e n t e r l e nb de c o d e s e n r e g i s t r é s ∗/
16 /∗ r q e : n = |d| : nb de c l é s d a n s l e d i c o ∗/
17 t 0 ← t 0 + d[w ] ; /∗ a j o u t e r l e c o d e de w à t 0 ∗/
18 w ←c;
19 t 0 ← t 0 + d[w ] ;
20 r e n v o y e r t0
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 11 / 26
Compression
Invariant
Avec les conventions du code ci-dessus :
Si on considère (artificiellement) que ε est une clé du dictionnaire (par
exemple encodée par −1) alors w est une clé du dictionnaire est un
invariant de boucle.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 12 / 26
Compression
Exemple (Wikipedia)
On veut compresser ”TOBEORNOTTOBEORTOBEORNOT”.
Initialisation de d : (A :65) ... (T :84), (O :79), (B :66), (E :69),
(R :82), (N :78) ... (Z :90) ... (\255,255) et t 0 ← ε (texte compressé)
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 13 / 26
Compression
Exemple (Wikipedia)
On veut compresser ”TOBEORNOTTOBEORTOBEORNOT”.
Initialisation de d : (A :65) ... (T :84), (O :79), (B :66), (E :69),
(R :82), (N :78) ... (Z :90) ... (\255,255) et t 0 ← ε (texte compressé)
Position 0 : T est une clé mais pas TO. d[TO] ← 255 + 1 = 256,
t 0 ← 84
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 13 / 26
Compression
Exemple (Wikipedia)
On veut compresser ”TOBEORNOTTOBEORTOBEORNOT”.
Initialisation de d : (A :65) ... (T :84), (O :79), (B :66), (E :69),
(R :82), (N :78) ... (Z :90) ... (\255,255) et t 0 ← ε (texte compressé)
Position 0 : T est une clé mais pas TO. d[TO] ← 255 + 1 = 256,
t 0 ← 84
Position 1 : O est une clé mais pas OB. d[OB] ← 257, t 0 ← 84, 79
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 13 / 26
Compression
Exemple (Wikipedia)
On veut compresser ”TOBEORNOTTOBEORTOBEORNOT”.
Initialisation de d : (A :65) ... (T :84), (O :79), (B :66), (E :69),
(R :82), (N :78) ... (Z :90) ... (\255,255) et t 0 ← ε (texte compressé)
Position 0 : T est une clé mais pas TO. d[TO] ← 255 + 1 = 256,
t 0 ← 84
Position 1 : O est une clé mais pas OB. d[OB] ← 257, t 0 ← 84, 79
Position 2 : B est une clé mais pas BE. d[BE] ← 258, t 0 ← 84, 79, 66
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 13 / 26
Compression
Exemple (Wikipedia)
On veut compresser ”TOBEORNOTTOBEORTOBEORNOT”.
Initialisation de d : (A :65) ... (T :84), (O :79), (B :66), (E :69),
(R :82), (N :78) ... (Z :90) ... (\255,255) et t 0 ← ε (texte compressé)
Position 0 : T est une clé mais pas TO. d[TO] ← 255 + 1 = 256,
t 0 ← 84
Position 1 : O est une clé mais pas OB. d[OB] ← 257, t 0 ← 84, 79
Position 2 : B est une clé mais pas BE. d[BE] ← 258, t 0 ← 84, 79, 66
Position 3 : E est une clé mais pas EO. d[EO] ← 259,
t 0 ← 84, 79, 66, 69
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 13 / 26
Compression
Exemple (Wikipedia)
On veut compresser ”TOBEORNOTTOBEORTOBEORNOT”.
Initialisation de d : (A :65) ... (T :84), (O :79), (B :66), (E :69),
(R :82), (N :78) ... (Z :90) ... (\255,255) et t 0 ← ε (texte compressé)
Position 0 : T est une clé mais pas TO. d[TO] ← 255 + 1 = 256,
t 0 ← 84
Position 1 : O est une clé mais pas OB. d[OB] ← 257, t 0 ← 84, 79
Position 2 : B est une clé mais pas BE. d[BE] ← 258, t 0 ← 84, 79, 66
Position 3 : E est une clé mais pas EO. d[EO] ← 259,
t 0 ← 84, 79, 66, 69
Position 4 : O est une clé mais pas OR. d[OR] ← 260,
t 0 ← 84, 79, 66, 69, 79
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 13 / 26
Compression
Exemple (Wikipedia)
On veut compresser ”TOBEORNOTTOBEORTOBEORNOT”.
Initialisation de d : (A :65) ... (T :84), (O :79), (B :66), (E :69),
(R :82), (N :78) ... (Z :90) ... (\255,255) et t 0 ← ε (texte compressé)
Position 0 : T est une clé mais pas TO. d[TO] ← 255 + 1 = 256,
t 0 ← 84
Position 1 : O est une clé mais pas OB. d[OB] ← 257, t 0 ← 84, 79
Position 2 : B est une clé mais pas BE. d[BE] ← 258, t 0 ← 84, 79, 66
Position 3 : E est une clé mais pas EO. d[EO] ← 259,
t 0 ← 84, 79, 66, 69
Position 4 : O est une clé mais pas OR. d[OR] ← 260,
t 0 ← 84, 79, 66, 69, 79
Position 5 : R est une clé mais pas RN. d[RN] ← 261, Puis N est une
clé mais pas NO. t 0 ← 84, 79, 66, 69, 79, 82, 78
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 13 / 26
Compression
Exemple (Wikipedia)
On veut compresser ”TOBEORNOTTOBEORTOBEORNOT”.
Position 7 : O est une clé mais pas OT. d[OT] ← 263,
t 0 ← 84, 79, 66, 69, 79, 82, 78, 79. T est une clé mais pas TT.
d[TT] ← 264, t 0 ← 84, 79, 66, 69, 79, 82, 78, 79, 84
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 14 / 26
Compression
Exemple (Wikipedia)
On veut compresser ”TOBEORNOTTOBEORTOBEORNOT”.
Position 7 : O est une clé mais pas OT. d[OT] ← 263,
t 0 ← 84, 79, 66, 69, 79, 82, 78, 79. T est une clé mais pas TT.
d[TT] ← 264, t 0 ← 84, 79, 66, 69, 79, 82, 78, 79, 84
Position 9 : T, TO sont des clés mais pas TOB. d[TOB] ← 265,
t 0 ← 84, 79, 66, 69, 79, 82, 78, 79, 84, 256
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 14 / 26
Compression
Exemple (Wikipedia)
On veut compresser ”TOBEORNOTTOBEORTOBEORNOT”.
Position 7 : O est une clé mais pas OT. d[OT] ← 263,
t 0 ← 84, 79, 66, 69, 79, 82, 78, 79. T est une clé mais pas TT.
d[TT] ← 264, t 0 ← 84, 79, 66, 69, 79, 82, 78, 79, 84
Position 9 : T, TO sont des clés mais pas TOB. d[TOB] ← 265,
t 0 ← 84, 79, 66, 69, 79, 82, 78, 79, 84, 256
Position 11 : B, BE sont des clés mais pas BEO. d[BEO] ← 266,
t 0 ← 84, 79, 66, 69, 79, 82, 78, 79, 84, 256, 258 etc.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 14 / 26
Compression
Exemple (Wikipedia)
On veut compresser ”TOBEORNOTTOBEORTOBEORNOT”.
Position 7 : O est une clé mais pas OT. d[OT] ← 263,
t 0 ← 84, 79, 66, 69, 79, 82, 78, 79. T est une clé mais pas TT.
d[TT] ← 264, t 0 ← 84, 79, 66, 69, 79, 82, 78, 79, 84
Position 9 : T, TO sont des clés mais pas TOB. d[TOB] ← 265,
t 0 ← 84, 79, 66, 69, 79, 82, 78, 79, 84, 256
Position 11 : B, BE sont des clés mais pas BEO. d[BEO] ← 266,
t 0 ← 84, 79, 66, 69, 79, 82, 78, 79, 84, 256, 258 etc.
Au final
84; 79; 66; 69; 79; 82; 78; 79; 84; 256; 258; 260; 265; 259; 261; 263
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 14 / 26
Compression
Exemple (Wikipedia)
On veut compresser ”TOBEORNOTTOBEORTOBEORNOT”.
Position 15 : T,TO,TOB sont des clés mais pas TOBE.
d[TOBE] ← 268,
t 0 ← 84, 79, 66, 69, 79, 78, 79, 84, 84, 256, 258, 260, 265
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 15 / 26
Compression
Exemple (Wikipedia)
On veut compresser ”TOBEORNOTTOBEORTOBEORNOT”.
Position 15 : T,TO,TOB sont des clés mais pas TOBE.
d[TOBE] ← 268,
t 0 ← 84, 79, 66, 69, 79, 78, 79, 84, 84, 256, 258, 260, 265
Position 18 : E,EO sont des clés mais pas EOR. d[EOR] ← 269,
t 0 ← 84, 79, 66, 69, 79, 78, 79, 84, 84, 256, 258, 260, 265, 259
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 15 / 26
Compression
Exemple (Wikipedia)
On veut compresser ”TOBEORNOTTOBEORTOBEORNOT”.
Position 15 : T,TO,TOB sont des clés mais pas TOBE.
d[TOBE] ← 268,
t 0 ← 84, 79, 66, 69, 79, 78, 79, 84, 84, 256, 258, 260, 265
Position 18 : E,EO sont des clés mais pas EOR. d[EOR] ← 269,
t 0 ← 84, 79, 66, 69, 79, 78, 79, 84, 84, 256, 258, 260, 265, 259
Position 20 : R,RN sont des clés mais pas RNO. d[RNO] ← 270,
t 0 ← 84, 79, 66, 69, 79, 78, 79, 84, 84, 256, 258, 260, 265, 259, 261
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 15 / 26
Compression
Exemple (Wikipedia)
On veut compresser ”TOBEORNOTTOBEORTOBEORNOT”.
Position 15 : T,TO,TOB sont des clés mais pas TOBE.
d[TOBE] ← 268,
t 0 ← 84, 79, 66, 69, 79, 78, 79, 84, 84, 256, 258, 260, 265
Position 18 : E,EO sont des clés mais pas EOR. d[EOR] ← 269,
t 0 ← 84, 79, 66, 69, 79, 78, 79, 84, 84, 256, 258, 260, 265, 259
Position 20 : R,RN sont des clés mais pas RNO. d[RNO] ← 270,
t 0 ← 84, 79, 66, 69, 79, 78, 79, 84, 84, 256, 258, 260, 265, 259, 261
Position 22 à fin : O,OT sont des clés.
t 0 ← 84, 79, 66, 69, 79, 78, 79, 84, 84, 256, 258, 260, 265, 259, 261, 263
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 15 / 26
Décompression
1 Compression
2 Décompression
3 Taille des entiers de codage
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 16 / 26
Décompression
Initialisation
On note d le dictionnaire (code,facteur) qui est l’inverse de celui de la
partie précédente (en fait, puisque l’ensemble des codes forme un
intervalle de nombres, un simple tableau redimensionnable suffit).
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 17 / 26
Décompression
Initialisation
On note d le dictionnaire (code,facteur) qui est l’inverse de celui de la
partie précédente (en fait, puisque l’ensemble des codes forme un
intervalle de nombres, un simple tableau redimensionnable suffit).
Ce dictionnaire est initialisé ainsi : à tous les codes entre (par exemple
0 et 256) on associe la lettre correspondante de l’alphabet.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 17 / 26
Décompression
Initialisation
On note d le dictionnaire (code,facteur) qui est l’inverse de celui de la
partie précédente (en fait, puisque l’ensemble des codes forme un
intervalle de nombres, un simple tableau redimensionnable suffit).
Ce dictionnaire est initialisé ainsi : à tous les codes entre (par exemple
0 et 256) on associe la lettre correspondante de l’alphabet.
La notation |d| désigne le nombre d’associations déjà entrées. Avec le
code ASCII, |d| = 256 au départ.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 17 / 26
Décompression
Initialisation
On note d le dictionnaire (code,facteur) qui est l’inverse de celui de la
partie précédente (en fait, puisque l’ensemble des codes forme un
intervalle de nombres, un simple tableau redimensionnable suffit).
Ce dictionnaire est initialisé ainsi : à tous les codes entre (par exemple
0 et 256) on associe la lettre correspondante de l’alphabet.
La notation |d| désigne le nombre d’associations déjà entrées. Avec le
code ASCII, |d| = 256 au départ.
Le premier code c lu est nécessairement celui d’un unique caractère.
On écrit donc d[c] dans le fichier de sortie et on garde c en mémoire.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 17 / 26
Décompression
Déroulement
Cas facile : on lit un code connu
On garde en mémoire le précédent code lu c. On lit un code n où n < |d|
(ce qui signifie qu’on sait ce que code n) :
Posons d[n] = xm0 ; x est un caractère et m0 un mot.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 18 / 26
Décompression
Déroulement
Cas facile : on lit un code connu
On garde en mémoire le précédent code lu c. On lit un code n où n < |d|
(ce qui signifie qu’on sait ce que code n) :
Posons d[n] = xm0 ; x est un caractère et m0 un mot.
On écrit xm0 dans le fichier de sortie
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 18 / 26
Décompression
Déroulement
Cas facile : on lit un code connu
On garde en mémoire le précédent code lu c. On lit un code n où n < |d|
(ce qui signifie qu’on sait ce que code n) :
Posons d[n] = xm0 ; x est un caractère et m0 un mot.
On écrit xm0 dans le fichier de sortie
On rajoute ensuite un nouvel élément mx dans le dictionnaire où
m = d[c]. On pose donc d[|d|] = mx.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 18 / 26
Décompression
Déroulement
Cas facile : Pourquoi cela marche-t-il ?
On reproduit en fait le processus de compression mais en remplissant
le dictionnaire avec un temps de retard.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 19 / 26
Décompression
Déroulement
Cas facile : Pourquoi cela marche-t-il ?
On reproduit en fait le processus de compression mais en remplissant
le dictionnaire avec un temps de retard.
Selon le principe de compression :
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 19 / 26
Décompression
Déroulement
Cas facile : Pourquoi cela marche-t-il ?
On reproduit en fait le processus de compression mais en remplissant
le dictionnaire avec un temps de retard.
Selon le principe de compression :
On ajoute une entrée au dictionnaire pour mx quand on lit x et que le
précédent motif lu est m.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 19 / 26
Décompression
Déroulement
Cas facile : Pourquoi cela marche-t-il ?
On reproduit en fait le processus de compression mais en remplissant
le dictionnaire avec un temps de retard.
Selon le principe de compression :
On ajoute une entrée au dictionnaire pour mx quand on lit x et que le
précédent motif lu est m.
Le code c de m (qui est connu, sinon on ne serait pas arrivé à x) est
ajouté au texte codé.
Dans la décompression, quand on lit c, on ajoute m
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 19 / 26
Décompression
Déroulement
Cas facile : Pourquoi cela marche-t-il ?
On reproduit en fait le processus de compression mais en remplissant
le dictionnaire avec un temps de retard.
Selon le principe de compression :
On ajoute une entrée au dictionnaire pour mx quand on lit x et que le
précédent motif lu est m.
Le code c de m (qui est connu, sinon on ne serait pas arrivé à x) est
ajouté au texte codé.
Dans la décompression, quand on lit c, on ajoute m
On repart alors avec x comme motif lu (dans la compression)
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 19 / 26
Décompression
Déroulement
Cas problématique : n = |d|
Le code n lu est tel que n = |d|, donc on lit un code non encore présent
dans la table de décompression.
On lit le code n : il a été placé à cet endroit au moment de la
compression après avoir lu un wy . Ainsi, n est le code de w .
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 20 / 26
Décompression
Déroulement
Cas problématique : n = |d|
Le code n lu est tel que n = |d|, donc on lit un code non encore présent
dans la table de décompression.
On lit le code n : il a été placé à cet endroit au moment de la
compression après avoir lu un wy . Ainsi, n est le code de w .
n est maximal parmi les codes déjà rencontrés. Revenant au moment
de la compression, cela signifie que w est le dernier facteur qui a
produit un code avant d’écrire n.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 20 / 26
Décompression
Déroulement
Cas problématique : n = |d|
Le code n lu est tel que n = |d|, donc on lit un code non encore présent
dans la table de décompression.
On lit le code n : il a été placé à cet endroit au moment de la
compression après avoir lu un wy . Ainsi, n est le code de w .
n est maximal parmi les codes déjà rencontrés. Revenant au moment
de la compression, cela signifie que w est le dernier facteur qui a
produit un code avant d’écrire n.
Or, juste avant n dans le texte compressé, il y a c (lequel code m).
Ainsi w est de la forme mx.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 20 / 26
Décompression
Déroulement
Cas problématique : n = |d|
Le code n lu est tel que n = |d|, donc on lit un code non encore présent
dans la table de décompression.
On lit le code n : il a été placé à cet endroit au moment de la
compression après avoir lu un wy . Ainsi, n est le code de w .
n est maximal parmi les codes déjà rencontrés. Revenant au moment
de la compression, cela signifie que w est le dernier facteur qui a
produit un code avant d’écrire n.
Or, juste avant n dans le texte compressé, il y a c (lequel code m).
Ainsi w est de la forme mx.
Dans la compression, après avoir lu w = mx, on repart de x et on lit
wy , c.a.d. mxy . Ainsi, la 1ere lettre de m est x ! (dans le texte
originel, on a donc . . . mmxy . . . ).
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 20 / 26
Décompression
Déroulement
Cas problématique : n = |d|
Le code n lu est tel que n = |d|, donc on lit un code non encore présent
dans la table de décompression.
On lit le code n : il a été placé à cet endroit au moment de la
compression après avoir lu un wy . Ainsi, n est le code de w .
n est maximal parmi les codes déjà rencontrés. Revenant au moment
de la compression, cela signifie que w est le dernier facteur qui a
produit un code avant d’écrire n.
Or, juste avant n dans le texte compressé, il y a c (lequel code m).
Ainsi w est de la forme mx.
Dans la compression, après avoir lu w = mx, on repart de x et on lit
wy , c.a.d. mxy . Ainsi, la 1ere lettre de m est x ! (dans le texte
originel, on a donc . . . mmxy . . . ).
On ajoute mx au texte décompressé et on réalise l’association
d[n] = mx.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 20 / 26
Décompression
Cas problématique : n = |d|
n code un wy tel que le code de w est le dernier lu.
codé par n
w y
m x
codé par c
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 21 / 26
Décompression
Algorithme
On initialise le dictionnaire avec l’alphabet (par exemple alphabet ASCII
des caractères codés sur 8 bits). La fonction Lire lit le code courant de T 0
et positionne le curseur sur le code suivant.
Listing 2 – Décompression
1 f o n c t i o n l z w d e c o m p r e s s ( T 0 : t e x t e c o m p r e s s é ,
2 d : d i c t i o n n a i r e ( code , f a c t e u r ) ) :
3 c ← Lire(T 0 ) ; /∗ 1 e r c o d e l u ∗/
4 /∗ l e 1 e r c o d e c o r r e s p o n d t o u j o u r s à une l e t t r e ∗/
5 Ecrire (d[c]) ; /∗ a j o u t e r l e t e x t e cod é p a r c ∗/
6 t a n t q u e i l r e s t e un c o d e non l u de T 0 f a i r e
7 n ← Lire(T 0 ) ; /∗ c o d e c o u r a n t ∗/
8 s i n e s t une c l e f de d /∗ c o d e n dé j à r e n c o n t r é ∗/
9 a l o r s e ← d[n] ; /∗ dé c o m p r e s s i o n ∗/
10 d[|d|] ← d[c] · e[0] /∗ n o u v e l l e a s s o c i a t i o n ∗/
11 s i n o n /∗ dé c o m p r e s s i o n , c a s n = |d|∗/
12 e ← d[c] · d[c][0] ;
13 d[|d|] ← e /∗ n o u v e l l e a s s o c i a t i o n ∗/
14 Ecrire (e) ;
15 c←n
16 fin faire
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 22 / 26
Taille des entiers de codage
1 Compression
2 Décompression
3 Taille des entiers de codage
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 23 / 26
Taille des entiers de codage
Taille des entiers en OCaml
En OCaml, les entiers sont un bit plus court que les entiers machines. Sur
la plupart des machines, les entiers sont de taille 32 ou 64 bits. En OCaml,
les entiers sont donc de taille 31 ou 63 bits.
Or, le premier bit est un bit de signe, les entiers positifs sont donc codés
entre 0 et 230 − 1 (ou 262 − 1).
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 24 / 26
Taille des entiers de codage
La représentation du résultat de la compression par une liste d’entiers
OCAML n’est pas très réaliste : il faudrait a priori 30 bits (ou 62) pour
stocker chaque entier. Cependant, on remarque que la taille des entiers
produits par l’algorithme de compression croı̂t progressivement au fur et à
mesure que l’on avance dans la liste (et que le dictionnaire se remplit).
Dans la pratique, on peut donc utiliser la technique suivante pour coder la
liste :
Tant que tous les entiers sont strictement inférieurs à 255, coder ces
entiers sur 8 bits.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 25 / 26
Taille des entiers de codage
La représentation du résultat de la compression par une liste d’entiers
OCAML n’est pas très réaliste : il faudrait a priori 30 bits (ou 62) pour
stocker chaque entier. Cependant, on remarque que la taille des entiers
produits par l’algorithme de compression croı̂t progressivement au fur et à
mesure que l’on avance dans la liste (et que le dictionnaire se remplit).
Dans la pratique, on peut donc utiliser la technique suivante pour coder la
liste :
Tant que tous les entiers sont strictement inférieurs à 255, coder ces
entiers sur 8 bits.
Lorsque l’on rencontre le premier entier supérieur ou égal à 255,
émettre la séquence 11111111 (huit fois le bit 1) et continuer, tant
que les entiers sont strictement inférieurs à 511, en codant les entiers
sur 9 bits.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 25 / 26
Taille des entiers de codage
La représentation du résultat de la compression par une liste d’entiers
OCAML n’est pas très réaliste : il faudrait a priori 30 bits (ou 62) pour
stocker chaque entier. Cependant, on remarque que la taille des entiers
produits par l’algorithme de compression croı̂t progressivement au fur et à
mesure que l’on avance dans la liste (et que le dictionnaire se remplit).
Dans la pratique, on peut donc utiliser la technique suivante pour coder la
liste :
Tant que tous les entiers sont strictement inférieurs à 255, coder ces
entiers sur 8 bits.
Lorsque l’on rencontre le premier entier supérieur ou égal à 255,
émettre la séquence 11111111 (huit fois le bit 1) et continuer, tant
que les entiers sont strictement inférieurs à 511, en codant les entiers
sur 9 bits.
Lorsque l’on rencontre le premier entier supérieur ou égal à 511,
émettre la séquence 111111111 (neuf fois le bit 1) et continuer, tant
que les entiers sont strictement inférieurs à 1023, en codant les
entiers sur 10 bits.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 25 / 26
Taille des entiers de codage
De manière générale, tant que les entiers considérés sont strictement
inférieurs à n = 2k − 1, on peut les représenter sur k bits.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 26 / 26
Taille des entiers de codage
De manière générale, tant que les entiers considérés sont strictement
inférieurs à n = 2k − 1, on peut les représenter sur k bits.
Lorsque le premier entier supérieur ou égal à 2k − 1 est rencontré, on
émet la séquence 1 . . . 1 (k fois le bit 1) et on continue en codant les
entiers sur k + 1 bits.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 26 / 26
Taille des entiers de codage
De manière générale, tant que les entiers considérés sont strictement
inférieurs à n = 2k − 1, on peut les représenter sur k bits.
Lorsque le premier entier supérieur ou égal à 2k − 1 est rencontré, on
émet la séquence 1 . . . 1 (k fois le bit 1) et on continue en codant les
entiers sur k + 1 bits.
Donc si le code 10 se trouve au début de la liste des codages, il prend
8 bits d’espace mais après le premier nombre plus grand que 255, il
prend 9 bits etc.
( Lycée Thiers ) Algorithme de Lempel-Ziv-Welch 26 / 26