TD 2, Huffman Code
INF 563 Introduction to Information Theory
January 13, 2023 |
1 Huffman Code
Consider a source with 27 letters specified by the
following probability distribution.
| ' ' |
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 |
which is implemented in the following Java classes :
Source.java and Source_fr.java.
1.1 Preliminaries
Compute the entropy of this source.
1.2 Huffman Tree
Write a program
Dico.java that builds the Huffman tree of this source by using for instance the java classes
ArbreHuffman.java,Feuille.java and Noeud.java.
The Huffmann code f of the source X={a0,…,an−2,an−1}
with the probability distribution (P(a0),…,P(an−1)) is defined by :
-
when n=2, f(a0) = 0 and f(a1) = 1
- otherwise it is assumed without loss of generality that the least likely letters
are given by a0 and a1, and a new source is considered
Y={a2,…,an,b} of cardinality n−1 with probability distribution
|
|
| Q(ai) |
= |
P(ai) |
i = 2 … n−1 |
| Q(b) |
= |
P(a0)+P(a1) |
|
|
|
| f(ai) |
= |
g(ai) |
i = 2 … n−1 |
| f(a0) |
= |
g(b)||0 |
| f(a1) |
= |
g(b)||1 |
|
Print the list of codewords and the average code length.
You should obtain something like
% java Dico
111
a 1010
b 0010011
c 01001
d 01110
e 110
f 0111100
g 0111110
h 0010010
...
1.3 Encoder
Write a program which takes a file as argument and which returns the corresponding binary sequence
which encodes the file with the Huffman code. The input file can be chosen to be
an excerpt of Candide (the line feeds will be viewed as space
characters).
% wc -m extrait.txt
1831 extrait.txt
% java Coder extrait.txt > extrait.code
% wc -m extrait.code
7315 extrait.code
The 1831 characters of the file extrait.txt are encoded by 7315
bits.
1.4 Decoder
Write a program which takes as argument a file containing only '0''s and '1's
and which outputs the corresponding text file.
% 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 Switching to English
Still with 27 letters, a scene taken from Hamlet together with
statistics for the English language. Measure the compressed sizes in all these cases. Conclusions ?
2 and beyond...
To go beyond sources with 27 letters, you can compute statistics for French texts, for
instance
Candide, Cyrano de Bergerac or
other French texts.
The statistics are obtained through the following program:
Stat.java.
If you want to measure what is lost by the « memoryless » approximation, try gzip on the same files.
This document was translated from LATEX by
HEVEA.