Le codage à longueur
variable
Introduction
Contexte : codage ou compression des
données numériques
Pourquoi : réduction de la quantité d ’éléments
binaires représentant l ’information
=> codage de source
Qté d'info. ima. originale [bit]
Taux de comp. =
Qté d'info. ima. compressée [ bit]
Finalité : archivage ou transmission
2
Codage Huffman (1952)
Le codage de Huffman est un algorithme de compression de données
sans perte. Le codage de Huffman utilise un code à longueur variable
pour représenter un symbole de la source (par exemple un caractère
dans un fichier).
Le code est déterminé à partir d'une estimation des probabilités
d'apparition des symboles de source, un code court étant associé aux
symboles de source les plus fréquents.
Il a été inventé par David Albert Huffman, et publié en 1952
3
Codage Huffman (1952)
Algorithme de génération d’un code optimal symbole par symbole
Codage à longueur variable : code long pour probabilités faibles
• Algorithme
1. Extraction des probabilités
2. Création de l’arbre
3. Création de la table de Huffman
4. Codage
On transmet la table + les codes en binaires
1. Lecture de la table de Huffman
2. Création de la table de décodage
3. Lecture séquentielle et décodage
4
Codage Huffman, Principe : (1952)
L'arbre est créé suivant un principe simple : on associe à chaque fois
les deux nœuds de plus faibles poids, pour donner un nouveau nœud
dont le poids équivaut à la somme des poids de ses fils. On réitère ce
processus jusqu'à n'en avoir plus qu'un seul nœud : la racine. On
associe ensuite par exemple le code 0 à chaque embranchement
partant vers la gauche et le code 1 vers la droite.
5
Codage Huffman : Exemple 1
supposons que tous les messages envoyés d’une source à une
destination contiennent les lettres a, b, c, d et e representées par les
probabilités .05, .2, .4, .17 et .18, respectivement.
Notre but est d’encoder chaque caractère en une sequence de 1 et 0 de
manière a ce qu’aucun code representant un caractere ne représente le
prefix d’un autre.
Example: on ne peut pas avoir les codes “110” et “1101” car “110” est
un prefix de “1101”.
6
Codage Huffman : Exemple 1
Un noeud est représenté par :
lettre
probabilite
Gauche Droite
7
Solution
1
0 1 Code
c .6
.4 a= 100
0 1 b= 111
c= 0
.22 .38 d=101
0 1 0 1 e=110
a d e b
.05 .17 .18 .2
8
Codage de Huffman : Exemple 2
9
a
1
0.40
a
b 001 0.40 racine
0.18 b 1
0.18
c 011 c 001
0.10 0.10
011 (cefbdgh)
(cef)
d 0000 d 0.60
0.23
0.10 0.10 01 0
e 0100 (bdgh)
0.07 0.37
(ef) 00
f 0101 0.1 CODE
3010
0.06 Probabilité
(dgh) du regroupement DE LA
g 0.9 BRANCHE
0.05 00010 000
(gh) Codage de Huffman
h 00011 0.09
0.04 0001
a
1
a
b 001 1
b racine
c 011 c
001 0
011
(cefbdgh)
01
d 0000 d (cef)
00(bdgh)
e 0100
010
(ef) Boucle du décodage
f 0101 début à la racine ;
000
g (dgh) progression dans
le message jusqu’à
00010 0001 une feuille :
h (gh) lettre décodée.
00011
Le code de Huffman en pratique
Apparaît pratiquement partout…
Dans les algorithmes de compression gzip, pkzip, winzip,bzip2.
Les images compressées jpeg, png.
L'audio compressée mp3.
Le code de Huffman en pratique
Limites
le codage de Huffman n'est pas adapté dans le cas d'une source
dont les propriétés statistiques évoluent au cours du temps,
puisque les probabilités des symboles se modifient et le codage
devient inadapté.
La transmission de l'arbre de codage
Chaque code est représenté par un nombre entier de bits.
Codage Arithmétique (1976)
Le codage arithmétique est un codage entropique utilisé en
compression de données sans perte. Il permet une meilleure
compression que le codage de Huffman, sauf lorsque tous les poids
pour les feuilles/nœuds/racines de l'arbre de Huffman sont des
puissances de 2, auquel cas les deux méthodes sont équivalentes
14
Codage Arithmétique (1976)
Le codage arithmétique (au même titre que le Codage de Huffman) est
un code à longueur variable, c'est-à-dire qu'un symbole de taille fixe
(en bits) sera codé par un nombre variable de bits, de préférence
inférieur ou égal à sa taille originale. On ne modifie donc pas la
densité de symboles mais leur codage afin de réduire l'espace qu'ils
occupent.
Ce qui différencie le codage arithmétique des autres codages sources
est qu'il code le message par morceaux (théoriquement il peut coder un
message entier de taille quelconque mais dans la pratique on ne peut
coder que des morceaux d'une quinzaine de symboles et représente
chacun de ces morceaux par un nombre n flottant.
15
Codage Arithmétique, Compression (1976)
La compression demande un tableau statistique qui comprend :
La totalité des s symboles que l'on rencontre dans le message à
compresser.
Les probabilités p de rencontrer le symbole s dans le message.
L'intervalle [ 0 ; 1 [ découpé en intervalles proportionnel à la
probabilité p que le symbole s apparaisse dans le message (ex: si s a
50 % de chance d'apparaître, son intervalle fera 0,5).
Le but est d'appliquer une suite d'opérations à un intervalle donné
(couramment c'est l'intervalle [ 0 ; 1 [ ) afin de modifier ses bornes à
chaque ajout d'un symbole s et de restreindre au maximum le nombre
de possibilités du nombre de sortie.
16
Codage Arithmétique, Compression (1976)
Voici les opérations à effectuer lors de l'ajout d'un symbole s :
On enregistre la différence entre la borne supérieure (BS) et la borne
inférieure (BI). On notera cette valeur BB.
La BS prend la valeur : BS=BI + BB * (BS_du_symbole_s)
La BI prend la valeur : BI=BI + BB * (BI_du_symbole_s)
17
Codage Arithmétique, Décompression (1976)
Pour décompresser un fichier (représenté par un nombre n), il faut
utiliser la même table qui a été utilisée pour la compression puis
effectuer les étapes suivantes jusqu'à la fin du fichier :
Observer dans l'intervalle de quel symbole s se trouve le nombre,
ajouter s au fichier décompressé et garder en mémoire la probabilité p
de s ainsi que sa BI.
n prend la valeur n = ( n − B I ) / p .
Une fois le marqueur de fin atteint, l'algorithme s'arrête et le fichier est
considéré comme décompressé.
18
Codage Arithmétique, Exemple (1976)
On appliquera ici l’algorithme de compression arithmétique sur le
texte "WIKI". On obtient dès lors le tableau suivant :
BS=BI + BB * (BS_du_symbole_s)
BI=BI + BB * (BI_du_symbole_s)
Par convention on initialise l'algorithme avec une borne inférieure
valant 0 et une borne supérieure valant 1. Il ne reste plus qu'à appliquer
la suite d'opérations vue précédemment à chaque ajout d'un caractère.
19
Codage Arithmétique, Exemple (1976)
Donc, tout nombre compris dans intervalle [ 0 , 1640625 ; 0 , 1796875
sera une version compressée de la chaîne de caractère "WIKI". Le
nombre 0,17 étant compris dans cet intervalle, il peut convenir pour
représenter "WIKI" compressé. À l'inverse, 0,16 ou 0,1796875 n'étant
pas dans l'intervalle, ils ne conviendront pas et entraîneront des erreurs
lors du décodage.
Codage Arithmétique, Exemple (1976)
Décompression
Supposons que l'on reçoive le message compressé 0,17, voici comment
il serait décodé : (On utilise évidemment le même tableau que
précédemment pour connaître les intervalles de chaque lettre et leurs
probabilités d'apparition). .
n=(n−BI)/p
On retrouve donc la bonne chaîne de caractères auparavant
compressée
21
