12.1 Introduction
381
avaient une repr´ esentation de huit bits. Par exemple, un texte dans une langue o` u
les probabilit´ es des lettres sont diff´ erentes pourrait bien ne pas ˆ etre comprim´ e par cet
algorithme. (Les lettres les plus probables en anglais sont, dans l’ordre, , e, t, a, o, i,
n,. . .) Le succ` es de cet algorithme ´ el´ ementaire de compression d´ epend donc des fichiers
` a comprimer. L’id´ ee d’accorder aux lettres de l’alphabet un encodage de longueur reli´ ee
` a leur fr´ equence est la base du code de Huffman.
lettre fr´ equence
e
0,164
a
0,089
s
0,074
t
0,074
i
0,074
n
0,070
r
0,066
u
0,065
o
0,057
lettre fr´ equence
l
0,051
d
0,037
m
0,033
c
0,031
p
0,025
v
0,020
q
0,013
h
0,011
f
0,0097
lettre fr´ equence
g
0,0096
b
0,0081
j
0,0064
x
0,0038
z
0,0035
y
0,0030
k
0,0003
w
0,0002
Tab. 12.1. Fr´ equence des lettres de l’alphabet dans Les trois mousquetaires d’Alexandre Dumas. (Les espaces et les signes de ponctuation ont ´ et´ e ignor´ es ; les lettres accentu´ ees et les
majuscules ont ´ et´ e identifi´ ees ` a la minuscule sans accent correspondante. Ce roman contient
un peu plus de un million de lettres.)
Notre second exemple se rapproche du sujet de ce chapitre. Tous les ´ ecrans d’ordinateur ont une r´ esolution finie. Pour la plupart d’entre eux, celle-ci est mesur´ ee en
nombre de points lumineux qu’ils peuvent afficher. Chacun de ces points (appel´ es pixels
pour picture elements) peut ˆ etre allum´ e en toutes les couleurs du spectre
1 avec une
intensit´ e variable. Les premiers ´ ecrans pouvaient afficher 640 × 480 = 307 200 pixels
2 .
(Le nombre de pixels est donn´ e sous la forme « nombre de pixels par ligne horizontale × nombre de lignes ».) Supposons que le Louvre d´ esire num´ eriser sa collection.
Le mus´ ee voudra sˆ urement obtenir des reproductions num´ eriques dont les experts du
domaine de l’art pourront ˆ etre satisfaits. Cependant, si le mus´ ee d´ esire aussi produire
des versions pour transmission par Internet et visualisation sur un ´ ecran d’ordinateur,
1 Ceci n’est pas strictement exact. Les ordinateurs divisent aussi l’arc-en-ciel des couleurs
en petites fenˆ etres ` a peu pr` es ´ egales ; ceci permet de reproduire le spectre des couleurs par un
nombre grand, mais fini de couleurs.
2 Maintenant, il est standard d’avoir des ´ ecrans d’ordinateur donc le nombre de pixels est
de l’ordre du million. Les tr` es grands ´ ecrans d´ epassent mˆ eme quatre millions de pixels.
381
avaient une repr´ esentation de huit bits. Par exemple, un texte dans une langue o` u
les probabilit´ es des lettres sont diff´ erentes pourrait bien ne pas ˆ etre comprim´ e par cet
algorithme. (Les lettres les plus probables en anglais sont, dans l’ordre, , e, t, a, o, i,
n,. . .) Le succ` es de cet algorithme ´ el´ ementaire de compression d´ epend donc des fichiers
` a comprimer. L’id´ ee d’accorder aux lettres de l’alphabet un encodage de longueur reli´ ee
` a leur fr´ equence est la base du code de Huffman.
lettre fr´ equence
e
0,164
a
0,089
s
0,074
t
0,074
i
0,074
n
0,070
r
0,066
u
0,065
o
0,057
lettre fr´ equence
l
0,051
d
0,037
m
0,033
c
0,031
p
0,025
v
0,020
q
0,013
h
0,011
f
0,0097
lettre fr´ equence
g
0,0096
b
0,0081
j
0,0064
x
0,0038
z
0,0035
y
0,0030
k
0,0003
w
0,0002
Tab. 12.1. Fr´ equence des lettres de l’alphabet dans Les trois mousquetaires d’Alexandre Dumas. (Les espaces et les signes de ponctuation ont ´ et´ e ignor´ es ; les lettres accentu´ ees et les
majuscules ont ´ et´ e identifi´ ees ` a la minuscule sans accent correspondante. Ce roman contient
un peu plus de un million de lettres.)
Notre second exemple se rapproche du sujet de ce chapitre. Tous les ´ ecrans d’ordinateur ont une r´ esolution finie. Pour la plupart d’entre eux, celle-ci est mesur´ ee en
nombre de points lumineux qu’ils peuvent afficher. Chacun de ces points (appel´ es pixels
pour picture elements) peut ˆ etre allum´ e en toutes les couleurs du spectre
1 avec une
intensit´ e variable. Les premiers ´ ecrans pouvaient afficher 640 × 480 = 307 200 pixels
2 .
(Le nombre de pixels est donn´ e sous la forme « nombre de pixels par ligne horizontale × nombre de lignes ».) Supposons que le Louvre d´ esire num´ eriser sa collection.
Le mus´ ee voudra sˆ urement obtenir des reproductions num´ eriques dont les experts du
domaine de l’art pourront ˆ etre satisfaits. Cependant, si le mus´ ee d´ esire aussi produire
des versions pour transmission par Internet et visualisation sur un ´ ecran d’ordinateur,
1 Ceci n’est pas strictement exact. Les ordinateurs divisent aussi l’arc-en-ciel des couleurs
en petites fenˆ etres ` a peu pr` es ´ egales ; ceci permet de reproduire le spectre des couleurs par un
nombre grand, mais fini de couleurs.
2 Maintenant, il est standard d’avoir des ´ ecrans d’ordinateur donc le nombre de pixels est
de l’ordre du million. Les tr` es grands ´ ecrans d´ epassent mˆ eme quatre millions de pixels.