Cours Algorithmique, 2ème partie AS IUT
Codage de Huffman
Anne Vilnat
http://www.limsi.fr/Individu/anne/coursAlgo
Codages de caractères
Codage binaire de caractères
longueur fixe
longueur variable
Exemple
soit à coder a, b, c, d, e, f (six symboles)
longueur fixe → 3 bits
par exemple
a b c d e r
000 001 010 011 100 101
Avantages et ...
Exemple : un texte utilisant les six caractères
Total : 100 000 caractères
Codage fixe : 300 kbits
Avantage : pas d’ambiguı̈té
000001101000010000011000001101000
avec :
a b c d e r
000 001 010 011 100 101
abracadabra
... inconvénients
Remarques
Les caractères n’ont pas tous la même fréquence :
a b c d e r
45 13 12 16 9 5
les caractères fréquents occupent beaucoup de place...
Idée : codage de longueur variable : peu de bits pour les
fréquents, plus pour ceux qui le sont moins
Autre solution...
Codage de longueur variable
avec :
a b c d e r
0 101 100 111 1101 1100
abracadabra
0101110001000111010111000
Sur le fichier de départ, au lieu de 300kB, 224kB
Mais des règles à respecter!
Comment isoler les lettres?
Exemple : l’alphabet Morse
a d e i s u
.- -.. . .. ... ..-
Que veut dire : ..-....- ?
..-....-, soit idea
ou : ..-...., soit usa
Ajouter des séparateurs? Pas efficace pour compresser!
Rendre inutile les séparateurs : Condition de Fano
Code “préfixe” : aucun mot de code n’est préfixe d’un autre
mot du code
Avantage : codage et décodage simples
Exemple de codage et représentation du problème
avec le code de longueur fixe
a b c d e r
000 001 010 011 100 101
que l’on peut voir ainsi :
Exemple de codage et représentation du problème
ou mieux avec un code de longueur variable
a b c d e r
0 101 100 111 1101 1100
que l’on peut voir ainsi :
Codage de Huffman : définition
Définition
Un algorithme glouton
qui construit un codage préfixe optimal
en construisant l’arbre bianire de façon ascendante
en utilisant une file de priorité, pour trouver l’élément le moins
fréquent
Algorithme de Huffman
Données
Ensemble C des caractères avec leur fréquence
File de priorité F d’arbres binaires (vide)
Algo
F ←C
Pour i ← 1 à cardinal(C ) − 1 faire
z : nouvel arbre
x ← F .extraireMin(); fg (z) ← x
y ← F .extraireMin(); fd(z) ← y
freq(z) ← freq(x) + freq(y )
F .inserer (z)
finPour
retourner (F.extraireMin())
Exemple : Initialisation
Exemple : Etape 1
Exemple : Etape 2
Exemple : Etape 3
Exemple : Etape 4
Exemple : Etape 5
Et le codage...
Conclusion
Bilan
Méthode simple
Mais qui exige de connaı̂tre les fréquences à l’avance
Autre solution : codage de Huffman adaptatif ou dynamique
ou ... autres méthodes de compression!
