04/02/2020

Codage et Compression
(codage de source)
Badreddine Rejeb, ISITCom

Introduction
• Notion de code au sens large :
Règle permettant de convertir une information
sous une forme différente de sa représentation
initiale
• Plusieurs grandes familles de codes :
⁻ les codes de communication (Morse, Baudot,...)
⁻ les codes de représentation (ASCII, UTF, Base64,…)
⁻ les codes de protection (Cryptographie ,…)
⁻ les codes de compression (“Théorie du codage”)
⁻ les codes d’identification (IBAN, EAN, Code-barres,...)

B. rejeb, ISITCom 2

1
 04/02/2020

Codes d’identification
 Code EAN-13 (European Article Numbering) :
Soit le code 764-915481257-7, vérification :

a) On calcule la somme des 12 premiers chiffres du code

après calcul des produits de chacun d’eux alternativement
avec 1 et 3

7*1+6*3+4*1+9*3+1*1+5*3+4*1+8*3+1*1+2*3+5*1+7*3=133

b) On détermine alors le modulo 10 de l’opposé du résultat

de cette somme :
(-133) mod 10 = 7,
ce qui correspond au check digit fourni.
B. rejeb, ISITCom 3

Codes d’identification
 Code IBAN (International Bank Acount number)
Soit le code BE-43-068999999501, vérification :
a) On pratique dans un premier temps une rotation
circulaire de 4 caractères vers la gauche :
068999999501BE43
a) On convertit ensuite les lettres de la façon
suivante : A=10, B=11,. . .Z=35
068999999501111443
a) On calcule enfin le modulo 97 de ce nombre. S’il
est égal à 1, le check digit est valide :
068999999501111443 mod 97 = 1.
B. rejeb, ISITCom 4

2
 04/02/2020

Les tables de caractères

Code ASCII (American Standard Code for Information Interchange, 1961)
• ASCII de base : 7 bits de données et 1 bit de parité
• ASCII étendu (Extended ASCII ) : sur 8 bits,
plusieurs variantes
(OEM 1.2 , ANSI 1.3)

Table code ASCII de base

B. rejeb, ISITCom 5

Les tables de caractères

EBCDIC (Extended Binary Coded Decimal Interchange Code)
créé par IBM
codage des caractères sur 8 bits

Table EBCDIC
B. rejeb, ISITCom 6

3
 04/02/2020

Les tables de caractères

ISO 8859-1 / -15 (nommé Latin 1)
– Norme de l’International Organization for Standardization
– se compose de 191 caractères codés sur un octet.
– recouvre les caractères les plus utilisés dans les langues européennes
et dans une partie des langues africaines

B. rejeb, ISITCom 7

Les tables de caractères

ISO 8859-15
⁻ Ajout du caractère € et guillemets anglais
⁻ 218 caractères imprimables

Différence entre ISO 8859-1 et ISO 8859-15

B. rejeb, ISITCom 8

4
 04/02/2020

Les tables de caractères

Unicode (en 1987):
• Un code universel sur 16 bits ou 32 bits, permettant
donc 216 ou 232 codes différents
• L’espace des codes s’étend de 0 à 0x10FFFF
• code ASCII + jeux complets de caractères coréens,
japonais, chinois, les symboles mathématiques et les
écritures anciennes
• Plusieurs formats d’encodage sont possibles UTF :
(Universal Transformation Format) :
⁻ UTF-8 : 8 bits
⁻ UTF-16 : 16 bits
⁻ UTF-32 : 32 bits

B. rejeb, ISITCom 9

Unicode UTF-8
UTF-8 : sur mots de 8 bits
• se présentent comme un octet ou une suite
d’octets. (maximum 4 octets au total)
• Lorsque le caractère se situe dans la plage
0x00 à 0x7F, il s’agit du code ASCII.
• Si non, un premier octet « lead byte » suivi
d’un nombre variable d’octets « trailing byte »
représentent la valeur à encoder.

B. rejeb, ISITCom 10

5
 04/02/2020

Unicode UTF-8
• Bit de poids fort du « lead byte » toujours à 1,
et suivi d’autant de bit à 1 que de «trailing
byte».
Format du premier octet Nombre d’octets au total
110 . . . . . 2
1110 . . . . 3

11110 . . . 4

• Les bits remplacés par ’ . ’ dans le tableau ci-

dessus représente les bits disponibles pour la
valeur Unicode à encoder.

B. rejeb, ISITCom 11

Les tables de caractères : Unicode

• Toutefois, chaque « railing byte» doit avoir ses deux
premiers bits à 10. Chaque «trailing byte» possédera 6 bits
d’information.
Formats possibles Nombres de bits d’encodage
110..... 10...... 8 à 11 bits disponibles
1110.... 10...... 10...... 12 à 16 bits disponibles

11110... 10...... 10...... 10...... 17 à 21 bits disponibles

• 21 bits est suffisants pour Unicode.
• Par cette méthode d’encodage, un même caractère peut
avoir plusieurs représentations.
• Par exemple, le caractère ’/’ peut s’écrire :
0x2F, 0xC0 0xAF, 0xE0 0x80 0xAF ou 0xF0 0x80 0x80 0xAF

B. rejeb, ISITCom 12

6
 04/02/2020

Unicode UTF-16
UTF-16 : sur mots de 16 bits
• Sous la forme de mots de 16 bits,
⁻ Si U < 0x10000, U est encodé comme un entier non signé sur 16
bits
⁻ Si non, Soit U’ = U - 0x10000.
U ≤ 0x10FFFF (plage de validité de Unicode),
U’ ≤ 0xFFFFF donc 20 bits sont donc nécessaires
⁻ Initialiser 2 entiers non signés de 16 bits, W1 et W2, aux valeurs
0xD800 et 0xDC00
Chaque entier possédera 10 bits libres, total 20 bits
⁻ Associer les 10 bits de poids forts de U’ aux bits libres de W1, et
les 10 bits de poids faibles de U’ à W2
• Une seule manière de représenter les données
mais 216 < 0x10FFFF, donc insuffisant

B. rejeb, ISITCom 13

Unicode UTF-32
• UTF-32 : sur mots de 32 bits
• Les code points sont ici représentés par une
valeur sur 32 bits ( 232 valeurs).
• Cette taille est suffisante pour représenter
tous les code points Unicode existants.

B. rejeb, ISITCom 14

7
 04/02/2020

Les tables de caractères

Code Base64
• Utilisé pour la transmission de messages
• Utilise un alphabet de 64 caractères
• En entrée par groupe de 24 bits (3 octets)
• En sortie un bloc de 4 caractères (4*6 bits)
• Chaque groupe de 6 bits sert d’index dans
l’alphabet Base64

B. rejeb, ISITCom 15

Code Base64
• Si la séquence d’entrée inferieur à 24 bits
⁻ l’entrée fournit 8 bits (1 octet) : le bloc de 4
caractères en sortie sera composé de 2
⁻ caractères de la table base64 suivis de 2
caractères finaux (‘=‘ c’est-à-dire le 65ème
caractère).
⁻ l’entrée fournit 16 bits (2 octets) : le bloc de 4
caractères en sortie sera composé de 3caractères
de la table base64 suivis de 1 caractère final

B. rejeb, ISITCom 16

8
 04/02/2020

Code Base64

Table Base64

B. rejeb, ISITCom 17

Code Base64
Exemple :
• Le mot “oui” est traduit sous forme binaire en :
’01101111 01110101 01101001’.
• On découpe ces 24 bits en blocs de 6 bits, il vient :
’011011 110111 010101 101001’.
• Sous forme décimale, on obtient ’27 55 21 41’, et en
substituant, il vient ’b3Vp’.
• Lorsqu’on utilise cet encodage dans le logiciel de
chiffrement de messages PGP, le résultat est ensuite
encodé au format ASCII.
• Ainsi, si on met le bit de parité à 0, la correspondance
de ’b3Vp’ est :
• ’01100010 00110011 01010110 01110000’.
B. rejeb, ISITCom 18

9
 04/02/2020

Codage de source
Définition
Le codage de source vise à représenter
l’information à transmettre sous la forme
numérique la plus compacte possible.
Il s’agit donc de :
• numériser si elles sont analogique ,
• comprimer les données numériques, de
manière à réduire le débit de transmission ou
le volume de stockage

B. rejeb, ISITCom 19

Codage de source

Chaine de communication avec codage et décodage de source

B. rejeb, ISITCom 20

10
 04/02/2020

Codage de Canal
Définition
Le codage de canal consiste à ajouter aux
message binaire des bits de redondance, de
telle sorte que le message codé ait une
structure particulière.
En réception, le décodeur de canal vérifie si
cette structure est bien respectée

B. rejeb, ISITCom 21

Codage de Canal

Place du codage de canal dans une chaine de communication

B. rejeb, ISITCom 22

11
 04/02/2020

Théorie de l’information
• La théorie de l’information donne le cadre
mathématique aux codes compresseurs.
• Un alphabet est un ensemble fini qui sert à
former les messages
Exemple :
⁻ L’alphabet latin pour les textes
⁻ L’alphabet pour transmettre les messages
⁻ C = {0, 10, 110} est un code binaire de
cardinal 2, sur l’alphabet V = {0,1}
B. rejeb, ISITCom 23

Source et codage de source

Source discrète sans mémoire
La sortie d’une sources discrètes sans mémoire
est une séquence de lettres tirées dans un
alphabet fini {a1, . . . , aK}.
Chaque lettre de la séquence est statistiquement
indépendante des autre et obtenue d'après une
loi de probabilité fixe P(a1), . . . , P(aK).
Pour toute lettre ak, 1 ≤ k ≤ K, de la source, P(aK)
est la probabilité pour que cette lettre soit
produite, nous aurons donc

B. rejeb, ISITCom 24

12
 04/02/2020

Source et codage de source

• Question:
Pourquoi modéliser une source d'information à
l'aide d'un processus aléatoire?
• Réponse :
Soit l’exemple d’une source d'information qui
fournit comme information l'une des quatre
lettres a1, a2, a3 et a4. Supposons que le codage
transforme cette information en symboles
binaires.
Dans la Table suivante, nous donnons deux
codages différents de cette source.

B. rejeb, ISITCom 25

Source et codage de source

• 1ère méthode, deux symboles binaires sont générés

pour chaque lettre émise,
• 2ème le nombre de symboles est variable.
• Si les quatre lettres sont équiprobables :
⁻ 1ère méthode est la meilleure : 2 symboles par
lettre en moyenne
⁻ 2ème 2,25 symboles.

B. rejeb, ISITCom 26

13
 04/02/2020

Source et codage de source

• Pour une probabilité d’apparition

• 1ère méthode nécessite toujours 2 symboles

binaires par lettre en moyenne alors que la
• 2ème méthode n'en nécessite que 1,75
Donc, pour coder correctement une source
il faut connaître son comportement statistique

B. rejeb, ISITCom 27

Quantité d’Information et Entropie

• L'information propre de x doit être une fonction
de sa probabilité : I(x) = f(p(x))
• L'information de x est une fonction décroissante
de p(x) : en effet un évènement certain n'apporte
aucune information, alors qu'un évènement
improbable en apportera beaucoup
• Si les évènements x et y sont statistiquement
indépendants l'information est une grandeur
additive :
f(p(x, y)) = f(p(x)p(y)) = f(p(x)) + f(p(y)).

B. rejeb, ISITCom 28

14
 04/02/2020

Quantité d’Information et Entropie

• donc choisir une fonction de la forme
I(x) = α log (p(x))
α < 0 pour assurer la décroissance par rapport à p(x)
• si X est un espace probabilisé dans l'espace des
épreuves {0, 1} , binaire, muni d'une loi uniforme
(i.e. p(0) = p(1) = 1/2), alors la quantité d'information
fournie par la réalisation de l'événement :
X = 0 (ou X = 1) est de 1 bit.
On a I(0) = α log p(0) = − α log(2) = 1,
donc α = −1/ log(2) ce qui revient à choisir le
logarithme en base 2 pour la définition de I(x) :
I(x) = −log2 (p(x)) et l’unité est donc le bit
B. rejeb, ISITCom 29

Quantité d’Information et Entropie

Exemple :
• Soit une source dont l'alphabet de sortie
{a0, . . . , a15} comprend 16 lettres équiprobables,
pour tout k, 0 < k < 16, P(ak) = 1/16.
• L'information propre de l'une de ces sorties ak :
I(ak) = −log2(1/16) = 4 bits.
• Dans ce cas, l'information va consister à choisir
un entier k dans {0,1,. . . ,15}, et pour représenter
cette information il faut disposer de 4 bits.

B. rejeb, ISITCom 30

15
 04/02/2020

Quantité d’Information et Entropie

• Si les lettres de la source ne sont pas
équiprobables alors l'information de
l'événement ak :
I(ak) = −log2 p(ak) est différente de 4 bits
• La quantité d’information moyenne peut
être inférieure strictement à 4 bits.

Donc, Compression de données

B. rejeb, ISITCom 31

Quantité d’Information et Entropie

Définitions
1. Information propre (Quantité d’Information)
L'information propre d’un événement x définie par
I(x) = −log2 (p(x))
L'information propre s'interprète comme la
quantité d'information fournie par la réalisation d'un
événement .
Notons que : l'information propre est toujours positive ou nulle, et
que plus un événement est improbable, plus son information
propre est grande.
À l'inverse, lorsque p(x) = 1, on a I(x) = 0, c'est-à-dire que la
réalisation d'un événement certain n'apporte aucune information,
ce qui semble.

B. rejeb, ISITCom 32

16
 04/02/2020

Quantité d’Information et Entropie

2. Entropie
L'entropie d'un espace probabilisé X est
défini par :

L’Entropie définit la
quantité d’Information mutuelle moyenne

B. rejeb, ISITCom 33

Quantité d’Information et Entropie

3. Longueur moyenne d’un code
Soit un codage des messages à partir d’un
alphabet de d caractères, tel qu’il existe une
correspondance non ambiguë entre chaque
message et son code alors,
La longueur moyenne d’un code est :

B. rejeb, ISITCom 34

17
 04/02/2020

Quantité d’Information et Entropie

Théorème de Shannon
Soit une source S sans mémoire d’entropie H.
Tout code uniquement déchiffrable (décodage
unique) de S sur un alphabet V de taille d, de
longueur moyenne L, vérifie :
L ≥ H / log2(d)
De plus, il existe un code uniquement
déchiffrable de S sur un alphabet V de taille d,
de longueur moyenne L qui vérifie :
L < (H / log2(d)) +1
B. rejeb, ISITCom 35

Quantité d’Information et Entropie

 Indépendance des messages
Soit un ensemble C de messages égal au
produit de 2 ensembles A et B indépendants.
Alors : H(C) = H(A) + H(B)

En effet :

B. rejeb, ISITCom 36

18
 04/02/2020

Quantité d’Information et Entropie

 Efficacité d’un système de codage
• D’après le théorème du codage de Shannon,
L ≥ H / log2(d)
Donc, soit E = H / (L*log2(d)) ≤ 1

Ce qui définit l’efficacité E d’un système

de codage.
• La redondance R est : R = 1 − E

B. rejeb, ISITCom 37

Quantité d’Information et Entropie

Théorème : Propriétés de l'entropie
Soit X un espace probabilisé discret de
cardinal K (nombre des mots de codes représentés en binaire).
Alors son entropie H(X) vérifie
H(X) ≤ log2 (K)
avec égalité si et seulement si la loi de
probabilité de X est uniforme.

B. rejeb, ISITCom 38

19
 04/02/2020

Codage d'un alphabet discret

Soit un alphabet X discret (fini ou infini dénombrable).
X* désigne l'ensemble des séquences finies non
vides de lettres de X.
{0, 1}* l'ensemble des séquences binaires nies.

Définition 1
Un codage d'un alphabet discret est une procédure
qui associe à chaque séquence finie de lettres une
séquence binaire finie.
Un codage est une application de X* dans {0, 1}*.

B. rejeb, ISITCom 39

Codage d'un alphabet discret

Définition 2
Un code d'un alphabet discret est une
procédure qui associe à chaque lettre une
séquence binaire appelée mot de code.
Définition 3
Un code est régulier s'il est injectif (deux
lettres distinctes sont codées à l'aide de deux
mots de code distincts).

B. rejeb, ISITCom 40

20
 04/02/2020

Codage d'un alphabet discret

Définition 4
Soit X = (X, PX) une source discrète sans
mémoire d'entropie H et soit ϕ un code de X.
La longueur moyenne de ϕ, notée L, est le
nombre de symboles binaires utilisés en
moyenne pour coder une lettre de la source :
L = ∑ L(x).PX(x)
L'efficacité de ϕ est dénie par :
E(ϕ) = H / L
B. rejeb, ISITCom 41

Codage d'un alphabet discret

Codes de longueur fixe
Un code de longueur xe est un code dont tous les
mots de code ont la même longueur. On parlera
de longueur du code.
Exemple :
Soit une source dont l'alphabet est l'ensemble des
chiffres décimaux X = {0, 1, . . . , 9} muni de la loi
de probabilité uniforme. Le code de longueur fixe
d'une telle source a une longueur au moins 4.
Par exemple :

B. rejeb, ISITCom 42

21
 04/02/2020

Codage d'un alphabet discret

L'efficacité de ce code est égale à :

H(X)/4 = (log2 10)/4 = 0, 83.
Il est clair que ce code n'est pas optimal, puisque six
mots binaires de longueur 4 sont inutilisés, donc ce
code pourrait être utilisé pour une source ayant un
cardinal 16.
B. rejeb, ISITCom 43

Codage d'un alphabet discret

Il est cependant possible d'améliorer l'efficacité du codage en
considérant non plus des chiffres isolés mais des paires de chiffres.
• L’alphabet sera l'ensemble X2 = {00, 01, . . . , 99} de cardinal 100.
Si X est sans mémoire, la nouvelle source, notée X2 reste munie
d'une loi de probabilité uniforme, et son entropie vaut :
H(X2) = log2 100 = 2H(X).
• La puissance de 2 immédiatement supérieure à 100 est 27 = 128.
Il existe donc un code régulier de X2 de longueur 7.

• L'efficacité de ce code est cette fois égale à :

H(X2)/7 = (2 log2 10)/7 = 0, 95 ce qui est meilleur.

• En considérant la source X3 de 1000 lettres, codées en 10 symboles

binaires, on obtient une efficacité de 0, 996.

B. rejeb, ISITCom 44

22
 04/02/2020

Exercice 1
Soit S la source d’alphabet {a, b, c, d} et de
probabilité :
U s1 = a s2 = b s3 = c s4 = d
P(U) 0.5 0.25 0.125 0.125
On code S avec le code suivant :
a b c d
0 10 110 111

1. Coder adbccab. Décoder 1001101010

2. Est-ce un code instantané ?
3. Calculer l’entropie de la source

Exercice 1 : Solution
1. Le mot de pour adbccab est :
011110110110010
Le mot de source pour 1001101010 est :
bacbb
2. On vérifie facilement en comparant tous les
mots deux à deux qu’aucun n’est préfixe d’un
autre. C’est donc un code instantané.
3. L’entropie de la source est H = 1,75

23
 04/02/2020

Exercice 2
On veut construire un code compresseur binaire sur une
source S = (S,P) (supposée infinie) où S = (0, 1) est l’alphabet
source et P = (P(0) = p, P(1) = 1 − p) est la loi de
probabilité´e de S.
On propose le code suivant : on compte le nombre
d’occurrences de “0” avant l’apparition d’un “1”. Les deux
règles de codage sont :
– Une chaîne de quatre “0” consécutifs (sans “1”) est codée
par 0.
– Si moins de quatre “0” apparaissent avant un symbole
“1”, on code la chaîne par le mot de code “1e1e2”, où e1e2
est la représentation binaire du nombre de “0” apparus
avant le “1”.

Exercice 2
Par exemple, l’apparition de quatre zéros consécutifs “0000” est codée
par “0”, tandis que l’occurrence “001” est codé par “110” car deux
“0” sont apparus avant le “1” et que “10” est la représentation
binaire de deux.
1. Expliciter les 5 mots de code. Le code possède-t-il la propriété du
préfixe ?
2. Sachant que la probabilité d’apparition de deux symboles successifs
s1 et s2 est, dans notre cas o`u l’on suppose la source sans mémoire,
p(s1)*p(s2), calculer la probabilité d’occurrence dans S d’une chaîne
de k “0” suivis d’un “1”.
3. Pour chaque mot du code, calculer le nombre de bits de code
nécessaires par bit de source. En déduire le taux de compression
de ce code, c’est `a dire la longueur moyenne par bit de source.

24
 04/02/2020

Exercice 2 : Solution
1. 0 n’est préfixe d’aucun autre mot de code, car ils commencent
tous par 1.
Tous les autres mots de code sont de la même longueur, ils ne
peuvent donc pas être préfixes les uns des autres.
Autre preuve : on peut dessiner un arbre de Huffman contenant
tous les mots de code.

2. P(0 . . . 01) = P(0) . . . P(0)P(1) = pk(1 − p)

3. Pour les mots de code (100, 101, 110, 111, 0), les rapports
(nombres de bits de code par bit de source) sont :
(3/1, 3/2, 3/3, 3/4, 1/4).
Le taux de compression est donc
T = 3(1 − p) + 3/2(1 − p)p + (1 − p)p2 + 3/4(1 − p)p3 + 1/4p4
= 3 − 3/2p − 1/2p2 − 1/4p3 − 1/2p4

Exercice 2 : Solution
1. 0 n’est préfixe d’aucun autre mot de code, car ils commencent
tous par 1.
Tous les autres mots de code sont de la même longueur, ils ne
peuvent donc pas être préfixes les uns des autres.
Autre preuve : on peut dessiner un arbre de Huffman contenant
tous les mots de code.

2. P(0 . . . 01) = P(0) . . . P(0)P(1) = pk(1 − p)

3. Pour les mots de code (100, 101, 110, 111, 0), les rapports
(nombres de bits de code par bit de source) sont :
(3/1, 3/2, 3/3, 3/4, 1/4).
Le taux de compression est donc
T = 3(1 − p) + 3/2(1 − p)p + (1 − p)p2 + 3/4(1 − p)p3 + 1/4p4
= 3 − 3/2p − 1/2p2 − 1/4p3 − 1/2p4

25
 04/02/2020

Exercice 3 :
Cet exercice introduit des éléments théoriques
sur la valeur du code généré par l’algorithme
de Huffman. Soit la source S = (S,P), où S = (0,
1), et P(0) = 0.99 et P(1) = 0.01.
1. Calculer l’entropie de S.
2. Donner le code généré par l’algorithme de
Huffman sur la troisième extension S3.
Quel est son taux de compression ?

Exercice 3 : Solution
Le code issu de l’algorithme de Huffman est :

• L’entropie de S est
• Sa longueur moyenne est : L = 1.05, soit par bit
de source l = 0.35.

26
 04/02/2020

Codes de longueur variable

Codage de Huffman
Supposons avoir 8 messages m1, ...,m8.
la probabilité d’occurrence est donnée par
p1 = p2 = ... = p8 = 1/8.

Si l’alphabet est {0,1}, alors :

d=2 et L ≥ 3/1 = 3
• Donc, le codage à 3 bits [000,001,...,111] est efficace1.
• Quand d=2 donc H(X) donne la longueur en bits pour
un codage non-redondant

B. rejeb, ISITCom 53

Codes de longueur variable : Huffman

Si on dispose d’une autre distribution P :

• Alors : H(X) = 127/64

• On obtient un codage non-redondant
où L < 2 bits
• Ce codage permet le décodage instantané
(caractère par caractère, sans attendre une séquence
entière. On parle de propriété préfixe : aucun mot de
code n’est préfixe d’un autre).

B. rejeb, ISITCom 54

27
 04/02/2020

Codes de longueur variable : Huffman

Algorithme du codage de Huffman
1. Les messages constituent les feuilles d’un
arbre portant chacune un poids égal à la
probabilité P d’occurrence du message
correspondant
2. Joindre les 2 nœuds de moindre poids en un
nœud parent auquel on attache un poids égal
à la somme de ces 2 poids

B. rejeb, ISITCom 55

Codes de longueur variable : Huffman

3. Répéter le point 2 jusqu’à l’obtention d’une
seule racine à l’arbre
4. Affecter les codes 0 et 1 aux noeuds
descendants directs de la racine
5. Continuer à descendre en affectant des codes
à tous les nœuds, chaque paire de
descendants recevant les codes L0 et L1 où L
désigne le code associé au parent

B. rejeb, ISITCom 56

28
 04/02/2020

Description : Algorithme de Huffman

B. rejeb, ISITCom 57

Description : Algorithme de Huffman

B. rejeb, ISITCom 58

29
 04/02/2020

Codes de longueur variable : Huffman

Exemple 1 : Construction du code de Huffman

Étape suivante :

B. rejeb, ISITCom 59

Codes de longueur variable : Huffman

B. rejeb, ISITCom 60

30
 04/02/2020

Codes de longueur variable : Huffman

B. rejeb, ISITCom 61

Codes de longueur variable : Huffman

• Exemple 2
• soit un ensemble de 3 messages a, b et c de
probabilité respective 0.6, 0.3 et 0.1.
• L’algorithme est :

B. rejeb, ISITCom 62

31
 04/02/2020

Codage par substitutions

• 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 (pi >> pj)
• Autrement, on effectue une compression en
remplaçant seulement des séquences choisies de
texte par des codes plus courts, plusieurs façons :
o parcourir le texte et remplacer les séquences
redondantes par des séquences plus courtes(RLE)
o analyser préalablement le texte pour déterminer les
groupes à remplacer et les codes qui les remplacent
(LZW)

B. rejeb, ISITCom 63

Codage par substitutions

Codage RLE (Run Length Encoding)
• élimine certaines séquences de caractères en
les remplaçant par un code spécifique.
• Chaque k éléments ( k ≥ 3 ) est remplacée par
un caractère non utilisé (ex : @) suivi de
l’entier k et du caractère substitué.
• Si tous les caractères sont utilisés, on en
choisit un rarement utilisé comme "indicateur"
et on le double quand on rencontre ce
caractère rare
B. rejeb, ISITCom 64

32
 04/02/2020

Codage par substitutions : RLE

• Exemple 1
AB2000000394000005260DBBBBBBBA2
est remplacé par :
AB2@60394@505260D@7BA2
• Exemple 2
AB2000039444452600D666@A2
devient :
AB2@4039@4452600D@36@@A2
B. rejeb, ISITCom 65

Codage par substitutions

Bit-map
• Soit un enregistrement de 4 champs de 8
caractères
• Le principe est d’utiliser une bit-map devant
chaque enregistrement pour indiquer la présence
ou l’absence de valeur dans les différents champs
• Exemple

B. rejeb, ISITCom 66

33
 04/02/2020

Les algorithmes à dictionnaire

• Consistent à remplacer des séquences par
un code plus court qui est l’indice de ce
facteur dans un dictionnaire
• Le dictionnaire n’est qu’une portion du
texte encodé précédemment.
• L’encodeur examine le texte à compresser
par l’intermédiaire d’une fenêtre glissante
• EXP. LZ77, LZ78, LZW (Lempel, Ziv, Welch)
B. rejeb, ISITCom 67

Les algorithmes à dictionnaire

LZ78 (GZIP, PKZIP, 1978)
• Les séquences codées ont la forme d’un
couple (i,c),
o i est l’index de l’entrée dans le dictionnaire
correspondant à la plus longue chaîne
semblable à la dite séquence à coder,
o c, le caractère suivant la séquence dans le flux
d’entrée.
o Si la séquence n’a pas de correspondance
dans le dictionnaire, i est égal à 0, et le couple
est ajouté au dictionnaire

B. rejeb, ISITCom 68

34
 04/02/2020

Les algorithmes à dictionnaire

• Exemple de dictionnaire

B. rejeb, ISITCom 69

Les algorithmes à dictionnaire

LZW (ZIP, 1984)
• Principe :
Réduire l’envoi de l’informations au
décodeur.
o Au lieu du couple (i,c)

o Seul l’index « i » sera transmis.

B. rejeb, ISITCom 70

35
 04/02/2020

Les algorithmes à dictionnaire : LZW

• Algorithme :
o On initialise le dictionnaire en y plaçant les
codes des caractères ASCII étendu (256
caractères)
o On regarde le caractère à transmettre :

- s’il existe déjà dans la table, on regarde le

caractère suivant,
- si le groupe des deux existe également,
on regarde le suivant…
B. rejeb, ISITCom 71

Les algorithmes à dictionnaire : LZW

o Lorsqu’un nouveau groupe est découvert, on le
définit en l’insérant dans le dictionnaire.
- Dans un premier temps, on transmet les codes
des morceaux qui le composent.
- La prochaine fois qu’on le rencontrera,
on transmettra son code propre.
- Les mots ajoutés au dictionnaire seront
déterminés par l’intermédiaire d’une "fenêtre«
évoluant au fil de l’analyse du texte à compresser
o On procède de la sorte jusqu’à la fin de la
transmission.
B. rejeb, ISITCom 72

36
 04/02/2020

Algorithme LZW : Compression

B. rejeb, ISITCom 73

Algorithme LZW : Décompression

B. rejeb, ISITCom 74

37
 04/02/2020

Les algorithmes à dictionnaire : LZW

• Exemple
Soit le message à compresser : "ma maison"
1. Le premier caractère a analysé est "m". Il est dans le
dictionnaire.
2. Le caractère suivant est concaténé avec "m" forme la
chaine "ma"
- N’est pas dans le dictionnaire : il faut donc l’ajouter
- On lui affecte donc l’entrée 256 dans le dictionnaire
- On envoie la valeur correspondante à "m" (109)
Le code : 109
B. rejeb, ISITCom 75

Les algorithmes à dictionnaire : LZW

Message à compresser "ma maison"
3. On reprend au dernier caractère pris en compte "a"
- Concaténation avec le caractère suivant on a la
chaine "a " (a-espace).
- n’est pas dans le dictionnaire : il faut donc l’ajouter
- On lui affecte donc l’entrée 257 dans le
dictionnaire
- On envoie la valeur correspondante à "a" (97)

Le code : 109 – 97
B. rejeb, ISITCom 76

38
 04/02/2020

Les algorithmes à dictionnaire : LZW

Message à compresser "ma maison«
4. On reprend alors au dernier caractère pris en compte
(ici " ")
- Concaténation avec le caractère suivant on la
chaine " m"
- N’est pas dans le dictionnaire : il faut donc l’ajouter
- On lui affecte donc l’entrée 258 dans le
dictionnaire.
- On envoie la valeur correspondante à " "(32)
Le code : 109 – 97 – 32
B. rejeb, ISITCom 77

Les algorithmes à dictionnaire : LZW

Message à compresser "ma maison"
5. On reprend alors au dernier caractère pris en compte
("m").
- Concaténation avec le caractère suivant on la chaine
"ma".
- Chaine déjà dans le dictionnaire.
- Concaténation avec le caractère suivant on la chaine
"mai".
- N’est pas dans le dictionnaire : il faut donc l’ajouter
- On lui affecte donc l’entrée 259 dans le dictionnaire.
- On envoie donc la valeur correspondante à "ma" 256
Le code : 109 – 97 – 32 – 256
B. rejeb, ISITCom 78

39
 04/02/2020

Les algorithmes à dictionnaire : LZW

Message à compresser "ma maison"
6. On reprend alors au dernier caractère pris en
compte (ici "i").
- Concaténation avec le caractère suivant on la
chaine "is".
- N’est pas dans le dictionnaire : il faut donc l’ajouter.
- On lui affecte donc l’entrée 260 dans le
dictionnaire.
- On envoie la valeur correspondante à "i" (105)
Le code : 109 – 97 – 32 – 256 – 105
B. rejeb, ISITCom 79

Les algorithmes à dictionnaire : LZW

Message à compresser "ma maison"
7. On reprend alors au dernier caractère pris en compte
(ici "s")
- Concaténation avec le caractère suivant on la
chaine "so".
- N’est pas dans le dictionnaire : il faut donc l’ajouter
- On lui affecte donc l’entrée 261 dans le
dictionnaire.
- On envoie la valeur correspondante à "s". (115)
Le code : 109 – 97 – 32 – 256 – 105 – 115
B. rejeb, ISITCom 80

40
 04/02/2020

Les algorithmes à dictionnaire : LZW

Message à compresser "ma maison"
8. On reprend alors au dernier caractère pris en compte
(ici "o").
- Concaténation avec le caractère suivant on la
chaine "on".
- N’est pas dans le dictionnaire : il faut donc l’ajouter
- On lui affecte donc l’entrée 262 dans le
dictionnaire.
- On envoie la valeur correspondante à "o" (111)
Le code : 109 – 97 – 32 – 256 – 105 – 115 – 111
B. rejeb, ISITCom 81

Les algorithmes à dictionnaire : LZW

Message à compresser "ma maison"
9. On reprend alors au dernier caractère pris en compte
(ici "n").
-Concaténation avec le caractère suivant on la
chaine "n(eof)".
- N’est pas dans le dictionnaire : il faut donc l’ajouter.
- Etant donné le caractère spécifique de fin de
fichier, il n’est pas ajouté au dictionnaire.
- On envoie la valeur correspondante à "n" (110)
Le code : 109 – 97 – 32 – 256 – 105 – 115 – 111 – 110
B. rejeb, ISITCom 82

41
 04/02/2020

Les algorithmes à dictionnaire : LZW

Message à compresser "ma maison"
• Au final, le flux compressé sera :
(109)(97)(32)(256)(105)(115)(111)(110)

• Lors de la décompression, le décodage se

fera de manière inverse

B. rejeb, ISITCom 83

42