Probleme – \textsc{lzw} complet, et son test

1. Le compresseur.

(* Compresse s. Les codes 1..|alphabet| sont les caracteres seuls.
   Precondition : tout caractere de s figure dans alphabet.
   Complexite : Theta(|s|) appels a la table de hachage. *)
let compresser alphabet s =
  let dico = Hashtbl.create 512 in
  String.iteri (fun i c -> Hashtbl.replace dico (String.make 1 c) (i + 1)) alphabet;
  let suivant = ref (String.length alphabet + 1) in
  let sortie = ref [] and w = ref "" in
  (* INVARIANT : w est le plus long prefixe du reste deja present au dictionnaire. *)
  String.iter (fun c ->
    let wc = !w ^ String.make 1 c in
    if Hashtbl.mem dico wc then w := wc          (* on peut allonger *)
    else begin
      sortie := Hashtbl.find dico !w :: !sortie; (* on emet le PLUS LONG connu *)
      Hashtbl.add dico wc !suivant; incr suivant;(* et on apprend wc *)
      w := String.make 1 c
    end) s;
  if !w <> "" then sortie := Hashtbl.find dico !w :: !sortie;
  List.rev !sortie

2. Le décompresseur.

(* Decompresse une liste de codes produite par compresser avec le MEME alphabet.
   Complexite : Theta(taille du texte reconstruit). *)
let decompresser alphabet codes =
  let dico = Hashtbl.create 512 in
  String.iteri (fun i c -> Hashtbl.replace dico (i + 1) (String.make 1 c)) alphabet;
  let suivant = ref (String.length alphabet + 1) in
  let b = Buffer.create 256 in
  let precedente = ref "" in
  List.iter (fun code ->
    let sequence =
      match Hashtbl.find_opt dico code with
      | Some s -> s
      | None -> !precedente ^ String.make 1 !precedente.[0]  (* LE CAS QUI PIEGE *)
    in
    Buffer.add_string b sequence;
    if !precedente <> "" then begin
      Hashtbl.add dico !suivant (!precedente ^ String.make 1 sequence.[0]);
      incr suivant                          (* on apprend avec UN TOUR DE RETARD *)
    end;
    precedente := sequence) codes;
  Buffer.contents b

3. Pourquoi le code inconnu est toujours le suivant.

Notons $D_c$ le dictionnaire du compresseur et $D_d$ celui du décodeur. Le compresseur, quand il émet le code de $w$, vient d'ajouter $wc$ ; le décodeur, lui, ne peut ajouter cette entrée qu'après avoir reçu le code suivant, puisqu'il ignore $c$ tant qu'il ne l'a pas lu. Le décodeur a donc exactement une entrée de retard : au moment de traiter le $i$-ième code, $D_d$ contient les $i-1$ premières entrées apprises, et $D_c$ en contient $i$.

Si le code reçu n'est pas dans $D_d$, c'est donc nécessairement la dernière entrée créée par le compresseur, celle de numéro $|D_d|+1$ — jamais une autre. Or cette entrée vaut $S+\mathtt{premier}(\text{seˊquence courante})$ où $S$ est la séquence précédente. Comme le code reçu est cette entrée, la séquence courante est elle-même $S+\mathtt{premier}(S)$, ce que le décodeur sait reconstituer sans rien deviner.

Ce n'est donc pas une convention, c'est une conséquence. Et cela vaut preuve de correction : le décodeur reconstitue exactement le texte, ce que la question suivante confirme par la mesure.

4. Le test. Il tient en une ligne, et c'est la bonne :

(* PROPRIETE : pour tout texte t sur l'alphabet, decompresser (compresser t) = t. *)
let tester () =
  Random.init 42;
  let ok = ref true and pieges = ref 0 in
  for _ = 1 to 5000 do
    let n = 1 + Random.int 40 in
    let t = String.init n (fun _ -> if Random.bool () then 'A' else 'B') in
    let c = compresser "AB" t in
    if decompresser "AB" c <> t then ok := false;
    (* on compte les textes qui declenchent le cas particulier *)
    (try ignore (decompresser_sans_cas_particulier "AB" c)
     with Code_inconnu _ -> incr pieges)
  done;
  Printf.printf "aller-retour exact : %b ; cas particulier declenche %d fois sur 5000\n"
    !ok !pieges

Mesure :

aller-retour exact : true ; cas particulier declenche 3784 fois sur 5000 (75,7 %)

Et sur les cas nommés :

ABABABA   -> [1; 2; 3; 5]     decode ABABABA   ; sans cas particulier : ECHEC sur 5
AAA       -> [1; 3]           decode AAA       ; sans cas particulier : ECHEC sur 3
ABAB      -> [1; 2; 3]        decode ABAB      ; sans cas particulier : OK
TOBEORNOTTOBEORTOBEORNOT -> [6;4;1;2;4;5;3;4;6;7;9;11;16;10;12;14]  ; OK

Trois enseignements.

• Le test à écrire n'est pas « le compresseur rend telle liste » mais la propriété d'aller-retour. Elle ne dépend d'aucun choix d'implémentation, elle se vérifie sur des milliers d'entrées tirées au hasard, et elle est la définition même de « sans perte ».
• Sur $5000$ mots aléatoires, la version sans cas particulier échoue trois fois sur quatre. Il n'était pas nécessaire de chercher un cas rare : il fallait seulement tester autre chose que ABAB.
• Le cas TOBEORNOTTOBEORTOBEORNOT — $24$ caractères, $16$ codes — passe aussi sans le cas particulier. C'est exactement pourquoi un unique exemple bien choisi ne remplace pas un test aléatoire : le contre-exemple ne se trouve pas en écrivant, il se trouve en tirant.