Codage de Huffman

Un texte se code naïvement à longueur fixe : $27$ symboles, lettres et espace, exigent $5$ bits par caractère. Or les caractères n'ont pas la même fréquence, le « e » écrase le « w », et coder court les fréquents, long les rares doit réduire la longueur moyenne. Le codage de Huffman (1952) construit le code à longueur variable optimal. Ce projet le met en œuvre et mesure exactement ce qu'il fait gagner.

1. Lien avec le cours

Le projet mobilise le chapitre 1 : la loi de masse empirique d'une source de caractères, et surtout l'espérance d'une fonction d'une variable aléatoire discrète, car la longueur moyenne d'un code est

$$E(L)=\sum _k{p}_k{\ell }_k,$$

où

• $p_k$ est la probabilité du symbole $k$,
• ${\ell }_k$ est la longueur en bits de son mot de code.

2. Structure du code

Le modèle est la source de caractères, une classe à l'API du projet sur les lois usuelles ; la longueur moyenne, le critère du projet, est une fonction séparée.

class Source:
    """Discrete source over an alphabet (usual-laws project API)."""

    def __init__(self, symbols, probs):
        ...

    def pmf(self, k):
        ...

    def rvs(self, size, rng):
        ...


def average_length(probs, lengths):
    """Expected code length E(L) = sum_k p_k * l_k."""
    ...

Tests imposés. Le test aller-retour, decode(encode(text)) == text sur un texte entier, la propriété qui fait un code utilisable ; et la longueur moyenne de l'exemple à $5$ symboles, confrontée au calcul à la main.

3. Travail demandé

1. La source. Estimer la PMF empirique des caractères d'un long texte français (texte fourni ou de votre choix, lettres non accentuées et espace). Tracer le diagramme en bâtons trié : la loi est-elle proche de l'uniforme ?
2. L'algorithme. Implémenter le codage de Huffman : tant qu'il reste plus d'un nœud, fusionner les deux nœuds de plus faibles probabilités en un nœud parent portant leur somme ; les mots de code se lisent sur les chemins de l'arbre. Vérifier sur un exemple à $5$ symboles calculable à la main.
3. Le gain. Calculer $E(L)$ pour votre code et le comparer aux $5$ bits du code fixe. Quel taux de compression ? Vérifier qu'aucun mot de code n'est le préfixe d'un autre, la propriété qui rend le décodage possible.
4. Vérification Monte-Carlo. Tirer $100000$ caractères selon la PMF, les coder, et confronter la longueur moyenne empirique à $E(L)$ : c'est la loi des grands nombres appliquée à un problème de compression.
5. Ouverture. Comparer $E(L)$ à la quantité $H=-\sum _k{p}_k{\log }_2{p}_k$, donnée ici sans théorie. Constater l'encadrement $H\le E(L)<H+1$ : cette borne, l'entropie, est le sujet de la théorie de l'information.

4. Livrables

Le notebook reproductible des modalités communes, avec l'arbre de l'exemple à $5$ symboles dessiné, le tableau $p_k$, ${\ell }_k$ du code final, et la comparaison chiffrée code fixe / Huffman / entropie.