Compresseur move-to-front

On parcourt un texte écrit. De bons exemples se trouvent dans ce corpus.
L'algorithme de compression est le suivant. On tient à jour une liste des mots déjà parcourus. Pour chaque mot du texte, on cherche le mot dans la liste, puis

• s'il est dedans, on le code à l'aide de sa position dans la liste, puis on le déplace en tête de liste;
• sinon, on le code par 0 suivi du mot en clair, et on l'ajoute en fin de liste.

Par exemple, soit le texte suivant :

deux et deux quatre quatre et quatre huit
    

• On code deux par 0deux. La liste est (deux).
• On code et par 0et. La liste est (deux > et).
• On code deux par 1, la liste est inchangée.
• On code quatre par 0quatre. La liste est (deux > et > quatre).
• Le quatre suivant est codé par 3. La liste est (quatre > deux > et).
• Le et est donc codé par 3, la liste est (et > quatre > deux).
• Le quatre suivant est codé par 2, la liste est (quatre > et > deux).
• Finalement le huit est codé par 0huit. La liste est (quatre > et > deux > huit).

Au final, on récupère à la sortie

0deux 0et 1 0quatre 3 3 2 0huit

On remarque que les mots qui reviennent souvent ont un petit indice, puisqu'ils sont souvent mis en tête de liste. Or, le précédent TP portait justement sur des méthodes d'encodage des entiers qui fonctionne bien avec beaucoup de petits nombres.
Une fois que le programme marche avec un encodage simple en ascii, vous appliquerez donc les méthodes vues précédemment, octet par octet et bit par bit.

Il y aura deux exécutables, comp et decomp. Chacun d'eux aura la syntaxe suivante :

comp x input output	
decomp x input output

où x prendra les valeurs

• a pour un codage ascii,
• o pour un codage octet par octet,
• b pour un codage bit par bit.

Il est plus important d'avoir un seul mode bien fait que plusieurs mal faits!