La compression de données
Change to an efficient
Change
representation,
to an efficient representation for,
Any source of information
i.e., data compression.
transmission, i.e., error control coding.
The channel is anything transmitting or storing information –
Recover
a radio link, from channel
a cable, [Link]
a disk, a CD, a piece of paper, …
Fundamental Entities
H R
C
H: The information content of the source.
R: Rate from the source coder.
C: Channel capacity.
Fundamental Theorems
H R
C
Shannon 1: Error-free transmission possible if R≥H and C≥R.
Shannon 2: Source coding and
Source coding
channel
Channel
theorem
coding can be
coding theorem
optimized independently, and binary symbols can be used as
intermediate format.
Théorie de l’information
1. Pour réduire le coût de stockage et transmettre
rapidement les données et éliminer la redondance, Il faut
utiliser
– la compression
2. Pour une transmission fiable, il faut utiliser
– les codes détecteurs/correcteurs
3. Pour une transmission confidentielle, il faut utiliser
– la cryptographie
La théorie de l’information est la science qui permet
d’étudier tous ces concepts
5
La Théorie de l’Information
• Premières tentatives de définition dans les années 1920 :
– Nyquist (Communication).
– Fisher (Statistique).
• La théorie de l'information se préoccupe des systèmes
d'information, des systèmes de communication et de leur
efficacité.
• Ce domaine trouve son origine scientifique avec Claude
Shannon (1916-2001) qui en est le père fondateur en 1948.
– Déterminer les limites imposées par les lois de la nature lorsque
l’on doit transmettre ou stocker le contenu d’une source
(l’information).
– Proposer des dispositifs permettant d’atteindre ou d’approcher
ces limites.
6
Définition de l’information
• Incertitude d’un événement ou self-information ou quantité
d’information.
• Plus de surprise, plus d’incertitude, plus d’information, plus de
«bits».
• Une information est un élément de connaissance qui peut être
conservé (mis en mémoire), traité (traitement de l’information)
ou transmis.
• La difficulté rencontrée pour définir la quantité d’information
relative à un événement est liée au caractère subjectif de
l’information effectivement apportée par la réalisation de cet
événement.
• La quantité d’information est relative à un contenu statistique,
plus grande si on ne s’attend pas à ce que l’évènement se
réalise.
7
Mesure de l’information
8
Exemples
• Un événement qui a une chance sur 2 de se
produire conduit à une quantité d’information de
-log2 (1/2) = 1 bit
• Une source peut délivrer 8 événements équiprobables :
Itotal = -8*log2 (1/8) = 24 bits
• I(E) peut être interprétée :
– à priori,
• par l'incertitude qui règne sur la réalisation de E;
– à posteriori,
• par l'information apportée par la réalisation de E.
9
Entropie
• Entropie d'une variable aléatoire discrète
• Soit X une variable aléatoire à valeurs dans {x1, x2 ,..., xn}
telle que pi = P(X = xi) pour i de 1 à n.
• L'entropie de X notée H(X) est la moyenne des
incertitudes calculée sur les événements {X = xi}
• L’entropie d’une source discrète est donc la quantité
moyenne d’information par symbole et est exprimée en
bits par symbole.
Information effet de surprise ; Entropie degré d’incertitude
10
La compression
Introduction
• Pourquoi comprimer ?
– Le problème du volume de stockage
– Difficultés de transmission sur la bande étroite du réseau
• Quelques chiffres …
– Un livre de 500 pages occupe :
• 1 Mo en texte intégral
• 4,7 Go (6 CDRoms ou 1 DVD) en mode image en niveaux de gris
• 39 heures pour télécharger l’ouvrage complet par modem à 56
Kb/s
Techniques de compression
• Objectifs
– Représenter un fichier par un nombre minimal de bits.
Permet de diminuer l’espace mémoire et réduire les temps
de transmission
• Principes
– Élimination de la redondance :
• Redondance du contenu : corrélations dans les divers espaces
de représentation; ainsi par exemple, la couleur d’un pixel
statistiquement de celle de ses voisins
• Redondance du codage : provient des codes non optimaux
• Approximations :
– Conserver les informations pertinentes
– Éliminer celles peu ou pas informatives. Les critères
d’élimination dépendent des applications
Concepts de base
• Compression
– Procédé qui consiste à remplacer une série de données
par une autre de taille plus réduite ou à supprimer
certaines jugées non utiles
• Décompression
– Opération inverse de la compression
• Tout algorithme de compression est réfléchi avec son
inverse
– Consiste à retrouver les données originales à partir de
données comprimées
Types de compression
• Réversibles (conservatrices)
– Conservent toute l’information se trouvant dans la source
• Celle-ci peut être reconstituée de manière exacte à partir de
la forme comprimée
• Non réversibles (non conservatrices)
– Éliminent une partie de l’information jugée non significative
pour l’application
• La source ne peut être reconstituée que de manière
approximative
Notions de taux et de perte
Notions de taux et de perte
• Taux de compression : soit un objet de 1600 octets (une
image par exemple)
Compression minimale 1% Compression maximale 99%
(taille 1559 octets) (371 octets)
Modifications invisibles à l‘œil Modifications visibles à l‘œil
• Compression avec perte
– Compression de 10% ≠ perte de 10% des informations
– La perte n'est pas linéaire, dépend des données de chaque
image par exemple
– L'échelle de compression n'est pas forcément la même
selon les logiciels ⇒ taux de compression difficilement
comparables
Les méthodes
• Méthodes physiques
Méthodes à base Méthodes statistiques Méthodes à base
de redondance de dictionnaire
- Suppression des - HUFFMAN statique - L.Z.W
blancs
ou dynamique - A.F.E
- Représentation
topographique binaire - FANO-SHANNON - EUHOLA-RAITA
- R.L.C
• Méthodes logiques
– Compression morphologique
Compression à base de
redondance
Méthodes à base de redondance
RLE (Run Length Encoding) ou RLC
•Principe : remplacer une suite de caractères identiques par un
couple (nombre de répétitions, caractère).
•Utilisation : image en noir et blanc, fax, BMP jusqu'à 8 bits
•Fort taux de compression pour des images possédant de nb.
zones de régions homogènes
RLE (Run Length Encoding) ou RLC
– Pour les textes, le RLC impose le choix d'un
caractère de contrôle ce qui est gênant lors du
compactage de fichiers exécutables, où tous les
codes ascii sont utilisés.
– Il donne cependant de très bonnes performances
pour les fichiers très redondants et est notamment
utilisé pour le compactage des images.
Technique de bit-map
• Il est facile de laisser tomber des champs entiers d’un
enregistrement. Prenons un enregistrement de 4
champs de 8 caractères (32 caractères) pour les noms
alors que la longueur moyenne est bien plus courte. On
utilise alors la technique du bit-mapping
• Principe: Utiliser une bit-map devant chaque
enregistrement pour indiquer la présence ou l’absence
de valeur dans les différents champs.
Compression Statistique
• Source: Ensemble de mots S. Le plus souvent les mots
sont des char (8 bits).
• Table de fréquences: Table qui associe à tout mot de la
source son nombre d’occurrences dans la source. Le
nombre d’occurrences f (x) peut être remplacé par la
probabilité d’occurrence:
p(x) = f (x)/|S|
• Définition: Trouver un codage préfixe de la source qui
tienne compte de la probabilité d’occurrence de chaque
mot.
• Exemple:
– Source: abracadabra
– (mot, poids, code)=(a 5 0 ; b 2 10; c 1 100 ; d 1 101; r 2 111)
Code Préfixe :
• Définition:
– Le codage d’un ensemble de mots S
est appelé code préfixe si aucun
code d’un mot de S n’est le préfixe du
code d’un autre mot de S.
• Arbre de codage
– Un arbre de codage pour un
ensemble de mots S est un arbre
binaire vérifiant les propriétés
suivantes:
• chaque branche est étiquetée par 0 ou
par 1,
• chaque feuille est étiquetée par un mot
de S,
• le code correspondant à une feuille de
S est le chemin parcouru depuis la
racine jusqu’à la feuille.
Compression de Huffman
• Principe
– L’algorithme part d’une forêt composée des mots de la
source et regroupe les racines deux à deux jusqu’à obtenir
un arbre de codage
• Règle
– durant chaque étape l’algorithme regroupe les deux arbres
dont le poids est minimal.
• Codage
– Le codage préfixe est obtenu en numérotant chaque paire
de branches par 0 et 1.
Compression de Huffman: Exemple
Lettre fréquence
A 4
C 3
BACFGABDDACEACG B 2
D 2
G 2
E 1
F 1
Compression de Huffman: Exemple
A C B D G E F
4 3 2 2 2 1 1
0 1
0 Lettre Codage
1
0 A 00
0 2
4 C 10
1 B 010
8 1 D 011
4
0
G 110
1 E 1110
0
7 F 1111
1
15
Compression de Huffman: Exemple
• Calcul du gain de compression
• Les codes émis par Huffman :
– 00 100 010 1010 1011 0110
0111 11000 11001 11010
11011 11100 11101 11110
11111
• Taille de la chaîne après
codage :
– (1*2)+(2*3)+(4*4)+(8*5) = 64
bits
• Taux de compression:
– 64/(28*8) = 0.285 = 28,5%
• Gain de compression:
– 1-0.28 = 0.72 = 72%
Compression de Huffman: Propriétés
• Propriété 1
– L’algorithme de Huffman construit un codage préfixe
• Propriété 2
– Dans un arbre de Huffman, les deux mots les moins
fréquents sont regroupés par le même nœud
• Théorème
– L’algorithme de Huffman construit un arbre de codage
optimal
Compression de Shannon-Fano
• Principe
– L’algorithme dichotomise récursivement la table de fréquences
• Algorithme
1. Construire une table des fréquences d’apparition des symboles
triée par ordre décroissant.
2. Diviser cette table en deux parties. Celles-ci doivent avoir une
somme de fréquences égale (ou pratiquement égale) à celle de
l’autre.
3. Affecter le chiffre binaire 0 à la moitié inférieure, la moitié
supérieure prenant la valeur 1.
4. Répéter les opérations 2 et 3 aux deux parties, jusqu’à ce que
chaque symbole ne représente plus qu’une partie de la table.
Compression de Shannon-Fano: Exemple
Prob État
final
1 0.25 1 1 11
2 0.20 1 0 10
3 0.15 0 1 1 011
4 0.15 0 1 0 010
5 0.10 0 0 1 001
6 0.10 0 0 0 1 0001
7 0.05 0 0 0 0 0000
Compression de Shannon-Fano: Propriétés
• Propriété 1
– L’algorithme de Shannon-Fano construit un codage préfixe
• Propriété 2
– L’arbre de Shannon-Faro n’est pas toujours optimal
Compression Statistique: Conclusion
• Le codage de HUFFMAN est efficace quand il y a un petit
nombre de types de messages dont quelques-uns
couvrent une proportion importante du texte
• Quand le nombre de types de messages augmente et que
les fréquences sont plus uniformes, le gain est
négligeable.
• Une autre façon de procéder :
– parcourir le texte et remplacer les séquences redondantes
par des séquences plus courtes (RLE)
– analyser préalablement le texte pour déterminer les groupes
à remplacer et les codes qui les remplacent (LZW)
Codage arithmétique
• Les algorithmes de Shannon-Fano ou de Huffman ont
des limitations même dans leur domaine de prédilection.
Ils fournissent un nombre entier de bits quand la valeur
optimale de longueur de code prévue par la théorie peut
être réelle.
• Dans les formats de compression classiques, les
codages arithmétiques remplacent de plus en plus le
codage de Huffman. L’idée générale consiste à
représenter l’ensemble de la source sous la forme d’un
seul nombre réel.
Codage arithmétique: algorithme
• Comme dans l’algorithme de Huffman, on commence par
considérer les probabilités des symboles.
• A chaque symbole, est alors associé un sous-intervalle de
[0,1[ de longueur égale à la probabilité pi du symbole i.
• Les intervalles sont construits de la manière suivante :
– I0 = [0,p0[,
– I1 = [p0,p0+p1[,
– …
• Le codage consiste à générer la suite d’intervalles emboîtés
convergeant vers un réel R de ]0,1[ qui codera la source
complète.
• le réel codant la séquence sera le début du dernier sous-
intervalle
Codage arithmétique: algorithme
• L'algorithme servant à encoder est le suivant:
// Tableau contenant les bornes inferieures des intervalles
// calcules ci-avant
Borne_Inf[];
// Idem pour la borne sup
Borne_Sup[];
// Initialisation
Inf=0.0;
Sup=1.0;
c = lireCaractere();
TantQue (c!= EOF) {
Sup = Inf + (Sup - Inf) * Borne_Sup[c];
Inf = Inf + (Sup - Inf) * Borne_Inf[c];
c = lireCaractere();
}
Codage arithmétique: Exemple
Codage arithmétique: décodage
• On doit connaître la table des symboles et leurs plages (début du
fichier)
S [0.5 1[ W [0.4 0.5[ I [0.2 0.4[ M [0.1 0.2[ _
[0.0 0.1[
• Soit à décoder 71753375
1. le code est dans l’intervalle [0.5 1[ donc premier symbole S
2. déterminer le nouveau code: (0.71753375-0.5)/0.5=0.4350675
new_code = (code - Low(S)) / range(S)
3. le code est dans l’intervalle [0.4 0.5[ donc second symbole W
4. nouveau code (0.4350675-0.4)/0.1=0.350675
5. I, nouveau code (0.350675-0.2)/0.2=0.753375
6. S, code (0.753375-0.5)/0.5=0.50675
7. S, code (0.50675-0.5)/0.5=0.0135
8. _, code (0.0135-0.0)/0.1=0.135
9. M, code (0.135-0.1)/0.1=0.35
10. Symbole I, code (0.35-0.2)/0.2=0.75
11. Symbole S, code (0.75-0.5)/0.5=0.5
12. Symbole S, code 0
