RANGE CODER


* Introduction

C'est un compresseur qui se base sur des statistiques, un peu comme l'algorithme de huffman.
Le principe est de donner la probabilité du message à coder en fonction des plages occupées par ces probabilités.
Par exemple pour le message "ab" ou "a" aurait une probabilité de 0.7 et "b" 0.3 :
"a" a une plage de [0.0 - 0.7]
"b" a une plage de [0.7 - 1.0]
donc le premier caractère "a" peut être représenté par la plage [0.0 - 0.7]
on peut représenter "ab" par une plage comprise dans la plage de "a"
"aa" a une plage [0.00 - 0.49]
"ab" a une plage [0.49 - 0.70]
notre message "ab" peut donc être représenté par la probabilité 0.49.
Et ainsi de suite pour tout le message.

* Pourquoi est ce mieux que l'algorithme de Huffman ?

Car le code de chaque caractère du message ne se fait pas au bit près. Il se fait sur des fractions de bits.

* Comment est ce possible de coder des fractions de bits ?

Prenons un exemple : on doit coder plusieurs valeurs qui peuvent varier de 0 a 5.
Première méthode on assigne 3 bits (0-7) :
si v1=2, v2=4, v3=1, v4=5 on obtient 4x3 bits = 12 bits (010 100 001 110)
Deuxième méthode : on se dit qu'il n'y a que 6 valeurs possibles pour chaque valeur.
Donc plutôt que de coder au bit près on va coder "à la valeur près".
En effet quand on code au bit près on fait :
v1 + v2x8 + v3x64 + v4x512 == v1 + v2x81 + v3x82 + v4x83
mais on a pas besoin d'autant de valeur : on peut donc réduire au nombre de valeur qui nous interesse :
v1 + v2x6 + v3x36 + v4x216 == v1 + v2x61 + v3x62 + v4x63
dans notre exemple cela donne 2+4x6+1x36+5x216=1142 (10001110110) 11 bits !
En fait si on ne pense plus en terme de bit fixe mais de fraction de bit, on peut se dire que :
Si l'intervalle 0 a 7 peut être codé sur 3 bits,
alors l'intervalle de 0 a 5 peut être codé sur log2(6)=log(6)/log(2)=2.58bits environ
soit pour 4 valeurs 4 x 2.58 = 10.34 Arrondi a 11 bits car tout bit entamé est un bit compté.

Voila ce qui fait la force d'un compresseur dit arithmétique par rapport à un compresseur de Huffman : sa précision.

* Doit on travailler en nombre à virgule ?

Le mieux est de travailler avec des nombres entiers. En effet, les ordinateurs s'en accomodent mieux.
Prenons pour cela un exemple un peu plus complet que ceux précédent.
nous avons le message "abaacbcaca" à coder.
Premièrement on extrait le nombre de caractères : (a,5) (b,2) (c,3)
Ceci nous permets de construire les plages : a [0-5] b [5-7] c [7-10]
Le nombre de caractère (10) n'est pas fortuit, il va permettre de mieux comprendre ce qui se passe :
en décimal. une division par 10 revient à éliminer un chiffre).
On démarre avec une plage assez grande [0 - 10000] qui représente la plage [0.0 - 1.0] :
"" a une plage de [00000 - 10000]
"a" a une plage de [00000 - 05000]
"ab" a une plage de [02500 - 03500]
on remarque que le calcul de la valeur basse de la plage est calculée comme suit :
Vb(i) = valeur basse de la plage de codage courante
Vb(i-1) = valeur basse de la plage de codage précédente
Vh(i) = valeur haute de la plage de codage courante
Vh(i-1) = valeur haute de la plage de codage précédente
NbChar = Nombre total de caractères
Pb = Valeur basse de la plage du caractère en cours de codage
Ph = Valeur haute de la plage du caractère en cours de codage


la valeur haute de la plage est :

Vh(i) = Vb(i-1) + Ph x (Vh(i-1) - Vb(i-1)) / NbChar

de même la valeur basse de la plage est :

Vb(i) = Vb(i-1) + Pb x (Vh(i-1) - Vb(i-1)) / NbChar

On peut donc continuer a coder le message :
"ab" a une plage de [02500 - 03500]
"aba" a une plage de [02500 - 03000]
"abaa" a une plage de [02500 - 02750]
"abaac" a une plage de [02675 - 02750]
"abaacb" a une plage de [02712.5 - 02727.5]
Une virgule ! Ceci n'est pas acceptable. On remarque pourtant que l'on aurait pu être un peu plus prévenant.
En effet, depuis "abaa" on remarque que la plage est comprise entre [02500 - 02750], on sait donc que peut importe
le message venant ensuite, on sera dans les 2000. On va donc ne plus prendre en compte les 2000 pour ne s'interesser
qu'à la plage de plus petite valeur. C'est ce que l'on appelle la normalisation de l'intervalle.
La plage de "abaa", [02500 - 02750] devient [50000 - 75000]. On a enlever 02 en tête et on a rajouté 00 en fin de nombres.
Est ce que cela change quelque chose pour la suite du message ?
"abaac" a une plage de [67500 - 75000]
"abaacb" a une plage de [71250 - 72750] (il n'y a plus de virgule)
"abaacbc" a une plage de [72300 - 72750]
"abaacbca" a une plage de [72300 - 72525] (normalisation on enlève 72)
"abaacbca" a une plage de [30000 - 52500]
"abaacbcac" a une plage de [45750 - 52500]
"abaacbcaca" a une plage de [45750 - 49125]

Le message final est donc 027247. le 7 de la fin provient du fait que l'on est entre 45000 et 49000 on prends donc au milieu.

* Décodons !

Pour décoder le message on a donc une plage [00000 - 10000] vide, et on cherche à savoir ou tombe le chiffre
que l'on va traiter ici en l'occurence 2724 (représentant la probabilité 0.2724). On sait que dans une plage comme celle là,
on a la distribution suivante :
[00000 - 05000] pour "a"
[05000 - 07000] pour "b" et
[07000 - 10000] pour "c"
Comme on voit arriver le nombre 2724 on se doute qu'il va tomber dans la plage du "a" car 0 < 2724 < 5000.
on sait donc que notre premier caractère est "a".
Dans la plage de "a" il y a la distribution suivante :
[00000 - 02500] pour "aa"
[02500 - 03500] pour "ab"
[03500 - 05000] pour "ac"
comme 2500<2724<3500 alors on sait que le second caractère est "b".
[02500 - 03000] pour "aba"
[03000 - 03200] pour "abb"
[03200 - 03500] pour "abc"
comme 2500<2724<3000 alors on sait que le troisième caractère est "a".

le prochain caractère est donc (Message - Vb(i-1)) x NbChar / (Vh(i-1) - Vb(i-1))
ex : dans le premier cas (2724-0)x10/(10000-0) = 2 -> a car 0<=2<5
dans le second cas (2724-0)x10/(5000-0) = 5 -> b car 5<=5<7
dans le troisieme cas (2724-2500)x10/(3500-2500) = 2 -> a car 0<=2<5

Message [02724] plage [00000 - 10000] donne "a"
Message [02724] plage [00000 - 05000] donne "b"
Message [02724] plage [02500 - 03500] donne "a"
Message [02724] plage [02500 - 03000] donne "a"
Message [02724] plage [02500 - 02750] on peut normalizer
Message [72470] plage [50000 - 75000] on note l'apparition du 5 provenant de 027245
Message [72470] plage [50000 - 75000] donne "c"
Message [72470] plage [67500 - 75000] donne "b"
Message [72470] plage [71250 - 72750] donne "c" (72470-71250)x10/(72750-71250)=12200/1500=8 c[7-10]
Message [72470] plage [72300 - 72750] on peut normaliser
Message [47000] plage [30000 - 75000] donne "a" (3.77)
Message [47000] plage [30000 - 52500] donne "c" (7.5)
Message [47000] plage [45750 - 52500] donne "a"
Message [47000] plage [45750 - 49125]

Comment detecter la fin du message ? et bien on sais grâce aux statistiques qu'il y a 10 caractères.
On suppose bien sur que le codeur et le decodeur connaissent les statistiques.

On sais maintenant coder et décoder un message range code sous forme décimale. Il ne devrait pas être très compliqué
de passer à une forme hexadécimale. Il reste cependant un point que l'on a pas trop aborder. Que se passe t il dans
le cas ou l'on peut perdre de la précision ?

* Attention on peut perdre de la précision !

Ex: le message "ccccb". Si on garde la même plage de début qu'auparavent on obtient :
"" plage [00000 - 10000]
"c" plage [07000 - 10000]
"cc" plage [09100 - 10000]
"ccc" plage [09730 - 10000]
"cccc" plage [09919 - 10000]
"ccccb" plage [09959.5 - 10000] et c'est le drame.
On a pas pu écarter les premiers chiffres car ils sont toujours différent : (10 != 09) et on a atteinds la limite de précision.
On sais que dans le cas "cccc" donc la plage [09919 - 10000], il va y avoir potentiellement un problème, car 10000-9919=81,
qui ne va pas bien se diviser par 10. On rearrange la plage et on garde un compteur qui indique que l'on a manqué de précision.
On sais que la plage est entre 099xx et 100xx ou encore entre 09xxx et 10xxx donc on peut enlever le second chiffre et le
remplacer par un compteur. Ce compteur signifie que l'on a enlever ce chiffre (0 et 9). Dès que les premiers chiffres
de la plage sont identique on va le restituer. Si la plage tends plutôt vers 0 comme premier chiffre on sais que l'on a
enlever un 9 donc on sors un 9 et si la plage tends plutôt vers le 1 (ce qui n'est pas possible dans notre exemple) on ajoute
un 0 puisque c'est un zero qui devra être présent dans le message.

[09919 - 10000] -> [09190 - 10000] + compteur a 1
si maintenant on a un "b" [09595 - 09757] on peut donc sortir "0" plus un "9" provenant du compteur de manque de précision.
Le début du message sera donc "09" puis on renormalize normalement et on obtient un autre "9".
La plage est donc [59500 - 75700]. Et on peut donc finir par un "6" (compris entre 5 et 7).
Le message est donc "0996"

Message [09960] plage [00000 - 10000] donne "c"
Message [09960] plage [07000 - 10000] donne "c"
Message [09960] plage [09100 - 10000] donne "c"
Message [09960] plage [09730 - 10000] donne "c"
la nouvelle est plage [09919 - 10000] on la retaille [09190 - 10000] on fait pareil pour le message
Message [09600] plage [09190 - 10000] donne "b"

Ce qui est bien le bon message. La conclusion est que dès que l'on a une plage du type [39xxx - 40xxx] c'est à dire
la différence entre les premiers chiffres est 1 et le second chiffre est 9 pour la limite basse et 0 pour la limite haute,
alors on peut normaliser avec le compteur : [3xxx0 - 4xxx0].
L'exemple précédent donne donc :
"" plage [00000 - 10000]
"c" plage [07000 - 10000]
"cc" plage [09100 - 10000] compteur=1 [01000 - 10000]
"ccc" plage [07300 - 10000]
"cccc" plage [09190 - 10000] compteur=2 [01900 - 10000]
"ccccb" plage [05950 - 07570]

on peut enfin sortir "0" suivi de "99" (compteur fois "9") puis 6

* Fin de message

Il faut aussi faire attention a la fin du message. Si il reste des chiffres que l'on a pas sorti.
Ex : on prends l'exemple précédent :
"cccc" plage [09190 - 10000] compteur=2 la plage devient [01900 - 10000]
on prends le milieu de l'intervalle : (10000-1900)/2 = 4050, on l'ajoute a la valeur basse de la plage ou bien on la
soustrait a la valeur haute. cela donne 05950, ceci nous donne les derniers chiffres, sachant que l'on ecrit
"0" puis comme le compteur vaut 2 "99" puis "5950" ce qui nous donne le message : 0995950


* Implémentation : ca ne marche pas !

Effectivement si l'on essaye d'écrire l'algorithme tel que présenté ci dessus, cela ne fonctionnera pas. C'est à cause d'un probleme de plage. Lorsque l'on décode, on va mettre en jeu l'imprécision due au fait que l'on doit exclure les fins de plage et donc aller de 0.0 a 0.9999.... Cette variation insère lors de la normalisation des 0 pour la partie basse et des 9 pour la partie haute :

Cette version est plus exacte mathématiquement car on ne va pas jusqu'a 1.0 inclus mais exclu.
Les recherches dans les plages des lettres de bases (a[0-5] b[5-7] c[7-10]) sont donc un peu différentes.
En effet, comme on ne va pas jusqu'à 1, on est sur que les calculs vont donner une exclusion de la borne haute de ces
plages. Ceci va nous faciliter la tâche pour retrouver la lettre adéquate.

Plage de début : [0000 - 9999]

la valeur haute de la plage est calculée comme suit :

Vh(i) = Vb(i-1) + Ph * (Vh(i-1) - Vb(i-1) + 1) / NbChar - 1;

de même la valeur basse de la plage est :

Vb(i-1) = Vb(i-1) + Pb * (Vh(i-1) - Vb(i-1) + 1) / NbChar;

et le calcul de la valeur pour trouver la lettre dans les plages de recherche :

((Message - Vb(i-1) + 1) x NbChar - 1) / (Vh(i-1) - Vb(i-1) + 1)

Cette version implémentée donne des résultats correctes en compression et en décompression.