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 :

pour le codage d'un arbre/dictionnaire, l'alphabet est l'ensemble des octets. Chaque noeud est susceptible d'avoir 256 fils
```
class Arbre {
    int indice;    // indice du mot représenté par ce noeud
    Arbre [] fils; // tableau de 256 fils
}
```
On trouvera un patron pour cette classe (ainsi que quelques méthodes élémentaires) dans la classe Arbre.java. La documentation javadoc associée se trouve dans Arbre.html. Pour trouver le mot m tel que m est dans le dictionaire mais pas m||a, on descend dans l'arbre en suivant les lettres lues, jusqu'à ce qu'on arrive sur une feuille.
pour le décodage on s'aidera de la classe Dictionnaire qui stocke le dictionnaire utilisé pour le décodage comme un tableau de String, dans lequel on empilera les mots du dictionnaire. La documentation correspondante se trouve ici

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 L^AT_EX par H^EV^EA