Le plus petit texte qui piège le décodeur \textsc{lzw}

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 18 — Algorithmique des textes

Énoncé

Le chapitre annonce que le décodeur lzw peut recevoir un code qu'il ne connaît pas encore, et l'illustre sur ABABABA. Quel est le plus court texte qui déclenche ce cas ? Le vérifier.

Corrigé

C'est AAA, trois lettres.

Compression, avec le dictionnaire initial $A \to 1$ , $B \to 2$ :


lit A     emet 1   ajoute AA -> 3   reste AA
lit AA    emet 3   ajoute ---       reste (vide)
codes emis : [1 ; 3]

Décompression : le décodeur reçoit $1$ , émet A. Il reçoit $3$ — et son dictionnaire ne contient que $1$ et $2$ , car il n'ajoute une entrée qu'après avoir reçu le code suivant. Il applique la règle : $s e ˊ quence = pr e ˊ c e ˊ dente + pr e ˊ c e ˊ dente [0] = A + A = AA$ . Il émet AA, ajoute $AA \to 3$ , et le texte AAA est reconstruit.

Recherche exhaustive sur les $2 + 4 + 8 = 14$ mots binaires de longueur $\leq 3$ : aucun mot de longueur $1$ ou $2$ ne déclenche le cas, et exactement deux mots de longueur $3$ le déclenchent — AAA et BBB. Le cas se produit donc dès la troisième lettre.

Pourquoi c'est exactement là. Le décodeur reçoit un code inconnu si et seulement si le compresseur vient de créer ce code au tour précédent, ce qui exige que la séquence émise commence par la séquence précédente : elle est de la forme $S + premier (S)$ . Le plus court $S$ est une lettre, et l'on a besoin d'une troisième lettre pour que le compresseur ait eu le temps d'apprendre $S S$ . Trois lettres, et pas moins.

Ce que ça change. Le cas n'est pas rare, c'est le cas ordinaire. Mesure sur des mots binaires aléatoires, décodés par une version sans le cas particulier :


longueur  5 : le decodeur naif echoue sur 50,0 % des mots
longueur 10 : ... 70,7 %
longueur 20 : ... 85,5 %
longueur 40 : ... 92,7 %
longueur 80 : ... 96,4 %

Sur un fichier réel, le décodeur sans le cas particulier échoue pratiquement toujours. Le chapitre a raison de le signaler comme « celui qui fait échouer les mises en œuvre naïves » — mais l'exercice montre que ce n'est pas un cas limite : c'est le régime normal, et un test de trois lettres suffit à l'attraper.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.