Compression des données

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

distinguer compression sans perte et compression avec pertes, et dire dans quelles situations chacune est légitime;
démontrer par comptage qu'aucun compresseur sans perte ne raccourcit tous les fichiers, et en tirer les bonnes conclusions pratiques;
reconnaître un code préfixe, le lire sur un arbre binaire, et exhiber l'ambiguïté d'un code qui ne l'est pas;
énoncer et démontrer l'inégalité de Kraft dans les deux sens, et construire un code préfixe à partir de longueurs admissibles;
démontrer le théorème du codage de source, construire un code de Huffman complet et mesurer l'écart qui le sépare de l'entropie;
expliquer le principe du codage arithmétique et celui de Lempel–Ziv, et décrire honnêtement ce que font JPEG et MP3.

Ce que comprimer veut dire

Le chapitre 6 a établi qu'une source d'information possède une mesure intrinsèque, son entropie $H (X)$ , exprimée en bits par symbole, et que cette quantité est la même quel que soit l'alphabet dans lequel on écrit les symboles. Nous y avons calculé l'entropie du message ABRACADABRA, qui vaut $H = 2, 0404$ bits par symbole. Ce chapitre répond à la question que le précédent laissait ouverte: cette borne est-elle atteignable, et par quel algorithme?

Comprimer, c'est remplacer une représentation d'une donnée par une autre, plus courte. Rien de plus — mais tout est dans le mot «remplacer», car il faut pouvoir revenir en arrière, et c'est le degré de fidélité de ce retour qui sépare les deux grandes familles.

La frontière n'est pas une nuance technique, c'est une frontière d'usage. Un exécutable, une archive comptable, un jeu de données de mesures, un fichier source: la moindre altération d'un bit les rend faux ou inutilisables, et seule la compression sans perte est acceptable. Une photographie destinée à être regardée, un enregistrement destiné à être écouté: le destinataire est un œil ou une oreille, et l'on peut jeter tout ce que cet œil ou cette oreille ne percevra pas. Le gain est alors d'un tout autre ordre de grandeur — mais il est définitif. Un fichier une fois dégradé ne redevient jamais net.

Aucun compresseur ne comprime tout

La promesse commerciale d'un logiciel «qui réduit tous vos fichiers de moitié» n'est pas seulement exagérée: elle est mathématiquement impossible, et la démonstration tient en quatre lignes de dénombrement. C'est le résultat le plus important du chapitre pour l'hygiène intellectuelle, car il fixe d'emblée ce qu'on a le droit d'espérer.

Démonstration. Il y a exactement $2^{n}$ suites de longueur $n$ . Le nombre de suites de longueur au plus $n - k$ est

j = 0 \sum n - k 2^{j} = 2^{n - k + 1} - 1. (7.2)

Comme $c$ est injective, deux suites distinctes de longueur $n$ ont des images distinctes; le nombre de suites de longueur $n$ dont l'image est de longueur au plus $n - k$ est donc majoré par le nombre de valeurs disponibles, soit $2^{n - k + 1} - 1$ . La proportion cherchée est au plus $(2^{n - k + 1} - 1) / 2^{n} < 2^{1 - k}$ .

Pour $k = 1$ la majoration donne $2^{n} - 1 < 2^{n}$ : strictement moins de $2^{n}$ suites de longueur $n$ sont raccourcies, donc au moins une ne l'est pas. C'est exactement le principe des tiroirs: on ne range pas $2^{n}$ objets distincts dans tiroirs sans en mettre deux ensemble.

Lisons la conclusion quantitative. Moins d'une suite sur $2^{9} = 512$ peut être raccourcie de $10$ bits; moins d'une sur $2^{19}$ , soit environ une sur $524288$ , peut l'être de $20$ bits. Une compression franche est donc, statistiquement, un événement rare — sur l'ensemble de toutes les suites de bits.

Et pourtant les compresseurs fonctionnent. La contradiction n'est qu'apparente: les fichiers que les gens possèdent ne sont pas des suites tirées au hasard. Un texte français, une image de paysage, une table de mesures, un programme: tous sont extraordinairement redondants, et ils occupent une partie minuscule de l'espace des suites possibles. Un compresseur est un pari sur cette structure. Il gagne sur les fichiers réels et, nécessairement, il perd sur d'autres — sur le bruit, sur les données déjà comprimées, sur les données chiffrées.

Zipper deux fois ne comprime pas deux fois

C'est la croyance la plus tenace du domaine. Un fichier déjà comprimé n'a plus de redondance à offrir: le second passage ne trouve rien à exploiter et ne peut plus qu'ajouter son propre en-tête. Le fichier grossit.

Vérifions-le plutôt que de l'affirmer. En Python, sur un texte français artificiellement répétitif de $944$ octets:

import zlib
t = ("La compression sans perte exploite la redondance du texte. ") * 16
b = t.encode()
print(len(b), len(zlib.compress(b, 9)), len(zlib.compress(zlib.compress(b, 9), 9

Question 7.1

Un ingénieur affirme avoir écrit un compresseur sans perte qui raccourcit d'au moins un bit toute suite de $1000$ bits. Que peut-on en conclure?

Codes à longueur variable

Le problème du décodage

La première idée pour comprimer un texte est d'abandonner la longueur fixe. Avec $q$ symboles, un code de longueur fixe dépense $⌈ lo g_{2} q ⌉$ bits par symbole, quelle que soit la fréquence de chacun. Pour ABRACADABRA, $q = 5$ et $⌈ lo g_{2} 5 ⌉ = 3$ : le message coûte bits. Or le A apparaît cinq fois sur onze et le D une seule: il est absurde de les payer le même prix.

L'absence de séparateur est le cœur du problème. On pourrait imaginer réserver un motif pour marquer la fin d'un mot, mais ce motif coûterait des bits à chaque symbole, exactement ce qu'on cherche à économiser. Un code doit donc se décoder par sa seule structure.

Être non singulier ne suffit pas. Considérons le code $C (A) = 0$ , $C (B) = 01$ , $C (C) = 11$ , $C (D) = 110$ : les quatre mots sont bien distincts deux à deux. Pourtant la suite $0110$ se lit de deux façons.

Codes préfixes et arbres binaires

Un code préfixe est déchiffrable, et pour une raison très concrète: on le décode de gauche à droite, un bit à la fois, en s'arrêtant dès que les bits accumulés forment un mot du code — puisqu'aucun mot n'en prolonge un autre, ce mot est nécessairement le bon. Le décodage ne revient jamais en arrière et ne regarde jamais au-delà du mot courant; c'est le sens de l'adjectif «instantané».

La bonne façon de voir un code préfixe est l'arbre binaire. Construisons l'arbre dont la racine est la suite vide, où descendre à gauche écrit un $0$ et descendre à droite un $1$ : chaque nœud de profondeur $ℓ$ correspond alors exactement à une suite de $ℓ$ bits. Un code est un choix de nœuds; il est préfixe si et seulement si aucun nœud choisi n'est ancêtre d'un autre, c'est-à-dire si les mots du code sont tous des feuilles de l'arbre qu'ils engendrent.

Question 7.2

Parmi les quatre codes suivants sur un alphabet de quatre symboles, lequel est préfixe?

L'inégalité de Kraft

Quelles suites de longueurs $ℓ_{1}, \dots, ℓ_{m}$ peut-on espérer? Il y a manifestement une contrainte: on ne peut pas donner un mot court à tout le monde, car un mot court «occupe» une grande partie de l'arbre. L'inégalité de Kraft (1949) quantifie exactement ce budget, et c'est le théorème structurel du chapitre.

Démonstration.

Sens direct. Posons $L = max_{i} ℓ_{i}$ et plaçons-nous dans l'arbre binaire complet de profondeur $L$ , qui possède $2^{L}$ feuilles. Chaque mot $c_{i}$ , situé à la profondeur , est l'ancêtre d'exactement de ces feuilles: ce sont les suites de bits qui commencent par . Deux mots distincts et ne peuvent avoir de descendant commun à la profondeur , car une telle feuille commencerait à la fois par et par , ce qui forcerait l'un des deux à être préfixe de l'autre — interdit. Les ensembles de descendants sont donc deux à deux disjoints, et tous contenus dans l'ensemble des feuilles:

i = 1 \sum m 2^{L - ℓ_{i}} \leq 2^{L} .

En divisant par $2^{L}$ , on obtient (7.3).

Réciproque. Quitte à renuméroter, supposons $ℓ_{1} \leq ℓ_{2} \leq \dots \leq ℓ_{m}$ . Définissons les sommes partielles

w_{1} = 0, w_{i} = j < i \sum 2^{- ℓ_{j}} (i \geq 2) . (7.4)

L'hypothèse (7.3) donne $w_{i} \leq \sum_{j} 2^{- ℓ_{j}} \leq 1$ , et même $w_{i} < 1$ pour tout puisqu'il manque au moins le terme . Chaque est un rationnel dyadique de ; prenons pour mot les de son développement binaire (ce développement est fini et comporte au plus bits, car est un multiple entier de : tous les pour sont inférieurs ou égaux à ).

Montrons que ce code est préfixe. Soient $i < k$ et supposons que $c_{i}$ soit un préfixe de $c_{k}$ . Alors les $ℓ_{i}$ premiers bits de $w_{i}$ et de coïncident, donc . Or, par construction,

w_{k} - w_{i} = j = i \sum k - 1 2^{- ℓ_{j}} \geq 2^{- ℓ_{i}},

puisque la somme contient au moins le terme $j = i$ et que tous les termes sont positifs. Contradiction. Le code est donc préfixe, et ses mots ont bien les longueurs voulues. $□$

Question 7.3

Un code binaire préfixe doit coder six symboles avec les longueurs $2, 2, 3, 3, 4, 4$ . Calculez la somme de Kraft $\sum_{i} 2^{- ℓ_{i}}$ .

Longueur moyenne et théorème du codage de source

La quantité à minimiser

Sur un message de $n$ symboles indépendants de même loi, la loi des grands nombres dit que le nombre total de bits est proche de $n \overset{ˉ}{L}$ : minimiser $\overset{ˉ}{L}$ , c'est minimiser la taille du fichier. La question est donc: jusqu'où peut-on descendre?

La borne inférieure: on ne descend pas sous l'entropie

Démonstration. Notons $K = \sum_{i} 2^{- ℓ_{i}}$ , qui vérifie $K \leq 1$ par l'inégalité de Kraft, et posons $q_{i} = 2^{- ℓ_{i}} / K$ . Les sont positifs et de somme : c'est une loi de probabilité sur le même alphabet. Alors , donc

\overset{ˉ}{L} - H (X) = i \sum p_{i} ℓ_{i} + i \sum p_{i} lo g_{2} p_{i} = i \sum p_{i} lo g_{2} \frac{p _{i}}{q _{i}} - lo g_{2} K . (7.7)

Le second terme est positif ou nul, car $K \leq 1$ entraîne $lo g_{2} K \leq 0$ . Pour le premier, utilisons l'inégalité élémentaire $ln u \leq u - 1$ , valable pour tout $u > 0$ (la fonction est convexe, de dérivée , minimale en où elle vaut ). Avec :

i \sum p_{i} lo g_{2} \frac{q _{i}}{p _{i}} = \frac{1}{ln 2} i \sum p_{i} ln \frac{q _{i}}{p _{i}} \leq \frac{1}{ln 2} i \sum p_{i} (\frac{q _{i}}{p _{i}} - 1) = \frac{1}{ln 2} (i \sum q_{i} - i \sum p_{i}) = 0.

Donc $\sum_{i} p_{i} lo g_{2} (p_{i} / q_{i}) \geq 0$ , et (7.7) donne .

L'égalité exige simultanément $K = 1$ et $q_{i} = p_{i}$ pour tout $i$ (car $ln u = u - 1$ n'a lieu que pour ), c'est-à-dire , soit : les probabilités doivent être exactement des puissances de .

La quantité $\sum_{i} p_{i} lo g_{2} (p_{i} / q_{i})$ qui apparaît ici est la ; nous venons d'établir au passage qu'elle est toujours positive ou nulle, et nulle seulement si . Elle mesure le prix payé quand on code une source de loi avec un code conçu pour la loi — autrement dit, le coût d'un mauvais modèle.

La borne supérieure: un bit, jamais plus

Démonstration. La première inégalité est le théorème 7.3. Pour la seconde, prenons les longueurs de Shannon–Fano

ℓ_{i} = ⌈ - lo g_{2} p_{i} ⌉ . (7.9)

Ces entiers sont admissibles: comme $ℓ_{i} \geq - lo g_{2} p_{i}$ , on a $2^{- ℓ_{i}} \leq 2^{l o g_{2} p_{i}} = p_{i}$ , d'où

i \sum 2^{- ℓ_{i}} \leq i \sum p_{i} = 1.

L'inégalité de Kraft étant vérifiée, le sens réciproque du théorème 7.2 fournit un code préfixe de ces longueurs. Sa longueur moyenne se majore en utilisant $⌈ u ⌉ < u + 1$ :

\overset{ˉ}{L} = i \sum p_{i} ⌈ - lo g_{2} p_{i} ⌉ < i \sum p_{i} (- lo g_{2} p_{i} + 1) = H (X) + 1.

Enfin, le code optimal a par définition une longueur moyenne au plus égale à celle-ci, et au moins égale à $H (X)$ par le théorème 7.3. $□$

Question 7.4

Une source a quatre symboles de probabilités $1/2$ , $1/4$ , $1/8$ , $1/8$ . Que vaut la longueur moyenne du meilleur code préfixe?

Le codage de Huffman

Le théorème 7.4 garantit qu'un bon code existe, mais sa démonstration ne fournit pas le meilleur: les longueurs de Shannon–Fano sont admissibles, pas optimales. L'algorithme de Huffman (1952), trouvé par un étudiant à qui son professeur avait proposé la question comme sujet d'examen, construit un code optimal, et il est d'une simplicité désarmante.

L'algorithme

L'idée tient en une phrase: les deux symboles les moins fréquents doivent être les plus profonds dans l'arbre, donc frères; on peut alors les fusionner en un seul symbole de fréquence cumulée et recommencer sur une source à un symbole de moins.

fonction Huffman(fréquences):
    F ← file de priorité contenant une feuille par symbole,
        chaque feuille ayant pour clé sa fréquence
    tant que F contient au moins deux éléments:
        x ← extraire le minimum de F
        y ← extraire le minimum de F
        z ← nouveau nœud interne de clé (clé de x) + (clé de y)
        fils gauche de z ← x
        fils droit de z ← y
        insérer z dans F
    retourner l'unique élément de F        // la racine de l'arbre

Le code se lit ensuite en parcourant l'arbre depuis la racine: descendre à gauche écrit un $0$ , descendre à droite un $1$ , et le mot d'un symbole est la suite de bits menant à sa feuille. Comme les symboles sont aux feuilles, le code est préfixe par construction.

En Python, une file de priorité s'obtient avec le module heapq; le troisième champ du triplet sert à départager les poids égaux de façon déterministe.

import heapq

def huffman(freq):                       # freq: symbole -> fréquence
    tas = [(f, i, s) for i, (s, f) in enumerate(freq.items())]
    heapq.heapify(tas)                   # file de priorité sur la fréquence
    k = len(tas)
    while len(tas) > 1:
        f1, _, g = heapq.heappop(tas)    # les deux plus petits poids
        f2, _, d = heapq.heappop(tas)
        heapq.heappush(tas, (f1 + f2, k, (g, d)))   # fusion du minimum
        k +=

Avec $m$ symboles, l'algorithme fait $m - 1$ fusions, chacune coûtant $O (lo g m)$ opérations sur le tas: le coût total est $Θ (m lo g m)$ , négligeable devant la lecture du fichier lui-même.

ABRACADABRA, fusion par fusion

Les vingt-trois bits contre les vingt-deux et demi

Comparons maintenant les trois quantités. La version à longueur fixe coûte $33$ bits. Le code de Huffman en coûte $23$ . Et l'entropie calculée au chapitre 6 donne un plancher de $11 \times 2, 0404 = 22, 44$ bits.

Il faut dire les choses franchement: $23$ est strictement supérieur à $22, 44$ , et cet écart n'est pas une imprécision de calcul. Il ne disparaîtra jamais, quel que soit le code préfixe employé, parce que sa cause est structurelle. Les longueurs idéales $- lo g_{2} p_{i}$ valent ici

- lo g_{2} \frac{5}{11} = 1, 1375, - lo g_{2} \frac{2}{11} = 2, 4594, - lo g_{2} \frac{1}{11} = 3, 4594,

et ce ne sont pas des entiers. Un code préfixe ne peut dépenser que des nombres entiers de bits par symbole; il arrondit donc, et l'arrondi coûte. C'est la pénalité de longueur entière, et elle vaut ici $23 - 22, 44 = 0, 56$ bit sur tout le message, soit $0, 0505$ bit par symbole. L'encadrement du théorème 7.4 est bien respecté:

2, 0404 \leq 2, 0909 < 3, 0404.

Un mot, enfin, sur ce que «le» code de Huffman veut dire: l'article défini est trompeur, et à deux niveaux.

D'abord, les motifs binaires ne sont pas uniques. Échanger le fils gauche et le fils droit d'un nœud interne échange un $0$ et un $1$ dans tous les mots de son sous-arbre, sans toucher à aucune longueur. Notre arbre a quatre nœuds internes, donc $2^{4} = 16$ codes le réalisent — par exemple $C (A) = 1$ avec tous les autres mots commençant par $0$ .

Ensuite, et c'est plus surprenant, les longueurs elles-mêmes ne sont pas uniques. Dès que plusieurs nœuds ont le même poids — à la fusion 2, trois nœuds pèsent $2$ — le départage change l'arbre. En énumérant par programme tous les ordres de fusion licites, on trouve exactement trois assignations de longueurs optimales:

A	B	C	D	R	Total
1	3	3	3	3	23 bits
1	2	4	4	3	23 bits
1	3	4	4	2	23 bits

Les trois saturent l'inégalité de Kraft, et les trois coûtent $23$ bits. C'est le total qui est forcé, parce qu'il est optimal; la répartition ne l'est pas, et les motifs binaires encore moins. La première ligne est celle que ce cours retient: c'est la convention de départage du programme ci-dessus — «à poids égal, le nœud entré le premier dans la file sort le premier» — et non une nécessité mathématique. Un décodeur a donc toujours besoin de recevoir la table du code, ou une convention qui permette de la reconstruire.

Huffman est optimal

Démonstration (esquisse). Elle repose sur deux observations, puis une récurrence sur $m$ .

Premier lemme: l'arbre d'un code optimal est complet et trie les longueurs. Si un nœud interne n'avait qu'un fils, on le remplacerait par ce fils, raccourcissant tous les mots du sous-arbre: le code ne serait pas optimal. Et si l'on avait $p_{i} > p_{j}$ avec $ℓ_{i} > ℓ_{j}$ , échanger les deux mots ferait varier la longueur moyenne de

Δ = (p_{i} ℓ_{j} + p_{j} ℓ_{i}) - (p_{i} ℓ_{i} + p_{j} ℓ_{j}) = - (p_{i} - p_{j}) (ℓ_{i} - ℓ_{j}) < 0,

donc l'échange améliorerait strictement le code: c'est l'argument d'échange. Un code optimal donne donc des mots plus courts aux symboles plus probables.

Second lemme: les deux symboles les moins probables peuvent être pris frères. Dans un arbre complet, une feuille de profondeur maximale a un frère, qui est aussi une feuille (sinon il serait plus profond). Par le premier lemme, ces deux feuilles portent des symboles de probabilité minimale, à un échange près qui ne change pas la longueur moyenne. Il existe donc un code optimal où les deux symboles les moins probables sont frères et de profondeur maximale.

Récurrence. Soit $p_{m - 1}$ et $p_{m}$ les deux plus petites probabilités. Fusionnons-les en un symbole $σ$ de probabilité $p_{m - 1} + p_{m}$ , ce qui donne une source à symboles. À tout code de correspond un code de obtenu en ajoutant un et un au mot de , et l'on a exactement

\overset{ˉ}{L} (C) = \overset{ˉ}{L} (C^{'}) + (p_{m - 1} + p_{m}), (7.10)

car les deux symboles gagnent un bit chacun. Le terme ajouté ne dépend pas du code: minimiser $\overset{ˉ}{L} (C)$ parmi les codes de cette forme revient donc à minimiser $\overset{ˉ}{L} (C^{'})$ . Le second lemme dit qu'un code optimal de $X$ est de cette forme. Par hypothèse de récurrence, l'algorithme produit un code optimal pour $X^{'}$ ; en défusionnant, il produit donc un code optimal pour . Le cas est immédiat: les deux mots et donnent , ce qu'aucun code ne bat.

Explorateur 7.1 · Huffman en direct

Réglez les fréquences des quatre symboles: l'arbre de Huffman, le code et la longueur moyenne sont reconstruits à chaque mouvement. La jauge du bas montre la bande [H, H + 1) du théorème du codage de source — la longueur moyenne n'en sort jamais.

Fréquence de A12

Fréquence de B3

Fréquence de C2

Fréquence de D1

Entropie H

1,4047 b/symbole

Longueur moyenne L

1,5000 b/symbole

Écart L − H

0,0953 bit

Inégalité de Kraft

1,000

Message entier

27 bits pour 18 symboles

Prenez le temps de jouer avec cet explorateur, car il rend visible le contenu du théorème 7.4. Il démarre sur les fréquences $12, 3, 2, 1$ , pour lesquelles $H = 1, 4047$ et $\overset{ˉ}{L} = 1, 5000$ : l'écart vaut $0, 0953$ bit, et c'est l'écart, sur la jauge, entre le trait fin H et le trait épais L.

Mettez maintenant les quatre fréquences à la même valeur: l'entropie vaut $2$ bits, l'arbre devient équilibré, les quatre mots font deux bits, et l'écart tombe exactement à zéro — le cas d'égalité du théorème 7.3, puisque $1/4$ est une puissance de $1/2$ . Réglez ensuite $8, 4, 2, 2$ : les longueurs deviennent $1, 2, 3, 3$ , l'entropie vaut $1, 75$ et l'écart s'annule à nouveau. Puis déséquilibrez fortement, par exemple $16, 1, 1, 1$ : l'entropie descend à bit, tandis que la longueur moyenne vaut — car aucun mot ne peut faire moins d'un bit, et le symbole A, qui occupe seize places sur dix-neuf, en coûte déjà un. L'écart grimpe à bit, sans jamais atteindre . Quelle que soit la combinaison, le trait L reste dans la bande de H à H+1: c'est le théorème, vu de l'œil.

Question 7.5

Une source de $100$ symboles émet E $45$ fois, T $25$ fois, A $15$ fois, O $10$ fois et N $5$ fois. Construisez son code de Huffman et donnez la taille totale du message codé, en bits.

Au-delà de Huffman: le codage arithmétique

Huffman est optimal parmi les codes qui attribuent un nombre entier de bits à chaque symbole. C'est cette clause qui coûte le demi-bit d'ABRACADABRA, et le codage arithmétique (Rissanen, Pasco, années 1970) la supprime en changeant complètement d'objet: il ne code plus les symboles un par un, il code le message entier comme un seul nombre.

L'idée est géométrique. On part de l'intervalle $[0, 1 [$ et on le découpe en sous-intervalles dont les longueurs sont les probabilités des symboles. Lire le premier symbole revient à se restreindre à son sous-intervalle; on le redécoupe dans les mêmes proportions, on lit le deuxième symbole, et ainsi de suite. Après $n$ symboles, il reste un intervalle $[α, β [$ dont la largeur est exactement le produit des probabilités des symboles lus:

β - α = k = 1 \prod n p_{x_{k}} . (7.11)

Tout nombre de cet intervalle identifie le message, et il suffit d'en transmettre un: on choisit celui dont l'écriture binaire est la plus courte. Or nommer un point dans un intervalle de largeur $w$ demande environ $⌈ - lo g_{2} w ⌉$ bits, plus un ou deux bits pour garantir qu'on reste bien à l'intérieur.

Le codage arithmétique a un second avantage, plus important encore en pratique: il se marie naturellement avec un modèle adaptatif. Rien n'oblige à garder les mêmes probabilités d'un symbole au suivant; on peut les mettre à jour au fil du texte, ou les conditionner aux symboles précédents (un u après un q en français est presque certain, donc presque gratuit). Le codeur et le décodeur font la même mise à jour et restent synchronisés. C'est le mécanisme des compresseurs les plus performants d'aujourd'hui, et c'est aussi ce qui les rend lents.

Lempel–Ziv: comprimer sans connaître la source

Huffman et le codage arithmétique ont un défaut commun: ils exigent de connaître les probabilités. Il faut soit les transmettre avec le fichier, soit les deviner. Or on ne dispose en général d'aucun modèle probabiliste d'un fichier quelconque.

Lempel et Ziv (1977, 1978) proposent un changement de stratégie: ne pas modéliser du tout, et se contenter de remplacer les répétitions par des renvois. Un dictionnaire des morceaux déjà vus se construit au fil de la lecture, à l'identique chez le codeur et chez le décodeur — qui n'a donc rien à recevoir de plus.

LZ78: un dictionnaire de phrases

La variante de 1978 découpe le texte en phrases dont chacune est une phrase déjà vue, prolongée d'un caractère. Chaque phrase est émise comme un couple (indice de la phrase antérieure, caractère ajouté), l'indice $0$ désignant la phrase vide.

Exemple 7.5 · LZ78 sur ABRACADABRA

Lisons le message de gauche à droite en tenant le dictionnaire à jour.

Étape	Phrase nouvelle	Couple émis	Dictionnaire après
1	A	(0, A)	1: A
2	B	(0, B)	2: B
3	R	(0, R)	3: R
4	AC	(1, C)	4: AC
5	AD	(1, D)	5: AD
6	AB	(1, B)	6: AB
7	RA	(3, A)	7: RA

Le message est reconstitué à partir des seuls couples: chacun désigne une phrase déjà construite et lui ajoute un caractère, ce qui reconstruit à la fois le texte et le dictionnaire. La vérification en Python redonne bien ABRACADABRA.

Et le bilan? Sept couples pour onze symboles. Même en codant chaque indice sur le minimum de bits nécessaires et chaque caractère sur trois bits, on dépasse largement les $23$ bits de Huffman. Lempel–Ziv perd sur un message de onze symboles, et c'est normal: l'algorithme passe la première moitié du fichier à apprendre le dictionnaire. Il ne devient rentable que sur des données longues — où il devient redoutable.

LZ77: une fenêtre glissante

La variante de 1977, celle qu'utilisent les formats courants, ne construit pas de dictionnaire explicite: elle regarde en arrière dans une fenêtre de texte déjà émis et remplace le morceau courant par un triplet (distance en arrière, longueur de la copie, caractère suivant), ou par un littéral quand aucune répétition n'est trouvée.

Sur la chaîne ABRACADABRACADABRA, un programme de recherche exhaustive du plus long facteur répété produit la séquence suivante, vérifiée par reconstruction:

littéral A   littéral B   littéral R   littéral A
littéral C   littéral A   littéral D
copie (distance 7, longueur 11)

Huit jetons pour dix-huit symboles. Le dernier mérite un regard: la copie a une longueur de $11$ alors que la source ne se trouve qu'à $7$ caractères en arrière. La copie se chevauche elle-même. Ce n'est pas un bug: le décodeur copie caractère par caractère, si bien que les caractères qu'il vient d'écrire deviennent disponibles pour la suite de la même copie. C'est ainsi que LZ77 encode une répétition périodique à un prix constant. Sur ABABABABABAB, le même programme produit littéral A, littéral B, copie (distance 2, longueur 10): trois jetons pour douze symboles.

Question 7.6

Remettez dans l'ordre les étapes de la compression d'un fichier texte par un format de type DEFLATE.

Glissez les éléments pour les mettre dans le bon ordre

Remplacer chaque répétition par un couple distance-longueur et laisser les autres caractères en littéraux

Construire un code de Huffman sur ces fréquences et écrire sa table dans l'en-tête

Lire le fichier et chercher, pour chaque position, la plus longue répétition dans la fenêtre précédente

Écrire la suite des jetons codés avec ce code de Huffman

Compter les fréquences des littéraux, des longueurs et des distances produits

La compression avec pertes

Tout ce qui précède respectait une contrainte absolue: restituer l'original bit pour bit. Le théorème 7.3 fixe alors un plancher infranchissable, l'entropie de la source. Pour descendre plus bas, il n'y a qu'un moyen: renoncer à la fidélité exacte.

Le principe de la compression avec pertes tient en une phrase: jeter ce que le destinataire ne remarquera pas. Ce «ne remarquera pas» n'est pas une notion mathématique mais une notion perceptive, et c'est pourquoi ces formats reposent sur des modèles de la vision et de l'audition humaines autant que sur des mathématiques.

Le schéma est presque toujours le même, en trois étages.

Transformer. On change de représentation pour concentrer l'information. Un signal exprimé en fréquences au lieu d'échantillons temporels, ou une image exprimée en motifs spatiaux au lieu de pixels, a la propriété que la plupart de ses coefficients sont proches de zéro. La transformation elle-même est réversible et ne perd rien.
Quantifier. On arrondit les coefficients, grossièrement là où l'œil ou l'oreille est peu sensible, finement ailleurs. C'est ici et seulement ici que l'information est détruite, et c'est cet étage que règle le curseur de «qualité».
Coder sans perte. Les coefficients quantifiés, dont beaucoup sont devenus nuls, sont enfin comprimés par un codeur entropique — exactement ceux de ce chapitre.

JPEG applique ce schéma aux images fixes. Il convertit d'abord les couleurs en une composante de luminance et deux de chrominance, et sous-échantillonne souvent les secondes, parce que l'œil humain distingue moins finement les variations de couleur que celles de clarté. Il découpe ensuite l'image en blocs de $8 \times 8$ pixels et applique à chaque bloc une transformée en cosinus discrète, qui exprime le bloc comme une somme de motifs de fréquences spatiales croissantes. Les coefficients sont divisés par une table de quantification — l'étage destructeur — puis parcourus en zigzag, du plus basse fréquence au plus haute, ce qui regroupe les zéros en fin de parcours; une compression par plages et un codage de Huffman terminent le travail.

MP3 applique le même schéma au son. Un banc de filtres décompose le signal en bandes de fréquences. En parallèle, un modèle psychoacoustique estime, pour chaque instant et chaque bande, le seuil de masquage: le niveau en dessous duquel un son ne sera pas entendu parce qu'un son voisin, plus fort, le couvre. Ce masquage est un phénomène mesuré de l'audition, en fréquence comme dans le temps. Le codeur alloue alors les bits bande par bande de façon que le bruit de quantification reste sous ce seuil, et code enfin les coefficients quantifiés par un codage de Huffman.

Ce qui est perdu ne revient pas

Trois conséquences pratiques, et une mise en garde sur les chiffres.

Le réencodage cumule les dégâts. Ouvrir un JPEG, le modifier, le réenregistrer en JPEG applique une seconde quantification à des données déjà quantifiées. Les pertes s'ajoutent à chaque génération. Pour un travail itératif, on conserve un original sans perte.
Comprimer un JPEG avec un outil sans perte ne donne presque rien: les données sont déjà passées par un codeur entropique, leur redondance a disparu, et l'on retombe sur le théorème 7.1.
Sans perte ne veut pas dire sans compression. PNG et FLAC sont sans perte et compriment réellement, en exploitant la corrélation entre pixels ou entre échantillons voisins, puis en codant les résidus. Ils gagnent moins que JPEG ou MP3, mais ils restituent l'original exactement.

Quant aux taux annoncés par les fabricants ou les articles de vulgarisation, ils dépendent entièrement du contenu, du réglage de qualité et de l'implémentation. Un taux n'a de sens que mesuré sur un corpus décrit. Ce chapitre ne cite donc aucun taux qu'il n'a pas calculé lui-même.

Une comparaison de bout en bout

Terminons par une mesure complète sur un texte réel, avec les trois grandeurs côte à côte. Le texte suivant a été écrit sans accents, pour que chaque caractère occupe exactement un octet et que les comptes ne dépendent pas de l'encodage.

Exemple 7.6 · Entropie, Huffman et zlib sur le même texte

Le texte compte $261$ caractères et $27$ symboles distincts (lettres, espace, apostrophe, point):

Un code prefixe est un code dans lequel aucun mot n'est le prefixe d'un autre mot. Un code prefixe se decode sans ambiguite, de gauche a droite, sans jamais revenir en arriere. Un code prefixe se lit sur un arbre binaire dont les mots du code sont les feuilles.

Les quatre mesures, toutes calculées en Python:

Mesure	Taille	Par symbole
Texte brut, un octet par caractère	2 088 bits (261 octets)	8 bits
Borne d'entropie d'ordre 0	1 060 bits (132,5 octets)	4,0616 bits
Code de Huffman, données seules	1 071 bits (133,9 octets)	4,1034 bits
Code de Huffman, table comprise	1 395 bits (174,4 octets)	5,34 bits
`zlib.compress(..., 9)`	1 216 bits (152 octets)	4,66 bits

Commentons chaque écart, car chacun a une cause différente.

Huffman contre entropie. $4, 1034$ contre $4, 0616$ : la pénalité de longueur entière, bit par symbole. L'encadrement du théorème 7.4 est vérifié, et la somme de Kraft du code vaut exactement .

Question 7.7

Le texte de l'exemple 7.6 compte $261$ caractères et son code de Huffman occupe $1071$ bits. Quel est le taux de compression $ρ$ par rapport au texte brut codé sur un octet par caractère, table non comprise?

Synthèse

Deux familles, deux contrats. La compression sans perte restitue l'original bit pour bit et son codeur est injectif; la compression avec pertes ne le fait pas, et c'est précisément en confondant des données distinctes qu'elle gagne de la place. Le choix dépend du destinataire, pas de l'algorithme.
Aucun compresseur sans perte ne raccourcit tout. Le principe des tiroirs suffit à le prouver, et il donne même une majoration: moins d'une suite de $n$ bits sur $2^{k - 1}$ peut être raccourcie de $k$ bits. Un compresseur est un pari sur la structure des fichiers réels; zipper deux fois fait grossir le fichier, et des données aléatoires ou déjà comprimées ne se compriment pas.
Un code préfixe est un arbre. Ses mots sont les feuilles, il se décode de gauche à droite sans jamais revenir en arrière, et l'inégalité de Kraft $\sum_{i} 2^{- ℓ_{i}} \leq 1$ caractérise exactement les longueurs réalisables: nécessaire par disjonction des sous-arbres, suffisante par la construction des sommes partielles.

Série d'exercices du chapitre 7Exercice 1 sur 5

Question 7.8

Un fichier de $1$ Mo est comprimé en $250$ ko par un outil sans perte. Que vaut le taux de compression $ρ$ défini par (7.1)?

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Exercice 7.1 · Codes préfixes et inégalité de Kraft

Parmi les suites de longueurs suivantes, lesquelles peuvent être celles d'un code binaire préfixe? $(a) 1, 2, 3, 4, 4$ ; $(b) 2, 2, 2, 3, 3$ ; $(c) 1, 2, 2, 2$ ; .

Exercice 7.2 · Un code de Huffman complet

Une source émet six symboles avec les fréquences suivantes, observées sur $100$ émissions: $a$ $= 38$ , $b = 22$ , $c = 17$ , $d = 13$ , $e = 6$ , .

Exercice 7.3 · L'argument de comptage, quantifié

Montrer qu'un codeur sans perte qui raccourcit strictement au moins une suite de longueur $n$ allonge nécessairement au moins une suite de longueur au plus $n$ .
Soit $S_{n}$ l'ensemble des $2^{n}$ suites de longueur $n$ et $c$ un codeur sans perte. Montrer que la longueur moyenne est strictement supérieure à . On pourra utiliser .

Exercice 7.4 · Quand un bit de trop coûte cher

Soit une source binaire sans mémoire émettant $0$ avec la probabilité $p$ et $1$ avec la probabilité $1 - p$ , avec $p = 0, 9$ .

Calculer son entropie $H$ . On donne $lo g_{2} 0, 9 = - 0, 15200$ et .

Exercice 7.5 · Lempel–Ziv à la main

Coder la chaîne AAABAAABAAAB par LZ78 (couples indice-caractère, l'indice $0$ désignant la phrase vide) et donner le dictionnaire obtenu.
Décoder la suite de couples LZ78 suivante, sur l'alphabet des lettres: $(0, B)$ , $(0, A)$ , $(2, N)$ , $(3, A)$ , $(1, A)$ .

Références

Shannon, C. E., A Mathematical Theory of Communication, Bell System Technical Journal, vol. 27, 1948 (l'article fondateur: le théorème du codage de source y est le théorème 9).
Huffman, D. A., A Method for the Construction of Minimum-Redundancy Codes, Proceedings of the IRE, vol. 40, 1952.
Cover, T. M. et Thomas, J. A., Elements of Information Theory, 2e éd., Wiley, Hoboken, chap. 5 (inégalité de Kraft, optimalité de Huffman) et chap. 13 (Lempel–Ziv).
MacKay, D. J. C., Information Theory, Inference and Learning Algorithms, Cambridge University Press (disponible librement), chap. 4 à 6.
Abelson, H., Ledeen, K. et Lewis, H., Blown to Bits, Addison-Wesley, Boston, chap. 3.
Sayood, K., Introduction to Data Compression, 5e éd., Morgan Kaufmann, Cambridge (codage arithmétique, JPEG, MP3).

Longueur	Somme partielle	Mot obtenu
1	0	0
2	1/2	10
3	3/4	110
3	7/8	111

Fusion	File avant (poids)	Deux plus petits	Nœud créé	File après
1	A 5, B 2, R 2, C 1, D 1	C 1 et D 1	CD, poids 2	A 5, B 2, R 2, CD 2
2	A 5, B 2, R 2, CD 2	B 2 et R 2	BR, poids 4	A 5, CD 2, BR 4
3	A 5, CD 2, BR 4	CD 2 et BR 4	CDBR, poids 6	A 5, CDBR 6
4	A 5, CDBR 6	A 5 et CDBR 6	racine, poids 11	racine 11

Fusion	Deux plus petits	Nœud créé	File après
1	$f$ 4 et $e$ 6	$e f$ = 10	$a$ 38, $b$ 22, $c$ 17, $d$ 13, $e f$ 10
2	$e f$ 10 et $d$ 13	$d e f$ = 23	$a$ 38, $d e f$ 23, $b$ 22, $c$ 17
3	$c$ 17 et $b$ 22	$b c$ = 39	$b c$ 39, $a$ 38, $d e f$ 23
4	$d e f$ 23 et $a$ 38	$a d e f$ = 61	$a d e f$ 61, $b c$ 39
5	$b c$ 39 et $a d e f$ 61	racine = 100	racine 100

Objectifs du chapitre

Ce que comprimer veut dire

Aucun compresseur ne comprime tout

Codes à longueur variable

Le problème du décodage

Codes préfixes et arbres binaires

L'inégalité de Kraft

Longueur moyenne et théorème du codage de source

La quantité à minimiser

La borne inférieure: on ne descend pas sous l'entropie

La borne supérieure: un bit, jamais plus

Le codage de Huffman

L'algorithme

ABRACADABRA, fusion par fusion

Les vingt-trois bits contre les vingt-deux et demi

Huffman est optimal

Au-delà de Huffman: le codage arithmétique

Lempel–Ziv: comprimer sans connaître la source

LZ78: un dictionnaire de phrases

LZ77: une fenêtre glissante

La compression avec pertes

Une comparaison de bout en bout

Synthèse

Exercices

Références

Le point de départ: la longueur fixe

Le plancher: l'entropie

Le code de Huffman

Le bilan, et ce qu'il ne dit pas

Étape	Phrase	Couple	Dictionnaire
1	A	(0, A)	1: A
2	AA	(1, A)	2: AA
3	B	(0, B)	3: B
4	AAA	(2, A)	4: AAA
5	BA	(3, A)	5: BA
6	AAB	(2, B)	6: AAB