Partie 1

Les fichiers sont ici

Q1. Ecrire l'algorithme de compression LZ78. On écrira en sortie des couples (position, lettre).

Q2. Ecrire une fonction taille qui, étant donné un entier x, dit de combien de bits on a besoin pour écrire x en binaire. Pour x = 3, il faut donc renvoyer 2, pour x = 240 il faut renvoyer 8. C'est donc le nombre de fois où on peut diviser x (entier) par 2 jusqu'à atteindre 0.

Q3. Modifier votre implémentation de lz78 pour qu'elle écrive le résultat sous forme binaire. Le caractère sera donc codé (naturellement) sur 8 bits, mais la position sera codée sur un nombre de bits dépendant de la taille du dictionnaire

On va maintenant chercher à écrire un decompresseur lz78.

Q4. Ecrire un programme qui, à partir du fichier compressé, retrouve la liste de couples (position, lettre)

Dans le compresseur, nous avions codé le dictionnaire par un tableau T. Si on note dict[i] le mot en position i du dictionnaire, T[i][c] est la position où se trouve le mot dict[i]c (le mot en position i du dictionnaire auquel on a ajouté la lettre c)

Dans le décompresseur, le dictionnaire va être codé par deux tableaux, un tableau P et un tableau C, qui correspondent au tableau "inverse" du tableau T: si T[i][c] = j, alors C[j] = c et P[j] = i.

L'idée est que C[j] est la dernière lettre du mot en position j du dictionnaire, et P[j] est la position du dictionnaire où se trouve le mot dict[j] privé de sa dernière lettre.

Autrement dit, le mot en position j du dictionnaire est le mot C[P[P[P..[j]]]]C[P[P[...[j]]]]...C[P[P[j]]]C[P[j]]C[j]

Dans le décompresseur, on fonctionne uniquement avec les tableaux C et P, et rien d'autre.

Q5. Ecrire un décompresseur lz78. Tester le sur test.lz78