On considère une source sans mémoire I={0,…,n−1}
(typiquement n=256). Pour tout i dans I les probabilités sont
données par
Pr(i)=pi/M
où pi est un entier strictement positif
et M une constante entière (une puissance de 2 en pratique, et
égale à 65536 dans ce TD). Nous noterons
si=Σj<ipj.
Grandes lignes de l'algorithme de codage :
on initialise l'intervalle [a,b[=[0,M[, et un compteur k=0
pour chaque lettre i produite par la source
[a,b[ devient [a + si*(b−a)/M, a + (si+pi)*(b−a)/M[
(les arrondis sont à l'entier inférieur)
le nouvel intervalle [a,b[ est réduit (voir plus loin)
quand tous les caractères ont été lus:
si a < M/4 alors 01k+1 est ajouté à la sortie, sinon
10k+1 est ajouté à la sortie.
Reduction de l'intervalle [a,b[, tant que l'une des conditions est vérifiée
si b ≤ M/2, l'intervalle devient [2a, 2b[
01k est ajouté à la sortie, k est remis à 0
sinon si a ≥ M/2, l'intervalle devient [2a − M, 2b − M[
10k est ajouté à la sortie, k est remis à 0
sinon si M/4 ≤ a < b ≤ 3M/4, l'intervalle devient [2a − M/2,
2b − M/2[
le compteur k est incrémenté
Pour un fichier à compresser (i1,…,iL) la sortie sera
l'écriture en base 2 de
S(x1,…,xn)
tronquée "au bon endroit". Si vous suivez exactement les instructions ci-dessus, çà marche.
On vous donne un fichier Source.java qui
contient les constantes (distribution de probas), et quelques fonctions
utiles (recherche de l'intervalle de Shannon-Fano-Elias).
Écrire un codeur, on pourra utiliser le
décodeur pour tester son programme. La syntaxe du décodeur est java Decoder fichier.code
où fichier.code est le fichier codé.
Vous utilisera les mécanismes de redirection d'unix: