Le codage arithmétique est une méthode de compression de données sans perte, de la famille du codage entropique. Il représente un message entier par un unique nombre compris entre 0 et 1, ce qui lui permet d'approcher de la compression maximum possible sans perte (l'entropie) de plus près que le codage de Huffman.
Esquissé dès 1948 par Claude Shannon et rendu récursif par Peter Elias, il ne passe de la théorie à la pratique qu'en 1976, lorsque Richard Pasco et Jorma Rissanen montrent comment le mener avec les nombres de précision finie qu'utilisent les ordinateurs. Son principe consiste à prendre l'intervalle [0 ; 1[, et à le restreindre à chaque ajout de symbole en sous-intervalles proportionnels à sa probabilité d'apparition, jusqu'à un intervalle dont tout nombre pioché dedans représentera le message dans son entièreté.
Longtemps jugé trop lent et gêné par des brevets, il s'est répandu à mesure que ceux-ci expiraient et qu'apparaissaient des implémentations plus rapides et mieux adaptées au matériel, comme le codage par intervalle, les codeurs binaires d'IBM, le CABAC ou les systèmes de numération asymétrique. Il est aujourd'hui omniprésent dans la compression d'images (JPEG 2000, JPEG XL), de vidéos (H.264, H.265, AV1) et de données en général (LZMA, Zstandard).
Histoire Les prémisses du codage arithmétique apparaissent en 1948, dans l'article fondateur de Claude Shannon sur la théorie de l'information. Il y suggère que des messages de symboles pourraient être codés en les classant tous par probabilité, puis en transmettant, pour le message voulu, la somme des probabilités de ceux qui le précèdent dans ce classement. Ce code prend la forme d'une fraction binaire : l'idée de représenter un message entier par un unique nombre compris entre 0 et 1 est née.
Des travaux non publiés de Peter Elias, décrits par Abramson en 1963, reprennent cette idée et la transforment en un algorithme récursif qui n'exige plus de trier les messages : la probabilité cumulée se calcule symbole par symbole, en restreignant l'intervalle à chaque ajout. La méthode reste cependant inutilisable en l'état : chaque ajout de symbole resserre l'intervalle, ce qui exige une précision arbitrairement grande pour le représenter et des calculs de plus en plus lourds à mesure que le nombre de décimales augmente.
C'est ce problème de précision que résolvent indépendamment deux chercheurs, Richard Pasco et Jorma Rissanen, en 1976. Ils montrent comment mener le même calcul avec une précision finie fixe, en arrondissant les valeurs intermédiaires, de sorte qu'un message de longueur quelconque puisse être codé sans que la précision nécessaire augmente avec lui. Le terme « codage arithmétique » apparaît la même année dans le titre de l'article de Rissanen.
Bien que le codage arithmétique offre un meilleur taux de compression que Huffman, et que la publication d'un code source performant en langage C en 1987 l'ait fait connaître, il peine à s'imposer. La méthode est jugée trop lente pour le matériel grand public, et juridiquement risquée en raison des multiples brevets déposés par IBM, dont certains portent justement sur des optimisations du temps de calcul.
D'autres évolutions arrivent ensuite. Les calculs sont accélérés en se restreignant à un codeur binaire, dont l'alphabet se limite aux bits 0 et 1, et en estimant les probabilités de façon dynamique. La première de ces optimisations, le Q-Coder d'IBM, remplace les multiplications de l'encodage par des additions et des décalages de bits, bien moins coûteux.
Son descendant, le QM-Coder, devient le codeur arithmétique commun aux standards JPEG (1992) et JBIG, mais reste soumis à une redevance. Le MQ-Coder, variante proche du QM-Coder dont il inverse l'attribution des sous-intervalles entre symbole le plus et le moins probable, est retenu en 2000 pour le JPEG 2000, puis le M-Coder (codeur modulo) équipe le codage CABAC des normes vidéo H.264 et H.265.
Leur diffusion s'élargit nettement dans les années 2010, portée d'abord par l'expiration progressive des brevets, puis par l'arrivée des systèmes de numération asymétrique (ANS), une famille voisine du codage arithmétique proposée par Jarek Duda à partir de 2007. L'ANS atteint un taux de compression proche de la limite théorique tout en étant généralement plus rapide que Huffman. Yann Collet en publie fin 2013 une implémentation libre et multi-symboles, le FSE (), dont la vitesse, en particulier au décodage, surpasse celle de l'implémentation Huffman de zlib. Adoptée dès 2015 par de grands acteurs du numérique, comme Facebook avec Zstandard et Apple avec LZFSE, puis par des formats d'image comme JPEG XL, cette approche fait du codage entropique proche de l'optimum une brique courante des formats modernes.
Principe vignette|alt=Six colonnes représentant l'intervalle de 0 à 1 partagé en trois bandes A, N et S proportionnelles à leurs probabilités. À chaque colonne, la bande de la lettre codée est redéployée sur toute la hauteur puis repartagée, l'intervalle se resserrant au fil du message ANANAS.|Visualisation du codage arithmétique du message ANANAS ainsi que de son décodage.
Comme tout codage entropique, le codage arithmétique cherche à réduire la taille d'un message en faisant en sorte que les symboles fréquents occupent moins de place que les symboles rares. La méthode la plus répandue de cette famille, le codage de Huffman, attribue à chaque symbole un code formé d'un nombre entier de bits, d'autant plus court que le symbole est fréquent.
Cette contrainte d'un nombre entier de bits par symbole impose une limite. Un symbole très fréquent, présent par exemple neuf fois sur dix, devrait idéalement coûter environ , mais le codage de Huffman lui attribue au minimum , soit plus de six fois la taille optimale. Le codage arithmétique lève cette limite en renonçant à coder les symboles un par un : il représente le message entier par un seul nombre, ce qui répartit le coût sans l'arrondir au bit pour chaque symbole.
Pour cela, il part de l'intervalle [0 ; 1[ et le partage en sous-intervalles, un par symbole de l'alphabet, dont la longueur est proportionnelle à la probabilité du symbole. Coder le premier symbole revient à se restreindre à son sous-intervalle, lui-même partagé de la même façon pour le symbole suivant, et ainsi de suite : chaque symbole emboîte l'intervalle un peu plus profondément. À la fin, l'intervalle obtenu est propre au message.
On transmet alors un seul nombre situé dans cet intervalle, et plus l'intervalle est large, plus il est facile d'y trouver un nombre à peu de chiffres. Or un symbole fréquent, qui occupe un large sous-intervalle, ne resserre l'intervalle que faiblement, là où un symbole rare le resserre beaucoup. Un message fait surtout de symboles fréquents conserve donc un intervalle assez large, désigné par un nombre court. Ce nombre étant écrit en binaire, ces chiffres sont en fait des bits, et c'est là que se mesure le gain de compression.
Pour le codage, on note et les bornes inférieure et supérieure de l'intervalle courant, et sa longueur. Cet intervalle vaut [0 ; 1[ au départ. Dans la table de probabilités, le symbole à coder occupe un sous-intervalle de borne inférieure et de borne supérieure . Son ajout remplace les bornes courantes par :
On applique ces deux opérations à chaque symbole du message, puis on transmet un nombre situé dans l'intervalle final, accompagné de la longueur du message si aucun symbole dédié à signaler la fin du message (EOF pour End Of File) n'a été mis en place.
Le nombre transmis n'est pas un point quelconque de cet intervalle, mais le plus court à écrire en binaire. Pour l'obtenir, on n'en conserve que les premiers bits, juste assez pour que la valeur qu'ils désignent reste dans l'intervalle final une fois sa suite complétée par le décodeur selon une convention fixée. Il en faut de l'ordre de , à un ou deux bits près, où L est la longueur de l'intervalle final. Chaque message reçoit ainsi un préfixe de bits qui lui est propre, de sorte qu'aucun code n'est le début d'un autre.
Le décodage emprunte le chemin inverse à partir de ce nombre, noté , à l'aide de la même table de probabilités. À chaque étape, on identifie le symbole dont le sous-intervalle contient et on l'ajoute au message. À l'aide de la borne inférieure et de la probabilité de ce symbole (la longueur de son sous-intervalle), on remplace alors par :
ce qui ramène la valeur dans [0 ; 1[ pour l'étape suivante. On répète l'opération autant de fois que le message compte de symboles ou jusqu'à rencontrer le symbole EOF.
Exemple Mettons que nous voulions dérouler le codage arithmétique tel que proposé par Elias (sans renormalisation) sur le message « ANANAS », en traitant chaque lettre comme un symbole et sans recourir à un symbole de fin. On suppose donc que la longueur du message est transmise en même temps que la valeur codée.
On relève d'abord le nombre d'apparitions de chaque lettre, puis on en déduit sa probabilité d'apparition et l'intervalle qui lui est attribué dans [0 ; 1[, de longueur proportionnelle à cette probabilité.
+ Probabilités et intervalles des lettres de « ANANAS » Lettre Nombre d'apparitions Probabilité Intervalle Intervalle (décimal) A 3 1/2 [0 ; 1/2[ [0 ; 0,5[ N 2 1/3 [1/2 ; 5/6[ [0,5 ; 0,833[ S 1 1/6 [5/6 ; 1[ [0,833 ; 1[
Les valeurs décimales sont données à titre informatif, mais les calculs sont menés sur les fractions exactes.
Codage
Le codage part de l'intervalle [0 ; 1[, puis le restreint à chaque lettre lue en utilisant les formules vues plus haut.
Par exemple, pour la deuxième lettre, un N, l'intervalle courant est [0 ; 1/2[, donc et . Le N occupe l'intervalle [1/2 ; 5/6[, d'où une nouvelle borne inférieure et une nouvelle borne supérieure .
En appliquant ces opérations à chaque lettre, on obtient :
+ Codage du message « ANANAS » Lettre ajoutée Borne inférieure Borne supérieure Longueur de l'intervalle Départ 0 1 1 A 0 1/2 1/2 N 1/4 5/12 1/6 A 1/4 1/3 1/12 N 7/24 23/72 1/36 A 7/24 11/36 1/72 S 131/432 11/36 1/432
À l'issue du codage, l'intervalle obtenu est [131/432 ; 11/36[, soit environ [0,3032 ; 0,3056[. N'importe quel nombre de cet intervalle représente fidèlement le message. On en choisit un dont l'écriture reste simple, par exemple 263/864 ≈ 0,304, qui sert de valeur codée finale.
Décodage Le décodage utilise le même tableau de probabilités. À chaque étape, on identifie la lettre dont l'intervalle contient la valeur courante, on l'ajoute au message, puis on ramène cet intervalle à [0 ; 1[ et on recommence.
Par exemple, la valeur initiale 263/864 ≈ 0,304 tombe dans [0 ; 1/2[, l'intervalle du A : la première lettre est donc A. La nouvelle valeur est .
En répétant l'opération, on retrouve les lettres du message :
+ Décodage de la valeur 263/864 Valeur courante Symbole décodé Nouvelle valeur 263/864 ≈ 0,304 A 263/432 263/432 ≈ 0,608 N 47/144 47/144 ≈ 0,326 A 47/72 47/72 ≈ 0,653 N 11/24 11/24 ≈ 0,458 A 11/12 11/12 ≈ 0,917 S 1/2
Au bout de six lettres, le décodeur a reconstruit le message « ANANAS ». Comme la longueur du message a été transmise avec la valeur codée, le décodeur sait qu'il doit s'arrêter ici.
Sans cette information, rien n'indiquerait que le message est terminé. Le calcul se poursuivrait et produirait des lettres supplémentaires, étrangères au message d'origine. En reprenant à partir de la dernière valeur obtenue, 1/2, le décodage continuerait ainsi :
+ Poursuite du décodage au-delà du message Valeur courante Symbole décodé Nouvelle valeur 1/2 ≈ 0,5 N 0 0 A 0 0 A 0
La valeur reste alors bloquée à 0 et le décodeur sort une suite infinie de A. Pour éviter ce comportement, on transmet la longueur du message, comme dans cet exemple, ou bien on ajoute à l'alphabet un symbole de fin qui marque l'arrêt du décodage.
Assises mathématiques