Codage arithmetique

Le codage arithmétique est une technique de compression sans perte. Normalement une chaîne de caractères comme "hello world" est représentable en utilisant un nombre fixe de bits par caractère, comme dans le code ASCII. Comme le Codage de Huffman, le codage arithmétique est un code à longueur variable. Ce qui différencie le codage arithmétique des autres codages source est qu'il encode le message entièrement et le représente par un seul nombre n (flottant) alors que les autres codages séparent le message d'entrée en les symboles qui le composent et encodent ensuite chaque symbole par un mot code.

Le codage arithmétique est toujours meilleur que le Codage de Huffman sauf si dans l'arbre de Huffman tous les poids des feuilles/noeuds/racines sont des puissances de 2.

Exemple: Si les poids sont A 1, B 1, C 1 l'arbre d'Huffman sera le suivant

On voit que A qui est pourtant aussi fréquent que B ou C est avantagé et on utilisera en moyenne 5/3= 1,667 bits par caractère. Le codage arithmétique utilisera lui exactement log2(3) bits par caractère soit 1,585 bits par caractère. Ce serait encore plus flagrant avec des poids tels que A 31, B 1 qui donneraient 1 bit par caractère pour Huffman contre (31 * (log2(32) - log2(31)) + 1 * (log2(32) - log2(1)))/32 = 0,201 soit 5 fois moins.

Le principe consiste à transformer les poids en intervale. Pour A 1, B 1, C 1 on a

Donc au depart l'encodeur rencontre A, son intervale deviendra [0, 1/3] puis B, la composition des intervales donne [1/9, 2/9] puis C [1/9+2/27, 2/9] puis ...

En terme informatique on ne peut pas se permettre de stocker des fractions non calculées, il y a donc des erreurs au niveau des arrondis, mais ce type de codage va faire les mêmes erreurs au décodage qu'a l'encodage et evite donc cet eccueil. De la même manière on ne peut pas gérer un flottant qui serait codé sur plusieurs dizaines de Ko (voire Mo, Go) il faut donc "streamer" l'intervale: Pour [0,1/3] mon intervale est en dessous de 1/2 et le sera toujours, à quoi bon utiliser un bit en memoire pour garder cette information, l'encodeur envoi un 0 dans la sortie et je tranforme mon interval en [0, 2/3]. De la même manière si il est plus élevé que 1/2 l'encodeur envoi un 1. Par contre si 1/2 est contenu dans l'intervale l'encodeur ne peut rien envoyer mais il va peut être être amené à le faire si il arrive en limite de precision exemple : l'encodeur doit savoir qu'avec sa precision en memoire pour les flottants il ne sera pas à même de decouper l'intervale [0,49999999999 , 0,5000000001] sans pertes d'information (les erreurs d'arrondi causent des décalages de l'intervale mais pas de perte) dans ce cas l'encodeur sera obligé de couper l'intervale en deux.

Voir aussi

• Codage de source
• Compression de données
• Codage de Huffman
• Codage de Shannon-Fano

Bibliographie

• *(en) David MacKay, Information Theory, Inference, and Learning Algorithms, 2003 [détail des éditions]

• Portail de l’informatique