Huffman sur un alphabet d'un seul caractère

Avec un seul caractère, la boucle while taille f > 1 ne s'exécute pas : l'arbre rendu est une feuille isolée. Le parcours racine-feuille est alors vide, et le code du caractère est le mot vide. Mesuré : sur un texte de $100$ caractères identiques, le codage produit $0$ bit.

Le texte codé est donc vide, et il est indécodable : rien ne distingue le codage de $100$ caractères de celui de $3$ ou de $10^6$. Le décodeur boucle sur une entrée vide, ou rend une chaîne vide. Et pourtant, aucune erreur n'est levée, et le taux de compression paraît infini.

Où est la faute, exactement. Le théorème d'optimalité de Huffman est vrai : le code de longueur $0$ minimise bien ${\sum }_c{n}_c{\ell }_c$. Le défaut n'est pas dans l'algorithme, il est dans la spécification : on a oublié d'exiger que le code soit décodable, c'est-à-dire que la fonction de codage soit injective sur les textes. Un code où tous les mots sont vides est préfixe au sens formel — aucun n'est préfixe strict d'un autre — mais il ne code rien.

(* Table des codes. Précondition : l'arbre a au moins UNE feuille.
   Postcondition : tout code a une longueur >= 1, y compris pour k = 1. *)
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

Avec ce garde, le caractère unique reçoit le code 0, et le texte de $100$ caractères occupe $100$ bits — ce qui est bien la réponse correcte : un alphabet d'un symbole ne transporte aucune information par symbole, mais la longueur du message en transporte.

La règle qui l'aurait évité. Le chapitre chap:discipline le dit : on teste aux frontières. Pour un algorithme sur $k$ symboles, les frontières sont $k=1$ et $k=2$. Le cas $k=1$ n'est pas une bizarrerie théorique : il survient dès qu'on compresse par blocs et qu'un bloc est uniforme — une page blanche dans une image, un silence dans un son.