Probleme – 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$.

2. Le décodage est non ambigu. Supposons deux textes $u\ne w$ de même codage $B$. Soit $j$ le premier rang où ils diffèrent : leurs préfixes communs ont même codage, donc le codage de $u_j$ et celui de $w_j$ commencent au même bit. L'un est alors préfixe de l'autre — ils sont tous deux préfixes de la même suite de bits restante. Or le code est préfixe : deux mots de code distincts ne peuvent pas être l'un préfixe de l'autre. Donc $u_j=w_j$, contradiction.

Complexités : codage en $\Theta (N)$ où $N$ est le nombre de bits produits ; décodage en $\Theta (N)$ également, chaque bit provoquant exactement une descente d'un niveau.

3. La mesure, sur un extrait du présent chapitre — $361$ caractères, $26$ symboles distincts. Le décodage a été comparé caractère à caractère à l'original : identique. La propriété du préfixe a été vérifiée sur les $26$ codes.

Soit $18,6\%$ de gain sur la longueur fixe et $49,1\%$ sur l'ascii. Le code le plus court fait $3$ bits (l'espace, $61$ occurrences ; puis le e, $48$ occurrences), le plus long en fait $8$.

Huffman est à $0,8\%$ de l'entropie. On démontre plus généralement que sa longueur moyenne $\bar{\ell }$ vérifie $H\le \bar{\ell }<H+1$ : il ne peut jamais perdre plus d'un bit par caractère, et il perd d'autant moins que les fréquences sont proches de puissances de $\frac{1}{2}$.

4. Le prix de la table. Le décodeur a besoin de l'arbre : il faut donc le transmettre. Un stockage naïf — le caractère sur $8$ bits, la longueur du code sur $4$ bits, puis le code — coûte environ $451$ bits ici. Le fichier complet fait donc $1470+451=1921$ bits, contre $2888$ : le gain réel tombe de $49\%$ à $33\%$.

Et le seuil de rentabilité. Le coût de la table ne dépend que de $k$, celui du texte est proportionnel à sa longueur $n$. Le gain net vaut donc $n(8-\bar{\ell })-T$ : il est négatif tant que $n<T/(8-\bar{\ell })$, soit ici environ $115$ caractères. Compresser un texte court coûte plus cher que de ne rien faire, et c'est pourquoi les formats réels emploient des tables convenues d'avance, ou adaptatives — le chapitre chap:textes y revient.