1-Problématique
2-Comment les fichiers sont enregistrés
3-Comment les fichiers sont compressés (les différentes méthodes)
4-Application
Problématiques
Souvent on est confronté au problème de manque d’espace sur les disques durs
de l’ordinateur ou sur la mémoire du téléphone. Alors il nous arrive de
compresser les fichiers en utilisant les utilitaires d’archives comme gzip ou
winzip.
Alors que ce passe t’il derrière cette manipulation que nous faisons si
commodément chaque jour ?
C’est ce que nous allons faire comprendre par notre présentation.
Comment les fichiers sont alors stockés sur l’ordinateur
Les fichiers à stocker sur l’ordinateur sont souvent d’autres divers (des images,
des chiffres, des mots………) or l’ordinateur ne comprend que les 0 1.
Alors il faut trouver un moyen de lui communiquer les données que nous voulons
enregistrer (ici nous allons étudier le cas des mots ou phrases)
On utilise alors pour cela le langage binaire pour résoudre ce problème.
On fait correspondre alors chaque lettre de l’alphabet à une série de bits
Par exemple on peut créer un alphabet
A=00
B=01
C=10
D=11
Les 01 ;00 ;10 ;11 sont appelées mots du code
Et pour coder alors le mot DADA ça nous fait alors 11OO11OO
Il est à remarquer que les mots sont de même longueur c’est-à-dire même
nombre de bits .
Comment l’ordinateur compresse-t-il alors ces fichiers
Si on veut coder par exemples un fichier avec un langage écrit avec des mots de
longueur n un fichier de x lettre alors on aura besoin de x.n bits .Le but de la
compression est de trouver un moyen pour quelles fichiers codés soient plus
courts que cela (pour que les fichiers stockés dans l’ordinateur prennent moins
de place). On va donc devoir changer de code.
Principe de la compression sans perte de données
L'idée essentielle est de ne pas coder toutes les lettres avec le même nombre de
bits : on veut profiter de ce que leE par exemple est beaucoup plus fréquent (en
français) que le K, comme tout joueur de Scrabble le sait bien. Donc si le E
pouvait
être codé sur moins de 8 bits, quitte à ce que le K soit plus long, on pourrait y
gagner.
Mais le problème est qu'on veut toujours pouvoir déchiffrer. Or on rappelle qu'on
ne peut pas mettre d'espace entre deux mots du code (car l'ordinateur ne
connaît
pas les espaces, il ne connaît que 0 et 1).
Un code non déchiffrable
Par exemple, si on décide de coder un alphabet de quatre lettres comme ceci
A →0
B →01
C →10
D →11
Comment décoder0010 ?
AAC ou ABA ?
Il y a ambiguïté, et ce code est donc un mauvais code.
Codes préfixes
Pour éviter ce problème, on fait en sorte d'utiliser des suites de 0 et de 1 telles
qu'aucune ne soit le début d'une autre. On dit que le code est préfixe. Dans le
code
précédent, 0(A) était le début de 01(B), et c'est pour cela qu'on pouvait avoir
ambiguïté.
Si on prend par exemple :
A →0
B →10
C →110
D →111
0 n'est pas le début de 10, ni de 110, ni de 111. De même, 10 n'est le début ni de
110
ni de 111. Donc quand on cherche à décoder un message, on peut lire de gauche
à
droite, et dès qu'on reconnaît un mot du code, c'est forcément lui (et pas le début
d'un autre).
Quel code choisir ?
On peut avoir plusieurs codes préfixes pour un alphabet. Suivant les fréquences
des lettres dans le texte à coder , un code pourra être plus efficace qu'un autre.
On
se doute bien que les lettres les plus fréquentes doivent être codées par un mot
plus court. Mais c'est plus compliqué que cela.
Par exemple, si on a un texte de 100 lettres avec 50 A, 30 B, 10 C et 10 D : si on
utilise le code :
A →0
B →10
C →110
D →111
on obtient un texte codé de longueur 170 bits.
Si on avait utilisé le code
A →0
B →01
C →10
D →11
le texte codé aurait eu une longueur de 200 bits : on a donc ici intérêt à utiliser le
premier code. Mais si on a un texte de 100 lettres avec 28 A, 25 B, 24 C et 23 D,
le
premier code fournit un texte codé de longueur 219 bits. Le deuxième code
aurait
fourni un texte codé de longueur toujours 200. Ici c'est donc le deuxième code
qui
est meilleur !
Il ne suffit donc pas de connaître l'ordre de fréquence des lettres... Le meilleur
code dépend donc vraiment des valeurs des fréquences dans le texte qu'on veut
compresser.
Le code optimale
Pour remedier au probleme soulevé plus tot David Huffman a publié, en 1952,
l'algorithme
qui porte son nom et qui permet, lorsqu'on connaît les fréquences des lettres
dans un fichier, de trouver l'arbre qui correspond au code préfixe qui raccourcira
le
plus le fichier.
L’algorithme de huffman
Pour mieux expliquer cet algorithme nous allons nous mettre dans le contexte de
representation d’un arbre genealogique avec les mots du codes .
Alors dans un code optimal, les deux caractères les moins fréquents seront codés
par les
mots les plus longs, et en fait par deux mots de même longueur. En effet, sinon,
le
mot le plus long a son frère inutilisé, on peut donc le remonter d'un cran (en
conservant un code préfixe).
On peut de plus aussi s'arranger pour que ces deux mots les plus longs soient
deux frères et qu'ils aient donc le même père (s'ils ne le sont pas c'est qu'il y a
d'autres mots de la même longueur, mais cela ne change rien de permuter deux
mots).
On peut alors identifier les deux lettres codées par ces deux mots, en une lettre
fictive
codée par le mot père : on obtient un nouveau texte où on a remplacé chaque
occurrence de ces deux lettres par ce nouveau caractère; on se retrouve alors à
chercher un code optimal pour ce nouveau texte, dont l'alphabet comporte un
symbole de moins, et ainsi de suite. C'est une sorte de récurrence descendante :
il
s'agit d'un principe récursif.
Exemple
Supposons par exemple que l'on veuille coder ABRACADABRA. On commence par
établir le nombre d'apparitions de tous les caractères, et par les classer dans
l'ordre
croissant. Ici on obtient :
(D ;1) (C ;1) (R ;2) (B ;2) (A ;5)
On prend les deux caractères les moins fréquents : D et C. Dans un code optimal,
d'après la première remarque, ils seront frères, et seront codés par pour et
pour où désigne une même suite de 0 et de 1 encore inconnue. On crée
alors un nouveau symbole qui remplacera tous les et tous les (et sera
codé par ); on est alors amené à chercher un code optimal pour un texte utilisant
un alphabet comportant un symbole de moins (4 au lieu de 5), avec les nombres
d'apparitions suivants :
(D ∼ C ;2) (R ;2) (B ;2) (A ;5)
où D ∼ C sera codé par la suite précédente. On recommence alors avec les
caractères les moins fréquents, qui sont maintenant par exemple et , qui seront
aussi frères dans le code qu'on cherche .
(D ∼ C ;2) (R ∼ B ;4) (A ;5)
On obtient alors :
Enfin, D ∼ C et R ∼ B seront aussi frères, et on obtient
((D ∼ C) ∼ (R ∼ B) ;6) (A ;5)
Finalement A peut être codé par 1, ((D ∼ C) ∼ (R ∼ B)) par 0, donc D ∼ C
sera codé par 00, R ∼ B par 01, et enfin D sera codé par 000,C par 001, R par
010, et par 011. Ce code est optimal, et fournit une longueur de 23 bits pour
ABRACADABRA
