Le décodeur qui perd la dernière lettre

Elle rend abb. Il manque le a final. Mesures :

bits   attendu   rendu par la fonction du chapitre
0      a         ""
01     ab        "a"
011    abb       "ab"
0110   abba      "abb"
1010   baba      "bab"

Le diagnostic. La fonction filtre d'abord sur la liste de bits et ensuite sur le nœud :

let rec descendre n = function
  | [] -> ()                                     (* <-- ON SORT SANS REGARDER n *)
  | b :: reste -> match n with
    | Feuille (c, _) -> Buffer.add_char sortie c; descendre a (b :: reste)
    | Interne (g, d, _) -> descendre (if b = 0 then g else d) reste

Quand le dernier bit a été consommé, on est sur une feuille — le dernier caractère est complet — mais la première branche a déjà rendu (). L'ordre des deux filtrages est la faute : c'est l'état de l'arbre qui décide s'il y a un caractère à émettre, pas l'état du flux.

Une seconde faute, cachée derrière. Si l'arbre se réduit à une feuille — un texte n'utilisant qu'un seul symbole — alors descendre a (b :: reste) ne consomme aucun bit et se rappelle à l'identique : la fonction boucle indéfiniment. La ligne finale du chapitre, match a with Feuille (c, _) -> ..., était destinée à ce cas, mais elle est placée après l'appel qui boucle : elle n'est jamais atteinte.

La correction filtre sur le nœud d'abord, et traite l'arbre à une feuille à part :

(* Decode la suite de bits selon l'arbre de Huffman a.
   Precondition : bits est le codage d'un texte par CE MEME arbre.
   Complexite : Theta(nombre de bits), chaque bit descendant d'un cran. *)
let decoder a bits =
  let sortie = Buffer.create 256 in
  (match a with
   | Feuille (c, _) ->
       (* arbre degenere : un seul symbole, un bit par symbole *)
       List.iter (fun _ -> Buffer.add_char sortie c) bits
   | Interne _ ->
       let rec descendre n bits =
         match n with
         | Feuille (c, _) ->                    (* ON REGARDE LE NOEUD D'ABORD *)
             Buffer.add_char sortie c;
             (match bits with [] -> () | _ -> descendre a bits)
         | Interne (g, d, _) ->
             (match bits with
              | [] -> ()                        (* flux epuise en plein caractere *)
              | b :: reste -> descendre (if b = 0 then g else d) reste)
       in descendre a bits);
  Buffer.contents sortie

Vérification : sur l'arbre de abracadabra et son codage de $23$ bits, la fonction corrigée rend "abracadabra" ; la fonction du chapitre rend "abracadabr". Sur l'arbre à une feuille et les bits 000, la corrigée rend "zzz" ; celle du chapitre ne rend rien, elle tourne.

Terminaison de la version corrigée. Le variant est le nombre de bits restants, sauf au passage par une feuille, qui n'en consomme aucun. On prend donc pour variant le couple (nombre de bits restants, $0$ si le nœud est interne et $1$ s'il est une feuille), ordonné lexicographiquement : un pas sur une feuille fait passer de $(k,1)$ à $(k,0)$, un pas sur un nœud interne fait passer de $(k,0)$ à $(k-1,\cdot )$. Le couple décroît strictement, et il est bien fondé (chapitre chap:induction).

La leçon de test. Aucun des trois cas fautifs n'est visible sur un décodage partiel ; les trois se voient au premier test qui vérifie decoder a (encoder a t) = t. Un codec se teste par aller-retour, jamais par inspection de sa sortie.