TD 4, Codage de Lempel-Ziv-Welsh
Introduction à la théorie de l'information
26 janvier 2023 |
Grandes lignes de l'algorithme de codage :
-
on lit le texte jusqu'à trouver un mot m suivi d'une lettre
a tels que m soit dans le dictionnaire, mais pas m||a,
- on imprime i où i est l'indice de m dans le dictionnaire,
- on ajoute m||a dans le dictionnaire, avec son indice,
- on continue.
Il faudra avoir préalablement placé dans le dictionnaire tous les mots
d'une lettre.
Grandes lignes de l'algorithme de décodage :
-
on lit un indice i,
- on imprime le mot m d'indice i
- on ajoute à la fin du dictionnaire le mot m||a où a est la
première lettre suivante.
Comme pour le codage, il faudra avoir préalablement placé dans le
dictionnaire tous les mots d'une lettre.
Pour représenter les données nous aurons besoin :
Voici ce que vous devez obtenir avec
le fichier hamlet.txt
% wc -c hamlet.txt
8573 hamlet.txt
% java Coder hamlet.txt > hamlet.txt.lzw
% wc -c hamlet.txt.lzw
35580 hamlet.txt.lzw
% java Decoder hamlet.txt.lzw >! hamlet.txt.dec
% diff hamlet.txt hamlet.txt.dec
%
Ce document a été traduit de LATEX par HEVEA