Faculté d'Electronique et d'Informatique (USTHB)

Master Réseau Radio-Mobile M1 (RRM)

Enseignant : Pr. M. BOUZID

MODULE : CODAGE et COMPRESSION

Solution - EXERCICES Chapitre 2 (Suite)

Exercice 5 :

1)- Codage du message texte sir∪sid∪eastman∪easily par la méthode LZ78 :

Etape (1) : Division du message en segments de caractères :

ε |s| |i| |r| |∪| |si| |d| |∪e| |a| |st| |m| |an| |∪ea| |sil| |y|

Construction du Dictionnaire et code en sortie LZ78 du message texte:

Algorithme LZ78 sous forme de tableau :

Tableau: Dictionnaire LZ78 et code en sortie du message texte

Dictionnaire Code en sortie

Entrée (mot) Index
ε 0
s 1 (0, s)
i 2 (0, i)
r 3 (0, r)
∪ 4 (0, ∪)
si 5 (1, i)
d 6 (0, d)
∪e 7 (4, e)
a 8 (0, a)
st 9 (1, t)
m 10 (0, m)
an 11 (8, n)
∪ea 12 (7, a)
sil 13 (5, l)
y 14 (0, y)

Dictionnaire :
Index : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Entrée : s i r ∪ si d ∪e a st m an ∪ea sil y

Code en sortie : (0, s) (0, i) (0, r) (0, ∪) (1, i) (0, d) (4, e) (0, a) (1, t) (0, m) (8, n) (7, a) (5, l)
(0, y)

Code LZ78 en sortie : (0, s) (0, i) (0, r) (0, ∪) (1, i) (0, d) (4, e) (0, a) (1, t) (0, m) (8, n) (7, a)
(5, l) (0, y).
Master RRM– USTHB, Pr. M. BOUZID Exercices - Chapitre 2 : Codage sans perte d'information

2)- Flux binaire en sortie (bitstream LZ78) :

- On commence par écrire les indices en binaire sur log 2 (i) :

( , s) (0, i) (00, r) (00, ∪) (001, i) (000, d) (100, e) (000, a) (0001, t) (0000, m) (1000, n)
0 bit 1bit |--2 bits--||----------3 bits----------||------------- 4 bits --

(0111, a) (0101, l) (0000, y)

----------------------|

- Enfin, on écrit les symboles en code ASCII sur 8 bits. Cela donne le flux de bits envoyé en binaire.

On a besoin donc de : (0+8) + (1+8) + 2 × (2+8) + 4 × (3+8) + 6 × (4+8)

= 8 + 9 + 20 + 44 + 72 = 153 bits

- Sans codage LZ78, le message original de l'exemple précédent (22 symboles en ASCII) serait écrit
sur: 22 × 8 = 176 bits.

3)- Taux et pourcentage de compression obtenu par le codage LZ78 :

Le taux de compression obtenu par le codage LZ78 sur l'exemple précédent est :

153
Taux compression = = 0.87
176

176 − 153
Ce qui donne un pourcentage de compression de : Pourcentage compression = % = 13.07%
176

Exercice 6 :

1)- Décodage LZ78 de la séquence de code suivante : (0, s) (0, i) (0, r) (0, ∪) (1, i) (0, d) (4, e) (0, a)
(1, t) (0, m) (8, n) (7, a) (5, l) (0, y)

Algorithme de décodage LZ78 sous forme de tableau :

Code LZ78 en Sortie Dictionnaire

entrée : (i, c) Décodage Index Mot
(0, s) s 1 s
(0, i) i 2 i
(0, r) r 3 r
(0, ∪) ∪ 4 ∪
(1, i) si 5 si
(0, d) d 6 d
(4, e) ∪e 7 ∪e
(0, a) a 8 a
(1, t) st 9 st
(0, m) m 10 m
(8, n) an 11 an
(7, a) ∪ea 12 ∪ea
(5, l) sil 13 sil
(0, y) y 14 y

2
Master RRM– USTHB, Pr. M. BOUZID Exercices - Chapitre 2 : Codage sans perte d'information

2)- On lit le message décodé sur la colonne sortie Décodage. On retrouve bien le message original
(Sortie décodage LZ78) : sir∪sid∪eastman∪easily

Exercice 7 :

Dictionnaire LZW:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 ……. 256
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z espace ……. 9

- Codage LZW du message AAABAABBBB en utilisant le principe de la méthode LZW :

Message à compresser : AAABAABBBB

– Le premier caractère lu est A. Il est dans le dictionnaire (on met A dans un tampon).
On lit le caractère suivant et on le concatène avec le contenu du tampon (caractère précédent A). On
forme ainsi la chaine AA (Elle n’est pas dans le dictionnaire).
→ On l’ajoute donc au dictionnaire LZW en lui affectant une nouvelle entrée à l’adresse 257.
→ On envoie le code en sortie LZW (du tampon) correspondant à A (1).

– Un nouveau mot venant d’être ajouté, on reprend alors au dernier caractère pris en compte (ici
A). On lit le caractère suivant et on le concatène avec A. On forme donc la chaine AA (elle est dans le
dictionnaire et on la met dans un tampon). Le caractère suivant est concaténé avec le contenu du
tampon, ce qui forme la chaine AAB (elle n'est pas dans le dictionnaire).

→ On l’ajoute donc au dictionnaire LZW en lui affectant une nouvelle entrée à l’adresse 258.
→ On envoie le code en sortie LZW (du tampon) correspondant à AA (257).

– On reprend alors au dernier caractère pris en compte (ici B). On lit le caractère suivant et on le
concatène avec B, formant ainsi la chaine BA (elle n'est pas dans le dictionnaire).
→ On l’ajoute donc au dictionnaire LZW en lui affectant une nouvelle entrée à l’adresse 259.
→ On envoie le code en sortie LZW correspondant à B (2).

– On reprend alors au dernier caractère pris en compte (ici A). Le caractère suivant est concaténé avec
A et forme la chaine AA (elle est dans le dictionnaire). Le caractère suivant est concaténé avec la
chaine précédente et forme la chaine AAB (elle est dans le dictionnaire). Le caractère suivant est
concaténé et forme la chaine AABB (elle n'est dans le dictionnaire).

→ On l’ajoute donc au dictionnaire LZW en lui affectant une nouvelle entrée à l’adresse 260.
→ On envoie le code en sortie LZW correspondant à AAB (258).

– On reprend alors au dernier caractère pris en compte (ici B). Le caractère suivant est concaténé avec
B et forme la chaine BB (elle n'est pas dans le dictionnaire).

→ On l’ajoute donc au dictionnaire LZW en lui affectant une nouvelle entrée à l’adresse 261.
→ On envoie le code en sortie LZW correspondant à B (2).

3
Master RRM– USTHB, Pr. M. BOUZID Exercices - Chapitre 2 : Codage sans perte d'information

– On reprend alors au dernier caractère pris en compte (ici B). On lit le dernier caractère et on le
concatène avec B, formant ainsi la chaine BB (elle est dans le dictionnaire). On envoie la valeur
correspondante à BB (261).

– FIN

Ainsi, les nouvelles entrées au dictionnaire sont :

… 256 257 258 259 260 261

… 9 AA AAB BA AABB BB

Au final, le flux compressé de sortie pour le message AAABAABBBB sera :

Code sortie LZW : 1 257 2 258 2 261

(c'est une suite d'adresse contenue dans le fichier compressé).

------------***************------------
Méthode 2 :
- Codage LZW sous forme de tableau :

Dictionnaire LZW:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 ……. 256
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z espace ……. 9

Message à compresser : AAABAABBBB

Le tableau suivant résume les étapes de déroulement de l’algorithme LZW appliqué au codage
du message, où tampon est une sorte de « buffer » dans le quel on place les caractères en attente
de codage, (EOF : fin du fichier message à comprimer).

Chaîne Ajout au dictionnaire LZW

Tampon Caractère concaténée Code LZW de « U »
Etape
Chaîne « T » actuel U = [T + C] en sortie de Chaînes Nouvelles
N° :
Lu « C » Appartient au «T» ajoutées adresses
dictionnaire ?
0 / A [A] : Oui / / /
1 A A [AA] : Non 1 AA 257
2 A A [AA] : Oui / / /
3 AA B [AAB] : Non 257 AAB 258
4 B A [BA] : Non 2 BA 259
5 A A [AA] : Oui / / /
6 AA B [AAB] : Oui / / /
7 AAB B [AABB] : Non 258 AABB 260
8 B B [BB] : Non 2 BB 261
9 B B [BB] : Oui / / /
10 BB EOF / 261 / /

4
Master RRM– USTHB, Pr. M. BOUZID Exercices - Chapitre 2 : Codage sans perte d'information

Exercice 8 :

- Décodage LZW de la séquence codée : 1 257 2 258 2 261

Application de l’algorithme de Décodage LZW :

– Etape initiale: Lire le premier code x (x = 1). Balayer le dictionnaire pour trouver élément à
l'indice x. Envoyez en sortie : élément = A. Mettre Mot = élément = A.

– Début itération :

- Lire prochaine code (x = 257)

Balayer le dictionnaire et vérifier qu'il n ya pas encore d'entrée pour l'indice x = 257.
élément = mot + 1er caractère du mot. D’où: élément = AA
Envoyez en sortie : élément = AA.
Ajouter mot + 1er caractère de élément au dictionnaire : AA (257).
Mettre mot = élément = AA.

- Lire prochaine code (x = 2). Envoyez en sortie : élément = B.

- Ajouter mot + 1er caractère de élément au dictionnaire : AAB (258).
- Mettre mot = élément = B.

- Lire prochaine code (x = 258). Envoyez en sortie : élément = AAB.

- Ajouter mot + 1er caractère de élément au dictionnaire : BA (259).
- Mettre mot = élément = AAB.

- Lire prochaine code (x = 2). Envoyez en sortie : élément = B .

- Ajouter mot + 1er caractère de élément au dictionnaire : AABB (260).
- Mettre mot = élément = B.

- Lire prochaine code (x = 261)

Balayer le dictionnaire et trouver qu'il n ya pas encore d'entrée pour l'index x = 261.
élément = mot + 1er caractère du mot. D’où: élément = BB
Envoyez en sortie : élément = BB .
Ajouter mot + 1er caractère de élément au dictionnaire : BB (261).
Mettre mot = élément = BB.

- Lire prochaine code : Non (EOF : fin du fichier compressé)

- Message décodé est la concaténation des éléments envoyés en sortie: AAABAABBBB

- Ainsi, le décodage LZW est correct.

------------------------------- ************************* -------------------------------

Méthode 2 :
- Décodage LZW sous forme de tableau :

Dictionnaire initial :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 ……. 256
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z espace ……. 9
5
Master RRM– USTHB, Pr. M. BOUZID Exercices - Chapitre 2 : Codage sans perte d'information

Séquence codée : 1 257 2 258 2 261

Le décodage LZW peut être résumé dans le tableau suivant:

Ajout au dictionnaire
Etape Code lu Mot- décodé Mot décodé
N° : « Précédent » « Sortie » Chaîne Nouvelle
ajoutée adresse
0 1 / A / /
1 257 A AA AA 257
2 2 AA B AAB 258
3 258 B AAB BA 259
4 2 AAB B AABB 260
5 261 B BB BB 261

- Message décodé en sortie: AAABAABBBB

- Ainsi, le décodage LZW est correct.

Exercices- Master M1 - RRM : Codage et Compression

Faculté d'Electronique et d'Informatique, Université USTHB, Alger
-  Diffusion autorisée à usage strictement pédagogique -
Auteur : Pr. M. BOUZID