Codage arithmétique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le codage arithmétique est un codage entropique utilisé en compression de données 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/nœuds/racines sont des puissances de 2.

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

0 A
10 B
11 C

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  \frac {(31 \times (log_2(32) - log_2(31)) + 1 \times (log_2(32) - log_2(1)))} {32} = 0,201 soit 5 fois moins.

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

[0, 1/3] A
[1/3, 2/3] B
[2/3, 1] C

Donc, au départ, l'encodeur rencontre A, son intervalle deviendra [0, 1/3] ; puis B, la composition des intervalles 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'à l'encodage et évite donc cet écueil. 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'intervalle : Pour [0, 1/3], mon intervalle est en dessous de 1/2 et le sera toujours, à quoi bon utiliser un bit en mémoire pour garder cette information ? L'encodeur envoie un 0 dans la sortie, et je transforme mon intervalle en [0, 2/3]. De la même manière, s'il est plus élevé que 1/2, l'encodeur envoie un 1. Par contre si 1/2 est contenu dans l'intervalle, l'encodeur ne peut rien envoyer mais il va peut-être être amené à le faire s'il arrive en limite de précision. Par exemple : l'encodeur doit savoir qu'avec sa précision en mémoire pour les flottants, il ne sera pas à même de découper l'intervalle [0,49999999999 , 0,5000000001] sans pertes d'information (les erreurs d'arrondi causent des décalages de l'intervalle mais pas de perte). Dans ce cas, l'encodeur sera obligé de couper l'intervalle en deux.


Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]