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 :
  1. si n=2, f(a0) = 0 et f(a1) = 1
  2. 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.