TD 2, Code de Huffman
INF 563 Introduction à la théorie de l'information
13 janvier 2023 |
1 Code de Huffman
Nous allons considérer une source de 27 lettres, avec la loi de
probabilité suivante :
' ' |
0.1834 |
'i' |
0.0591 |
'r' |
0.0555 |
'a' |
0.0640 |
'j' |
0.0023 |
's' |
0.0697 |
'b' |
0.0064 |
'k' |
0.0001 |
't' |
0.0572 |
'c' |
0.0259 |
'l' |
0.0465 |
'u' |
0.0506 |
'd' |
0.0260 |
'm' |
0.0245 |
'v' |
0.0100 |
'e' |
0.1486 |
'n' |
0.0623 |
'w' |
0.0001 |
'f' |
0.0078 |
'o' |
0.0459 |
'x' |
0.0031 |
'g' |
0.0083 |
'p' |
0.0256 |
'y' |
0.0021 |
'h' |
0.0061 |
'q' |
0.0081 |
'z' |
0.0008 |
que l'on pourra trouver sous forme de classes Java :
Source.java et Source_fr.java.
1.1 Préliminaire
Quelle est l'entropie de cette source ?
1.2 Arbre de Huffman
Écrire un programme Dico.java qui construit l'arbre du code de Huffmann de cette
source (en utilisant par exemple les classes ArbreHuffman.java,Feuille.java et Noeud.java).
Le code f de Huffmann de X={a0,…,an−2,an−1} muni
de la loi (P(a0),…,P(an−1)) est défini par :
-
si n=2, f(a0) = 0 et f(a1) = 1
- sinon on suppose (sans perte de généralité) que les lettres les
moins probables sont a0 et a1, et on considère la source
Y={a2,…,an,b} de cardinal n−1 munie de la loi
|
Q(ai) |
= |
P(ai) |
i = 2 … n−1 |
Q(b) |
= |
P(a0)+P(a1) |
|
Soit g() un code de Huffmann de Y, on a
|
f(ai) |
= |
g(ai) |
i = 2 … n−1 |
f(a0) |
= |
g(b)||0 |
f(a1) |
= |
g(b)||1 |
|
On affichera la liste des mots de code et la longueur moyenne du code.
% java Dico
111
a 1010
b 0010011
c 01001
d 01110
e 110
f 0111100
g 0111110
h 0010010
...
1.3 Codeur
Écrire un programme qui prend en argument un fichier et retourne la
séquence binaire codée correspondante. On pourra utiliser par exemple
cet extrait de Candide (on codera le saut de ligne
comme un espace).
% wc -m extrait.txt
1831 extrait.txt
% java Coder extrait.txt > extrait.code
% wc -m extrait.code
7315 extrait.code
Les 1831 caractères du fichier extrait.txt sont codés par 7315
bits.
1.4 Décodeur
Écrire un programme qui prend en argument un fichier contenant des '0'
et des '1' (les autres caractères seront ignorés) et qui retourne le
texte correspondant.
% java Decoder extrait.code
il y avait en vestphalie dans le chateau de monsieur le baron de thunder ten tronckh un jeune garcon a qui la nature avait donne les moeurs les plus douces sa physionomie annoncait son ame il avait le jugement assez droit avec l esprit le plus simple c est je crois pour cette raison qu on le nommait candide les anciens domestiques de la maison soupconnaient qu il etait fils de la soeur de monsieur le baron et d un bon et honnete gentilhomme du voisinage que cette demoiselle ne voulut jamais epouser parce qu il n avait pu prouver que soixante et onze quartiers et que le reste de son arbre genealogique avait ete perdu par l injure du temps monsieur le baron etait un des plus puissants seigneurs de la vestphalie car son chateau avait une porte et des fenetres sa grande salle meme etait ornee d une tapisserie tous les chiens de ses basses cours composaient une meute dans le besoin ses palefreniers etaient ses piqueurs le vicaire du village etait son grand aumonier ils l appelaient tous monseigneur et ils riaient quand il faisait des contes madame la baronne qui pesait environ trois cent cinquante livres s attirait par la une tres grande consideration et faisait les honneurs de la maison avec une dignite qui la rendait encore plus respectable sa fille cunegonde agee de dix sept ans etait haute en couleur fraiche grasse appetissante le fils du baron paraissait en tout digne de son pere le precepteur pangloss etait l oracle de la maison et le petit candide ecoutait ses lecons avec toute la bonne foi de son age et de son caractere pangloss enseignait la metaphysico theologo cosmolonigologie il prouvait admirablement qu il n y a point d effet sans cause et que dans ce meilleur des mondes possibles le chateau de monseigneur le baron etait le plus beau des chateaux et madame la meilleure des baronnes possibles
1.5 Changement de langue
Toujours en 27 lettres, une scène de hamlet avec les
statistiques de l'anglais. Mesurez les tailles
compressées dans les quatres cas. Conclusions ?
2 Pour aller un peu plus loin
Si vous voulez aller au delà des 27 lettres, vous pouvez faire des
statistiques à partir de textes en français (par exemple
Candide, Cyrano de Bergerac ou
d'autres textes en français).
Les statistiques sont obtenues à l'aide du programme suivant :
Stat.java.
Si vous voulez mesurer ce qui est perdu par l'approximation « sans
mémoire », essayez gzip sur les mêmes fichiers.
This document was translated from LATEX by
HEVEA.