Problème — Huffman de bout en bout : coder, décoder, mesurer

1. Les trois fonctions.

(* Table caractère -> mot de code. Précondition : arbre non vide.
   Complexité : Theta(taille de l'arbre), soit Theta(k). *)
let table arbre =
  let t = Hashtbl.create 97 in
  let rec parcours a prefixe = match a with
    | Feuille (c, _) -> Hashtbl.replace t c (if prefixe = "" then "0" else prefixe)
    | Interne (g, d, _) -> parcours g (prefixe ^ "0"); parcours d (prefixe ^ "1")
  in parcours arbre ""; t

(* Texte -> suite de bits. Précondition : tout caractère de s est dans t.
   Complexité : Theta(longueur du résultat). *)
let coder s t =
  let b = Buffer.create (String.length s * 3) in
  String.iter (fun c -> Buffer.add_string b (Hashtbl.find t c)) s;
  Buffer.contents b

(* Suite de bits -> texte. Précondition : bits a été produit par coder avec
   le MÊME arbre. Complexité : Theta(nombre de bits). *)
let decoder bits arbre =
  let b = Buffer.create 256 in
  let n = String.length bits in
  let rec aux i a = match a with
    | Feuille (c, _) -> Buffer.add_char b c; if i < n then aux i arbre
    | Interne (g, d, _) ->
        if i < n then aux (i + 1) (if bits.[i] = '0' then g else d)
  in
  if n > 0 then aux 0 arbre;
  Buffer.contents b

Le décodeur ne consulte aucune table : il descend dans l'arbre, un bit par arête, et repart de la racine dès qu'il touche une feuille. Terminaison : variant $n-i$, qui décroît à chaque descente ; le cas Feuille ne consomme pas de bit mais ne peut pas se répéter, puisqu'il relance à la racine, qui est interne dès que $k\ge 2$.