Compression de données

Table des matières

1. Introduction
2. Entropie
3. Huffman
4. Huffman adaptatif
5. Arithmétique
6. Réduction de l'entropie
7. RLE : Run Length Encoding
8. Méthodes par dictionnaire LZ (Lempel, Ziv)
9. LZ77
10. LZ78
11. LZW (Lempel, Ziv, Welch)
12. Rappel général

1 Introduction

Pourquoi on s'intéresse à la compression de données ?

La puissance des processeurs augmente plus vite que les capacités de stockage et de bande passante

1.1 Différents types de compression

Compression avec perte
- destructice, pertes irréversibles
- données perceptibles : images (jpeg, webp), sons (mp3, ogg vorbis), vidéos (mpeg, webm)
Compression presque sans perte
- compression logique (information équivalente 2+2 => 4)
- suppression des méta-données (EXIF pour jpeg)
- abbréviations (USA : United State of America)
- compression js, css (noms des variables plus courts)
Compression sans perte
- compression physique
- également appelé compactage (non destructrice)
- attention, si un algorithme compresse au moins un fichier, il en grossit au moins un

1.2 Compression symétrique/asymétrique

symétrique
- la compression et la décompression nécessitent le même nombre d'opérations (utile par exemple pour le transfert sur le réseau de fichiers texte, js, css, html…)
asymétrique
- une des 2 opérations (compression/décompression) nécessite plus d'opérations (utile par exemple pour l'archivage ou pour l'installation d'un programme)

1.3 Compression non-adaptative, adaptative ou semi-adaptive

non-adaptatif
- utilise un dictionnaire prédéfini en fonction du type de données
- utilisation de la fréquence d'apparition des lettres dans une langue donnée par ex pour la langue française : e,s,a,i,t,n,r,…
adapatif
- n'utilise aucune donnée a priori
- indépendant des données
semi-adapatif
- effectue un premier parcours des données à compresser pour construire un dictionnaire qui sera utilisé pour la compression

1.4 Notations/Vocabulaire

Notations
- alphabet source \(S = {s_1,...,s_{|S|}}\)
- code \(C = {c_1,...,c_{|S|}}\) avec \(f(s_i) = c_i\)
- distribution de probabilités sur \(S\), \(P = (p_1,...,p_{|S|})\)
- alphabet du code destination \(D = {d_1,...,d_{|D|}}\)
Vocabulaire
- quotient/ratio de compression : \(q = \frac{taille\_initiale}{taille\_finale}\)
- taux de compression : \(\tau = \frac{1}{q} = \frac{taille\_finale}{taille\_initiale}\)
- gain de compression : 1 - \(\tau\)

1.5 Préliminaires : décoder sans ambiguïté

ex : \(S = {A,...,Z}\) et \(C = {0,...,25}\) et \(D = {0,...,9}\)
123 peut correspondre à BCD, BX ou MD
la bijectivité de la fonction f n'est pas suffisante
Théorème : Un code C est non ambigu si et seulement si pour toutes séquences \(a = a_1...a_n\) et \(b = b_1...b_m\) de \(C^{+}\)
- \(a = b\) => (\(n = m\) et \(a_i = b_i\) pour tout \(i = 1,...,n\))
ex D = {0,1}
- C = {0,01,001} n'est pas uniquement déchiffrable
- C = {01, 10} est uniquement déchiffrable
- C = {0, 01, 11} est uniquement déchiffrable

1.6 Préliminaires : propriété préfixe

Avec la propriété préfixe, il est possible de décoder le code dès la fin de la réception d'un mot du code
ex : \(C = {0, 01, 11}\) est uniquement déchiffrable mais ne possède pas la propriété préfixe \(a = 001111111\dots\) on ne peut pas décoder le second mot \(0\) ou \(01\)

2 Entropie

2.1 définition

la quantité d'information contenue ou délivrée par une source d'information
\(H(S) = - \sum_{i=1}^{n} p_i log_2 (p_i)\)
\(p_i\) : probabilité d'apparition du symbole i de S

2.2 ABBCCCDDDDEEEEE :

H(ABBCCCDDDDEEEEE) = 2.14925539717

>>> from math import *
>>> -1./15*log(1./15)/log(2)
0.26045937304056793
>>> -2./15*log(2./15)/log(2)
0.3875854127478025
>>> -3./15*log(3./15)/log(2)
0.4643856189774725
>>> -4./15*log(4./15)/log(2)
0.5085041588289383
>>> -5./15*log(5./15)/log(2)
0.5283208335737187
>>> 0.26045937304056793+0.3875854127478025+0.4643856189774725
    +0.5085041588289383+0.5283208335737187
2.1492553971685

Chaque symbole possède une quantité de 2.1492553971685 bits, il faut donc théoriquement 15x2.1492553971685 = 32.2388309575 bits pour coder le message

3 Huffman

3.1 Huffman : Présentation

Principe du morse. Longueur du code en fonction des fréquences
Méthode de compression statistique en 2 passes (semi-adaptatif, asymétrique)
L'algorithme de Huffman est un codage optimal préfixe (symbole - symbole)

3.2 Huffman : Algorithme

première passe
- calculer la fréquence d'apparition des caractères de S
- trier par ordre croissant les fréquences
- créer l'arbre de Huffman
  - extraire les 2 premières plus petites fréquences (tri préalable, résultat différent)
  - créer un nouveau noeud avec comme nouvelle valeur la somme des 2 fréquences
  - réitérer jusqu'à obtenir un seul noeud (la racine)
- coder l'arbre de Huffman
deuxième passe
- coder la phrase avec l'arbre de Huffman

3.3 Huffman : ABBCCCDDDDEEEEE : 1

BB

CCC

DDDD

EEEEE

On calcule les fréquences des lettres : A apparaît 1 fois, B 2 fois, C 3 fois, D 4 fois et E 5 fois
On extrait ensuite les 2 premières plus petites fréquences A et B

3.4 Huffman : ABBCCCDDDDEEEEE : 2

ABB

CCC

DDDD

EEEEE

On retrie par ordre croissant (ici l'ordre ne change pas)
On extrait ensuite les 2 premières plus petites fréquences AB et C

3.5 Huffman : ABBCCCDDDDEEEEE : 3

ABBCCC

DDDD

EEEEE

On retrie par ordre croissant

3.6 Huffman : ABBCCCDDDDEEEEE : 4

DDDD

EEEEE

ABBCCC

On extrait ensuite les 2 premières plus petites fréquences D et E

3.7 Huffman : ABBCCCDDDDEEEEE : 5

DDDDEEEEE

ABBCCC

On retrie par ordre croissant

3.8 Huffman : ABBCCCDDDDEEEEE : 6

ABBCCC

DDDDEEEEE

On extrait ensuite les 2 premières plus petites fréquences ABC et DE

3.9 Huffman : ABBCCCDDDDEEEEE : 7

ABBCCCDDDDEEEEE

On code l'arbre de Huffman en partant toujours de la racine.
Le code de A est 0, 0 puis 0 soit 000
Le code de B est 001
Le code de C est 01
Le code de D est 10
Le code de E est 11

3.10 Huffman : ABBCCCDDDDEEEEE

ABBCCCDDDDEEEEE

On code le message ABBCCCDDDDEEEEE à partir de l'arbre de Huffman
sortie : \(000^A001^B001^B01^C01^C01^C10^D10^D10^D10^D11^E11^E11^E11^E11^E\) = 33 bits
codage de l'arbre (1 pour sous-arbre, 0 pour feuille): 1110A0B0C10D0E : 5*8+9 = 49 bits
49 + 33 = 82 bits

3.11 Huffman : Problèmes

la place du dico à coder
l'impossibilité de coder un caractère sur moins de 1 bit

4 Huffman adaptatif

4.1 Huffman adaptatif : Présentation

Éviter de transférer le codage du dico de l'algorithme de base
Méthode statistique adaptative en 1 passe (symétrique)

4.2 Huffman adapatif : Algorithme

créer un noeud vide α pour introduire un nouveau caractère
coder la phrase
- lire un caractère
- si déjà présent dans l'arbre
  - écrire le code du caractère présent dans l'arbre
  - augmenter la fréquence du caractère de 1
- sinon
  - écrire le code du caractère α
  - écrire le caractère en sortie
  - ajouter un nouveau noeud à l'arbre avec une fréquence 1
  - augmenter la fréquence du caractère α
- mettre à jour l'arbre
- réitérer jusqu'à la fin de la chaîne

4.3 Huffman adapatif : ABBCCCDDDDEEEEE : 1

0α

créer un noeud vide α pour introduire un nouveau caractère

4.4 Huffman adapatif : ABBCCCDDDDEEEEE : 1

\(\mathbf{0^αA}\)

0α

lire le caractère A
caractère non présent :
- on écrit le code du caractère α : 0
- on écrit le caractère A

4.5 Huffman adapatif : ABBCCCDDDDEEEEE : 2

\(0^αA\)

αA

on met à jour l'arbre

4.6 Huffman adapatif : ABBCCCDDDDEEEEE : 2

\(0^αA\mathbf{1^αB}\)

αA

lire le caractère B
caractère non présent :
- on écrit le code du caractère α : 1
- on écrit le caractère B

4.7 Huffman adapatif : ABBCCCDDDDEEEEE : 3

\(0^αA1^αB\)

αAαB

on met à jour l'arbre

4.8 Huffman adapatif : ABBCCCDDDDEEEEE : 3

\(0^αA1^αB\mathbf{01^B}\)

αAαB

lire le caractère B
caractère présent :
- on écrit le code du caractère B : 01

4.9 Huffman adapatif : ABBCCCDDDDEEEEE : 4

\(0^αA1^αB01^B\)

αAαBB

on met à jour l'arbre

4.10 Huffman adapatif : ABBCCCDDDDEEEEE : 4

\(0^αA1^αB01^B\mathbf{0^αC}\)

αAαBB

lire le caractère C
caractère non présent :
- on écrit le code du caractère α : 0
- on écrit le caractère C

4.11 Huffman adapatif : ABBCCCDDDDEEEEE : 5

\(0^αA1^αB01^B0^αC\)

αAαBBαC

on met à jour l'arbre

4.12 Huffman adapatif : ABBCCCDDDDEEEEE : 5

\(0^αA1^αB01^B0^αC\mathbf{101^C}\)

αAαBBαC

lire le caractère C
caractère présent :
- on écrit le code du caractère C : 101

4.13 Huffman adapatif : ABBCCCDDDDEEEEE : 6

\(0^αA1^αB01^B0^αC101^C\)

αAαBBαCC

on met à jour l'arbre

4.14 Huffman adapatif : ABBCCCDDDDEEEEE : 6

\(0^αA1^αB01^B0^αC101^C\mathbf{10^C}\)

αAαBBαCC

lire le caractère C
caractère présent :
- on écrit le code du caractère C : 10

4.15 Huffman adapatif : ABBCCCDDDDEEEEE : 7

\(0^αA1^αB01^B0^αC101^C10^C\)

αAαBBαCCC

on met à jour l'arbre

4.16 Huffman adapatif : ABBCCCDDDDEEEEE : 7

\(0^αA1^αB01^B0^αC101^C10^C\mathbf{0^αD}\)

αAαBBαCCC

lire le caractère D
caractère non présent :
- on écrit le code du caractère α : 0
- on écrit le caractère D

4.17 Huffman adapatif : ABBCCCDDDDEEEEE : 8

\(0^αA1^αB01^B0^αC101^C10^C0^αD\)

αAαBBαCCCαD

on met à jour l'arbre

4.18 Huffman adapatif : ABBCCCDDDDEEEEE : 8

\(0^αA1^αB01^B0^αC101^C10^C0^αD\mathbf{1101^D}\)

αAαBBαCCCαD

lire le caractère D
caractère présent :
- on écrit le code du caractère D : 1101

4.19 Huffman adapatif : ABBCCCDDDDEEEEE : 9

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D\)

αAαBBαCCCαDD

on met à jour l'arbre

4.20 Huffman adapatif : ABBCCCDDDDEEEEE : 9

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D\mathbf{00^D}\)

αAαBBαCCCαDD

lire le caractère D
caractère présent :
- on écrit le code du caractère D : 00

4.21 Huffman adapatif : ABBCCCDDDDEEEEE : 10

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D\)

αAαBBαCCCαDDD

on met à jour l'arbre

4.22 Huffman adapatif : ABBCCCDDDDEEEEE : 10

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D\mathbf{10^D}\)

αAαBBαCCCαDDD

lire le caractère D
caractère présent :
- on écrit le code du caractère D : 10

4.23 Huffman adapatif : ABBCCCDDDDEEEEE : 11

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D10^D\)

αAαBBαCCCαDDDD

on met à jour l'arbre

4.24 Huffman adapatif : ABBCCCDDDDEEEEE : 11

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D10^D\mathbf{11^αE}\)

αAαBBαCCCαDDDD

lire le caractère E
caractère non présent :
- on écrit le code du caractère α : 11
- on écrit le caractère E

4.25 Huffman adapatif : ABBCCCDDDDEEEEE : 12

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D10^D11^αE\)

αAαBBαCCCαDDDDαE

on met à jour l'arbre

4.26 Huffman adapatif : ABBCCCDDDDEEEEE : 12

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D10^D11^αE\mathbf{0101^E}\)

αAαBBαCCCαDDDDαE

lire le caractère E
caractère présent :
- on écrit le code du caractère E : 0101

4.27 Huffman adapatif : ABBCCCDDDDEEEEE : 13

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D10^D11^αE0101^E\)

αAαBBαCCCαDDDDαEE

on met à jour l'arbre

4.28 Huffman adapatif : ABBCCCDDDDEEEEE : 13

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D10^D11^αE0101^E\mathbf{100^E}\)

αAαBBαCCCαDDDDαEE

lire le caractère E
caractère présent :
- on écrit le code du caractère E : 100

4.29 Huffman adapatif : ABBCCCDDDDEEEEE : 14

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D10^D11^αE0101^E100^E\)

αAαBBαCCCαDDDDαEEE

on met à jour l'arbre

4.30 Huffman adapatif : ABBCCCDDDDEEEEE : 14

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D10^D11^αE0101^E100^E\mathbf{00^E}\)

αAαBBαCCCαDDDDαEEE

lire le caractère E
caractère présent :
- on écrit le code du caractère E : 00

4.31 Huffman adapatif : ABBCCCDDDDEEEEE : 15

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D10^D11^αE0101^E100^E00^E\)

αAαBBαCCCαDDDDαEEEE

on met à jour l'arbre

4.32 Huffman adapatif : ABBCCCDDDDEEEEE : 15

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D10^D11^αE0101^E100^E00^E\mathbf{01^E}\)

αAαBBαCCCαDDDDαEEEE

lire le caractère E
caractère présent :
- on écrit le code du caractère E : 01

4.33 Huffman adapatif : ABBCCCDDDDEEEEE : 16

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D10^D11^αE0101^E100^E00^E01^E\)

αAαBBαCCCαDDDDαEEEEE

4.34 Huffman adapatif : ABBCCCDDDDEEEEE

=0A1B010C101100D1101001011E01011000001
5*8+32 = 72 bits

4.35 Huffman adapatif : Décodage : 1

0α

créer un noeud vide α pour lire un nouveau caractère

4.36 Huffman adapatif : Décodage : 1

\(\mathbf{0^αA}\)

0α

on lit le code 0 qui correspond au caractère α
on lit donc les 8 bits suivants correspondant au caractère A

4.37 Huffman adapatif : Décodage : 2

\(0^αA\)

αA

on met à jour l'arbre

4.38 Huffman adapatif : Décodage : 2

\(0^αA\mathbf{1^αB}\)

αA

on lit le code 1 qui correspond au caractère α
on lit donc les 8 bits suivants correspondant au caractère B

4.39 Huffman adapatif : Décodage : 3

\(0^αA1^αB\)

αAαB

on met à jour l'arbre

4.40 Huffman adapatif : Décodage : 3

\(0^αA1^αB\mathbf{01^B}\)

αAαB

on lit le code 01 qui correspond au caractère B

4.41 Huffman adapatif : Décodage : 4

\(0^αA1^αB01^B\)

αAαBB

on met à jour l'arbre

4.42 Huffman adapatif : Décodage : 4

\(0^αA1^αB01^B\mathbf{0^αC}\)

αAαBB

on lit le code 0 qui correspond au caractère α
on lit donc les 8 bits suivants correspondant au caractère C

4.43 Huffman adapatif : Décodage : 5

\(0^αA1^αB01^B0^αC\)

αAαBBαC

on met à jour l'arbre

4.44 Huffman adapatif : Décodage : 5

\(0^αA1^αB01^B0^αC\mathbf{101^C}\)

αAαBBαC

on lit le code 101 qui correspond au caractère C

4.45 Huffman adapatif : Décodage : 6

\(0^αA1^αB01^B0^αC101^C\)

αAαBBαCC

on met à jour l'arbre

4.46 Huffman adapatif : Décodage : 6

\(0^αA1^αB01^B0^αC101^C\mathbf{10^C}\)

αAαBBαCC

on lit le code 10 qui correspond au caractère C

4.47 Huffman adapatif : Décodage : 7

\(0^αA1^αB01^B0^αC101^C10^C\)

αAαBBαCCC

on met à jour l'arbre

4.48 Huffman adapatif : Décodage : 7

\(0^αA1^αB01^B0^αC101^C10^C\mathbf{0^αD}\)

αAαBBαCCC

on lit le code 0 qui correspond au caractère α
on lit donc les 8 bits suivants correspondant au caractère D

4.49 Huffman adapatif : Décodage : 8

\(0^αA1^αB01^B0^αC101^C10^C0^αD\)

αAαBBαCCCαD

on met à jour l'arbre

4.50 Huffman adapatif : Décodage : 8

\(0^αA1^αB01^B0^αC101^C10^C0^αD\mathbf{1101^D}\)

αAαBBαCCCαD

on lit le code 1101 qui correspond au caractère D

4.51 Huffman adapatif : Décodage : 9

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D\)

αAαBBαCCCαDD

on met à jour l'arbre

4.52 Huffman adapatif : Décodage : 9

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D\mathbf{00^D}\)

αAαBBαCCCαDD

on lit le code 00 qui correspond au caractère D

4.53 Huffman adapatif : Décodage : 10

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D\)

αAαBBαCCCαDDD

on met à jour l'arbre

4.54 Huffman adapatif : Décodage : 10

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D\mathbf{10^D}\)

αAαBBαCCCαDDD

on lit le code 10 qui correspond au caractère D

4.55 Huffman adapatif : Décodage : 11

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D10^D\)

αAαBBαCCCαDDDD

on met à jour l'arbre

4.56 Huffman adapatif : Décodage : 11

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D10^D\mathbf{11^αE}\)

αAαBBαCCCαDDDD

on lit le code 11 qui correspond au caractère α
on lit donc les 8 bits suivants correspondant au caractère E

4.57 Huffman adapatif : Décodage : 12

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D10^D11^αE\)

αAαBBαCCCαDDDDαE

on met à jour l'arbre

4.58 Huffman adapatif : Décodage : 12

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D10^D11^αE\mathbf{0101^E}\)

αAαBBαCCCαDDDDαE

on lit le code 0101 qui correspond au caractère E

4.59 Huffman adapatif : Décodage : 13

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D10^D11^αE0101^E\)

αAαBBαCCCαDDDDαEE

on met à jour l'arbre

4.60 Huffman adapatif : Décodage : 13

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D10^D11^αE0101^E\mathbf{100^E}\)

αAαBBαCCCαDDDDαEE

on lit le code 100 qui correspond au caractère E

4.61 Huffman adapatif : Décodage : 14

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D10^D11^αE0101^E100^E\)

αAαBBαCCCαDDDDαEEE

on met à jour l'arbre

4.62 Huffman adapatif : Décodage : 14

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D10^D11^αE0101^E100^E\mathbf{00^E}\)

αAαBBαCCCαDDDDαEEE

on lit le code 00 qui correspond au caractère E

4.63 Huffman adapatif : Décodage : 15

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D10^D11^αE0101^E100^E00^E\)

αAαBBαCCCαDDDDαEEEE

on met à jour l'arbre

4.64 Huffman adapatif : Décodage : 15

\(0^αA1^αB01^B0^αC101^C10^C0^αD1101^D00^D10^D11^αE0101^E100^E00^E\mathbf{01^E}\)

αAαBBαCCCαDDDDαEEEE

on lit le code 01 qui correspond au caractère E

4.65 Huffman adaptatif : Problèmes

Très sensible aux erreurs

5 Arithmétique

5.1 Arithmétique : Présentation

Le codage arithmétique :

s'attaque au problème de Huffman du code des symboles sur des bits entier
est une méthode statistique semi-adaptative en 2 passes asymétrique
représente la chaîne entière à coder sous la forme d'un seul nombre réel

5.2 Arithmétique : Algorithme pour l'encodage

première passe
- on calcule des intervalles pour chaque symbole en fonction de leur fréquence d'apparition
deuxième passe
- on définit la borne basse en cours = 0
- on définit la borne haute en cours = 1
- on parcourt tous les symboles
  - écart = borne haute en cours - borne basse en cours
  - borne basse en cours = borne basse en cours + écart * borne basse du caractère à coder
  - borne haute en cours = borne basse en cours + écart * borne haute du caractère à coder
- on chercher le plus petit réel compris dans l'intervalle des 2 bornes

5.3 Arithmétique : ABBCCCDDDDEEEEE : première passe 1

On calcule les intervalles.
Pour calculer l'intervale on commence par 0 et on ajoute la première fréquence ce qui donne [0, 1/15), [0,0.0666...) pour A.
Ensuite on part de la borne max du dernier symbole, ici 1/15 ce qui donne la borne min de B et on ajoute la fréquence de B ce qui donne 1/15 + 2/15 = 3/15.
La borne max de B est 3/15 et donne la borne min de C. On ajoute la fréquence de C ce qui donne 3/15 + 3/15 = 6/15
etc.

5.4 Arithmétique : ABBCCCDDDDEEEEE : première passe 2

symbole	fréquence	intervalle	intervalle final
A	1/15	[0 , 0 + 1/15)	[0 , 0.0666…)
B	2/15	[1/15 , 1/15 + 2/15)	[0.0666… , 0.2 )
C	3/15	[3/15 , 3/15 + 3/15)	[0.2 , 0.4 )
D	4/15	[6/15 , 6/15 + 4/15)	[0.4 , 0.6666…)
E	5/15	[10/15 , 10/15 + 5/15)	[0.6666… , 1 )

5.5 Arithmétique : ABBCCCDDDDEEEEE : deuxième passe 1

On commence avec [0, 1) borne basse = 0 et borne haute = 1
On lit A qui a comme intervale [0, 0.0666…)
On calcule notre écart qui vaut borne haute - borne basse c'est à dire 1
On calcule notre nouvelle borne basse en cours
- borne basse en cours + écart * borne basse du caractère à coder
- c'est à dire 0 + 1 * 0
On calcule notre nouvelle borne haute en cours
- borne basse en cours + écart * borne haute du caractère à coder
- c'est à dire 0 + 1 * 0.0666

5.6 Arithmétique : ABBCCCDDDDEEEEE : deuxième passe 2

on lit le A : [0 , 1)

écart       = 1 - 0             = 1
borne basse = 0 + 1 * 0         = 0
borne haute = 0 + 1 * 0.0666... = 0.0666...

on lit le B : [0 , 0.0666…)

écart       = 0.0666... - 0             = 0.0666...
borne basse = 0 + 0.0666... * 0.0666... = 0.00444...
borne haute = 0 + 0.0666... * 0.2       = 0.01333...

on lit le B : [0.00444… , 0.01333…)

écart       = 0.01333... - 0.00444...              = 0.008888...
borne basse = 0.00444... + 0.008888... * 0.0666... = 0.00503703...
borne haute = 0.00444... + 0.008888... * 0.2       = 0.006222...

5.7 Arithmétique : ABBCCCDDDDEEEEE : deuxième passe 3

C [0.00503703703703 , 0.006222222222)
C [0.00532148148148 , 0.005511111111)
C [0.00533096296296 , 0.005340444444)
D [0.00533475555556 , 0.0053372839506173)
D [0.0053357669135802 , 0.0053364411522634)
D [0.0053360366090535 , 0.0053362164060357)
D [0.0053361085278464 , 0.0053361564737083)
E [0.0053361404917543 , 0.0053361564737083)
E [0.0053361511463903 , 0.0053361564737083)
E [0.0053361546979356 , 0.0053361564737083)
E [0.0053361558817841 , 0.0053361564737083)
E [0.0053361562764002 , 0.0053361564737083)

5.8 Arithmétique : ABBCCCDDDDEEEEE : deuxième passe 4

On cherche le plus petit réel compris dans notre intervalle [0.0053361562764002 , 0.0053361564737083)
Ici il s'agit de 0.00533615634777 codé par 01110111 1010111011011010111011001
Vous pourrez trouver un exemple sur https://www.h-schmidt.net/FloatConverter/IEEE754.html (dans notre cas nous n'avons pas besoin du bit pour le signe qui est toujours positif)
En python vous pouvez le calculer avec

2**-8*sum([int(c)*2**-index
           for index, c in enumerate('1010111011011010111011001')])

Ce n'est pas très important si vous ne comprenez pas toute la représentation des nombres réels

5.9 Arithmétique : Résumé

On utilise 8 bits pour l'exposant et 25 pour Mantissa soit 33 bits
Il faut stocker le tableau de fréquences, pour notre exemple court on pourrait indiquer le nombre d'apparition de chaque lettre avec 3 bits, ce qui donnerait 5*3 + 5*8 = 55 bits
55+33 = 88 bits

5.10 Arithmétique : Algorithme pour le décodage

À partir de la valeur en cours, trouver le symbole correspondant
\(\text{nouvelle valeur} = \frac{\text{valeur en cours} - \text{borne basse du symbole en cours}}{\text{probabilité du symbole}}\)

5.11 Arithmétique : Décodage `0.00533615634777` - 1

On trouve A car 0.00533615634777 est compris entre [0 , 0.0666...)
nouvelle valeur = (0.00533615634777-0)/(1./15) = 0.08004234521655
On trouve B car 0.08004234521655 est compris entre [0.0666... , 0.2)
nouvelle valeur = (0.08004234521655-1./15)/(2./15) = 0.10031758912412501
On trouve B car 0.10031758912412501 est compris entre [0.0666... , 0.2)
nouvelle valeur = (0.10031758912412501-1./15)/(2./15) = 0.2523819184309376

5.12 Arithmétique : Décodage `0.00533615634777` - 2

C : 0.2523819184309376 entre [0.2, 0.4)
C : 0.26190959215468795 entre [0.2, 0.4)
C : 0.3095479607734397 entre [0.2, 0.4)
D : 0.5477398038671984 entre [0.4, 0.666666666)
D : 0.5540242645019942 entre [0.4, 0.666666666)
D : 0.577590991882478 entre [0.4, 0.666666666)
D : 0.6659662195592924 entre [0.4, 0.666666666)
E : 0.9973733233473463 entre [0.6666666666, 1)
E : 0.992119970042039 entre [0.6666666666, 1)
E : 0.9763599101261171 entre [0.6666666666, 1)
E : 0.9290797303783515 entre [0.6666666666, 1)
E : 0.7872391911350545 entre [0.6666666666, 1)

5.13 Arithmétique : Problèmes

Il faut trouver comment coder les fréquences des caractères (on retrouve le problème du dictionnaire de Huffman).
Attention aux arrondis, la manipulation des réels peut poser des problèmes avec les ordinateurs et le nombre de chiffres après la virgule limité

6 Réduction de l'entropie

ABBCCCDDDDEEEEE et EBCEDDEAEDBECDC possèdent la même entropie
pourtant on peut imaginer que le premier peut être compressé avec plus d'efficacité que le second
au lieu de compresser directement le message, on va chercher à réduire son entropie

7 RLE : Run Length Encoding

7.1 RLE : Présentation

Permet de compresser l'apparition successive du même caractère
Utile pour les images noir/blanc, utilisé par exemple pour le transfert par fax
Pour éviter le problème de l'augmentation de l'espace quand il y a peu de répétitions, on peut utiliser un caractère spécial pour prévenir s'il s'agit d'une étape de compression ou pas

7.2 RLE : Exemple

Par exemple AAAAABBBBB peut être remplacer par 5A5B
Mais si on a ABABAB il faudrait écrire 1A1B1A1B1A1B ce qui n'est pas du tout efficace
L'utilisation d'un caractère spécial par exemple ! permet d'éviter ce problème mais devient intéressant seulement à partir de plus de 3 apparitions du même symbole
On aurait donc !5A!5B pour AAAAABBBBB alors que ABABAB reste inchangé.

7.3 RLE : ABBCCCDDDDEEEEE

Sans utiliser de caractère spécial on a

1A2B3C4D5E = 10*8 = 80 bits

Avec un caractère spécial par exemple ! on a

ABBCCC!4D!5E = 12*8 = 96 bits

8 Méthodes par dictionnaire LZ (Lempel, Ziv)

Le but des méthodes par dictionnaire est de remplacer des motifs fréquents par des références dans un dictionnaire

9 LZ77

9.1 LZ77 : Présentation

Algorithme adaptatif de type dictionnaire (local) en 1 passe (asymétrique)
Bien adapté pour compresser peu et décompresser souvent
La sortie est de type (position, longueur, caractère suivant)

9.2 LZ77 : Algorithme

Trouver le plus long prefixe dans le dico local
Afficher la position dans la fenêtre par rapport à la position courante
Afficher la longueur du préfixe
Afficher le caractère qui apparaît après le préfixe
Réitérer jusqu'à la fin de la chaîne

9.3 LZ77 : ABBCCCDDDDEEEEE : paramètres

L'algorithme LZ77 utilise 2 paramètres:
- longueur de la fenêtre (qui correspond à la taille du dictionnaire dans lequel nous chercherons le préfixe)
- longueur du préfixe (qui correspond à la longueur maximum du préfixe recherché)
Pour notre exemple, la chaîne de caractères étant petite, nous choisirons une fenêtre de 7 symboles (qui nécessite 3 bits pour stocker cette information), et une longueur de préfixe de 3 symboles (qui nécessite 2 bits pour stocker cette information)

9.4 LZ77 : ABBCCCDDDEEEEEE : 1

En jaune, la fenêtre correspondant au dictionnaire
On lit le symbole A, il n'existe pas dans le dictionnaire local, on affiche donc 0, 0, A
On décale la fenêtre après le symbole A

On lit le symbole B, il n'existe pas dans le dictionnaire local, on affiche donc 0, 0, B
On décale la fenêtre après le premier symbole B

9.5 LZ77 : ABBCCCDDDEEEEEE : 2

On lit le symbole B, il existe dans le dictionnaire local, on recherche le plus grand préfixe
Le plus grand préfixe est seulement B en rouge, on affiche donc l'index dans le dictionnaire du B qui est 1 la longueur du préfixe qui est aussi 1
Puis on affiche le caractère qui suit, le C (soit 1, 1, C)
On décale la fenêtre après le premier symbole C

9.6 LZ77 : ABBCCCDDDEEEEEE : 3

On lit le symbole C, il existe dans le dictionnaire local, on recherche le plus grand préfixe
Le plus grand préfixe est CC, on affiche donc l'index dans le dictionnaire qui est 1 et la longueur du préfixe qui est 2
Quand le caractère de fin du dictionnaire se répète on peut déborder sur la droite car si la longueur du préfixe dépasse cela signifie qu'il s'agit du même caractère répété.
Puis on affiche le caractère qui suit, le D (soit 1, 2, D)
On décale la fenêtre après le premier symbole D

9.7 LZ77 : ABBCCCDDDEEEEEE : 4

9.8 LZ77 : Résumé

(0,0,A) (0,0,B) (1,1,C) (1,2,D) (1,3,E) (1,3,E)
6*(3+2+8) = 78 bits

9.9 LZ77 : Décodage

(0,0,A) (0,0,B) (1,1,C) (1,2,D) (1,3,E) (1,3,E)

A
B
BC
CCD
DDDE
EEEE

0,0,A pas de préfixe, on affiche directement A
0,0,B pas de préfixe, on affiche directement B
1,1,C un préfixe qui commence par la dernière lettre affichée B et de longueur 1 donc B, puis on affiche C
1,2,D un préfixe qui commence par la dernière lettre affichée C et de longueur 2 donc C puis de nouveau C, puis on affiche D
1,3,E un préfixe qui commence par la dernière lettre affichée D et de longueur 3 donc DDD, puis on affiche E
1,3,E un préfixe qui commence par la dernière lettre affichée E et de longueur 3 donc EEE, puis on affiche E

10 LZ78

10.1 LZ78 : Présentation

méthode dictionnaire adaptative en 1 passe (symétrique)
La sortie est de type (index, caractère suivant)

10.2 LZ78 : Algorithme

lire un symbole
si le mot en cours suffixé par le symbole est présent dans le dico
- ajouter le symbole au mot en cours
sinon
- afficher l'index dans le dico du mot en cours
- afficher le symbole
- ajouter le mot en cours suffixé par le symbole dans le dico
- réinitialiser le mot en cours à vide

10.3 LZ78 : ABBCCCDDDDEEEEE : 1

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A		1

On commence avec le dictionnaire vide 0, null (1 bit est nécessaire pour stocker le dictionnaire)
On lit le premier symbole A

10.4 LZ78 : ABBCCCDDDDEEEEE : 2

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A

Le mot en cours suffixé par le symbole donne A et n'est pas dans le dictionnaire
- on affiche en sortie l'index dans le dico du mot en cours : 0
- on affiche en sortie le symbole A
- on ajoute le mot en cours suffixé par le symbole dans le dictionnaire : 1, A
- on réinitialise le mot en cours à vide

10.5 LZ78 : ABBCCCDDDDEEEEE : 3

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B

On lit le symbole suivant B

10.6 LZ78 : ABBCCCDDDDEEEEE : 4

Dictionnaire	Symbole	Sortie	Taille dico
0, null	A	0, A	1
1, A	B	0, B
2, B			2

Le mot en cours suffixé par le symbole donne B et n'est pas dans le dictionnaire
- on affiche en sortie l'index dans le dico du mot en cours : 0
- on affiche en sortie le symbole B
- on ajoute le mot en cours suffixé par le symbole dans le dictionnaire : 2, B (la taille du dico augmente d'un bit pour stocker l'index 2)
- on réinitialise le mot en cours à vide

10.7 LZ78 : ABBCCCDDDDEEEEE : 5

Dictionnaire	Symbole	Sortie	Taille dico
0, null	A	0, A	1
1, A	B	0, B
2, B	B		2

On lit le symbole suivant B

10.8 LZ78 : ABBCCCDDDDEEEEE : 6

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B

Le mot en cours suffixé par le symbole donne B et est présent dans le dictionnaire
- on ajoute donc le symbole au mot en cours qui devient B

10.9 LZ78 : ABBCCCDDDDEEEEE : 7

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C

On lit le symbole suivant C

10.10 LZ78 : ABBCCCDDDDEEEEE : 8

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C	2, C
3, BC

Le mot en cours suffixé par le symbole donne BC et n'est pas dans le dictionnaire
- on affiche en sortie l'index dans le dico du mot en cours : 2
- on affiche en sortie le symbole C
- on ajoute le mot en cours suffixé par le symbole dans le dictionnaire : 3, BC
- on réinitialise le mot en cours à vide

10.11 LZ78 : ABBCCCDDDDEEEEE : 9

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C	2, C
3, BC		C

On lit le symbole suivant C

10.12 LZ78 : ABBCCCDDDDEEEEE : 10

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C	2, C
3, BC		C	0, C
4, C				3

C n'est pas dans le dico, on affiche 0,C et on ajoute 4,C au dictionnaire (qui nécessite maintenant 3 bits)

10.13 LZ78 : ABBCCCDDDDEEEEE : 11

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C	2, C
3, BC		C	0, C
4, C		C		3

On lit le symbole suivant C

10.14 LZ78 : ABBCCCDDDDEEEEE : 12

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C	2, C
3, BC		C	0, C
4, C		C		3
	C

C est dans le dico, on ajoute C au mot en cours

10.15 LZ78 : ABBCCCDDDDEEEEE : 13

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C	2, C
3, BC		C	0, C
4, C		C		3
	C	D

On lit le symbole suivant D

10.16 LZ78 : ABBCCCDDDDEEEEE : 14

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C	2, C
3, BC		C	0, C
4, C		C		3
	C	D	4, D
5, CD

CD n'est pas dans le dico, on affiche 4,D (4 étant l'index dans le dico du mot en cours et D le symbole) et on ajoute 5,CD au dictionnaire

10.17 LZ78 : ABBCCCDDDDEEEEE : 15

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C	2, C
3, BC		C	0, C
4, C		C		3
	C	D	4, D
5, CD		D

On lit le symbole suivant D

10.18 LZ78 : ABBCCCDDDDEEEEE : 16

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C	2, C
3, BC		C	0, C
4, C		C		3
	C	D	4, D
5, CD		D	0, D
6, D

D n'est pas dans le dico, on affiche 0,D et on ajoute 6,D au dictionnaire

10.19 LZ78 : ABBCCCDDDDEEEEE : 17

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C	2, C
3, BC		C	0, C
4, C		C		3
	C	D	4, D
5, CD		D	0, D
6, D		D

On lit le symbole suivant D

10.20 LZ78 : ABBCCCDDDDEEEEE : 18

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C	2, C
3, BC		C	0, C
4, C		C		3
	C	D	4, D
5, CD		D	0, D
6, D		D
	D

D est dans le dico, on ajoute D au mot en cours

10.21 LZ78 : ABBCCCDDDDEEEEE : 19

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C	2, C
3, BC		C	0, C
4, C		C		3
	C	D	4, D
5, CD		D	0, D
6, D		D
	D	D

On lit le symbole suivant D

10.22 LZ78 : ABBCCCDDDDEEEEE : 20

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C	2, C
3, BC		C	0, C
4, C		C		3
	C	D	4, D
5, CD		D	0, D
6, D		D
	D	D	6, D
7, DD

DD n'est pas dans le dico, on affiche 6,D (6 étant l'index dans le dico du mot en cours et D le symbole) et on ajoute 7,DD au dictionnaire

10.23 LZ78 : ABBCCCDDDDEEEEE : 21

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C	2, C
3, BC		C	0, C
4, C		C		3
	C	D	4, D
5, CD		D	0, D
6, D		D
	D	D	6, D
7, DD		E

On lit le symbole suivant E

10.24 LZ78 : ABBCCCDDDDEEEEE : 22

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C	2, C
3, BC		C	0, C
4, C		C		3
	C	D	4, D
5, CD		D	0, D
6, D		D
	D	D	6, D
7, DD		E	0, E
8, E				4

E n'est pas dans le dico, on affiche 0,E et on ajoute 8,E au dictionnaire

10.25 LZ78 : ABBCCCDDDDEEEEE : 23

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C	2, C
3, BC		C	0, C
4, C		C		3
	C	D	4, D
5, CD		D	0, D
6, D		D
	D	D	6, D
7, DD		E	0, E
8, E		E		4

On lit le symbole suivant E

10.26 LZ78 : ABBCCCDDDDEEEEE : 24

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C	2, C
3, BC		C	0, C
4, C		C		3
	C	D	4, D
5, CD		D	0, D
6, D		D
	D	D	6, D
7, DD		E	0, E
8, E		E		4
	E

E est dans le dico, on ajoute E au mot en cours

10.27 LZ78 : ABBCCCDDDDEEEEE : 25

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C	2, C
3, BC		C	0, C
4, C		C		3
	C	D	4, D
5, CD		D	0, D
6, D		D
	D	D	6, D
7, DD		E	0, E
8, E		E		4
	E	E

On lit le symbole suivant E

10.28 LZ78 : ABBCCCDDDDEEEEE : 26

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C	2, C
3, BC		C	0, C
4, C		C		3
	C	D	4, D
5, CD		D	0, D
6, D		D
	D	D	6, D
7, DD		E	0, E
8, E		E		4
	E	E	8, E
9, EE

EE n'est pas dans le dico, on affiche 8,E et on ajoute 9,EE au dictionnaire

10.29 LZ78 : ABBCCCDDDDEEEEE : 27

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C	2, C
3, BC		C	0, C
4, C		C		3
	C	D	4, D
5, CD		D	0, D
6, D		D
	D	D	6, D
7, DD		E	0, E
8, E		E		4
	E	E	8, E
9, EE		E

On lit le symbole suivant E

10.30 LZ78 : ABBCCCDDDDEEEEE : 28

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C	2, C
3, BC		C	0, C
4, C		C		3
	C	D	4, D
5, CD		D	0, D
6, D		D
	D	D	6, D
7, DD		E	0, E
8, E		E		4
	E	E	8, E
9, EE		E
	E

E est dans le dico, on ajoute E au mot en cours

10.31 LZ78 : ABBCCCDDDDEEEEE : 29

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C	2, C
3, BC		C	0, C
4, C		C		3
	C	D	4, D
5, CD		D	0, D
6, D		D
	D	D	6, D
7, DD		E	0, E
8, E		E		4
	E	E	8, E
9, EE		E
	E	E

On lit le symbole suivant E

10.32 LZ78 : ABBCCCDDDDEEEEE : 30

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
0, null		A	0, A	1
1, A		B	0, B
2, B		B		2
	B	C	2, C
3, BC		C	0, C
4, C		C		3
	C	D	4, D
5, CD		D	0, D
6, D		D
	D	D	6, D
7, DD		E	0, E
8, E		E		4
	E	E	8, E
9, EE		E
	E	E
	EE		9

EE est dans le dico, on ajoute E au mot en cours
C'est la fin du message, on affiche 9

10.33 LZ78 : Résumé

0,A,0,B,2,C,0,C,4,D,0,D,6,D,0,E,8,E,9
(2*1 + 2*2 + 4*3 + 2*4)+9*8 = 98 bits
La taille du dictionnaire varie, il faut donc regarder la taille courante au moment de l'affichage en sortie

10.34 LZ78 : Décodage

0,A,0,B,2,C,0,C,4,D,0,D,6,D,0,E,8,E,9

0,A On affiche A et on ajoute A au dico à l'index 1
0,B On affiche B et on ajoute B au dico à l'index 2
2,C On affiche BC, B provenant du dico à l'index 2 et on ajoute BC au dico à l'index 3
0,C On affiche C et on ajoute C au dico à l'index 4
4,D On affiche CD, C provenant du dico à l'index 4 et on ajoute CD au dico à l'index 5
0,D On affiche D et on ajoute D au dico à l'index 6
6,D On affiche DD et on ajoute DD au dico à l'index 7
0,E On affiche E et on ajoute E au dico à l'index 8
8,E On affiche EE et on ajoute EE au dico à l'index 9
9 On affiche EE

11 LZW (Lempel, Ziv, Welch)

11.1 LZW : Présentation

méthode dictionnaire adaptative en 1 passe (symétrique)
basé sur lz78 avec en sortie uniquement des index

11.2 LZW : Algorithme

Même algo que LZ78 avec initialisation du dico avec la table ASCII, il y a donc 256 index dans le dictionnaire au départ
On n'affiche plus le symbole en cours à la sortie, mais on l'ajoute au mot en cours à la réinitialisation

11.3 LZW : ABBCCCDDDDEEEEE : 1

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8

On commence avec le dictionnaire ASCII, (1 octet, 8 bits sont nécessaires pour stocker le dictionnaire)
On lit le premier symbole A

11.4 LZW : ABBCCCDDDDEEEEE : 2

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A

A est dans le dictionnaire on l'ajoute au mot en cours

11.5 LZW : ABBCCCDDDDEEEEE : 3

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B

On lit le deuxième symbole B

11.6 LZW : ABBCCCDDDDEEEEE : 4

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B			9

On regarde si le mot en cours suffixé par le symbole est dans le dictionnaire.
AB n'est pas dans le dictionnaire, on affiche donc l'index du mot en cours en sortie A
On ajoute AB dans le dictionnaire avec l'index 256 (la taille du dico passe à 9)
On ajoute le symbole au mot en cours B

11.7 LZW : ABBCCCDDDDEEEEE : 5

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B		9

On lit le troisième symbole B

11.8 LZW : ABBCCCDDDDEEEEE : 6

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B

On regarde si le mot en cours suffixé par le symbole est dans le dictionnaire.
BB n'est pas dans le dictionnaire, on affiche donc l'index du mot en cours en sortie B
On ajoute BB dans le dictionnaire avec l'index 257
On ajoute le symbole au mot en cours B

11.9 LZW : ABBCCCDDDDEEEEE : 7

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C

On lit le quatrième symbole C

11.10 LZW : ABBCCCDDDDEEEEE : 8

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C

On regarde si le mot en cours suffixé par le symbole est dans le dictionnaire.
BC n'est pas dans le dictionnaire, on affiche donc l'index du mot en cours en sortie B
On ajoute BC dans le dictionnaire avec l'index 258
On ajoute le symbole au mot en cours C

11.11 LZW : ABBCCCDDDDEEEEE : 9

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C	C

On lit le cinquième symbole C

11.12 LZW : ABBCCCDDDDEEEEE : 10

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C	C	C
259, CC	C

CC n'est pas dans le dictionnaire, on affiche C en sortie
On ajoute CC dans le dictionnaire avec l'index 259
On ajoute le symbole au mot en cours C

11.13 LZW : ABBCCCDDDDEEEEE : 11

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C	C	C
259, CC	C	C

On lit le sixième symbole C

11.14 LZW : ABBCCCDDDDEEEEE : 12

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C	C	C
259, CC	C	C
	CC

CC est dans le dictionnaire, on ajoute le symbole C au mot en cours

11.15 LZW : ABBCCCDDDDEEEEE : 13

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C	C	C
259, CC	C	C
	CC	D

On lit le septième symbole D

11.16 LZW : ABBCCCDDDDEEEEE : 14

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C	C	C
259, CC	C	C
	CC	D	259
260, CCD	D

CCD n'est pas dans le dictionnaire, on affiche 259 correspondant à l'index du mot en cours CC en sortie
On ajoute CCD dans le dictionnaire avec l'index 260
On ajoute le symbole au mot en cours D

11.17 LZW : ABBCCCDDDDEEEEE : 15

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C	C	C
259, CC	C	C
	CC	D	259
260, CCD	D	D

On lit le huitième symbole D

11.18 LZW : ABBCCCDDDDEEEEE : 16

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C	C	C
259, CC	C	C
	CC	D	259
260, CCD	D	D	D
261, DD	D

DD n'est pas dans le dictionnaire, on affiche D en sortie
On ajoute DD dans le dictionnaire avec l'index 261
On ajoute le symbole au mot en cours D

11.19 LZW : ABBCCCDDDDEEEEE : 17

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C	C	C
259, CC	C	C
	CC	D	259
260, CCD	D	D	D
261, DD	D	D

On lit le neuvième symbole D

11.20 LZW : ABBCCCDDDDEEEEE : 18

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C	C	C
259, CC	C	C
	CC	D	259
260, CCD	D	D	D
261, DD	D	D
	DD

DD est dans le dictionnaire, on ajoute le symbole D au mot en cours

11.21 LZW : ABBCCCDDDDEEEEE : 19

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C	C	C
259, CC	C	C
	CC	D	259
260, CCD	D	D	D
261, DD	D	D
	DD	D

On lit le dixième symbole D

11.22 LZW : ABBCCCDDDDEEEEE : 20

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C	C	C
259, CC	C	C
	CC	D	259
260, CCD	D	D	D
261, DD	D	D
	DD	D	261
262, DDD	D

DDD n'est pas dans le dictionnaire, on affiche 261 en sortie
On ajoute DDD dans le dictionnaire avec l'index 262
On ajoute le symbole au mot en cours D

11.23 LZW : ABBCCCDDDDEEEEE : 21

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C	C	C
259, CC	C	C
	CC	D	259
260, CCD	D	D	D
261, DD	D	D
	DD	D	261
262, DDD	D	E

On lit le onzième symbole E

11.24 LZW : ABBCCCDDDDEEEEE : 22

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C	C	C
259, CC	C	C
	CC	D	259
260, CCD	D	D	D
261, DD	D	D
	DD	D	261
262, DDD	D	E	D
263, DE	E

DE n'est pas dans le dictionnaire, on affiche D en sortie
On ajoute DE dans le dictionnaire avec l'index 263
On ajoute le symbole au mot en cours E

11.25 LZW : ABBCCCDDDDEEEEE : 23

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C	C	C
259, CC	C	C
	CC	D	259
260, CCD	D	D	D
261, DD	D	D
	DD	D	261
262, DDD	D	E	D
263, DE	E	E

On lit le douzième symbole E

11.26 LZW : ABBCCCDDDDEEEEE : 24

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C	C	C
259, CC	C	C
	CC	D	259
260, CCD	D	D	D
261, DD	D	D
	DD	D	261
262, DDD	D	E	D
263, DE	E	E	E
264, EE	E

EE n'est pas dans le dictionnaire, on affiche E en sortie
On ajoute EE dans le dictionnaire avec l'index 264
On ajoute le symbole au mot en cours E

11.27 LZW : ABBCCCDDDDEEEEE : 25

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C	C	C
259, CC	C	C
	CC	D	259
260, CCD	D	D	D
261, DD	D	D
	DD	D	261
262, DDD	D	E	D
263, DE	E	E	E
264, EE	E	E

On lit le treizième symbole E

11.28 LZW : ABBCCCDDDDEEEEE : 26

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C	C	C
259, CC	C	C
	CC	D	259
260, CCD	D	D	D
261, DD	D	D
	DD	D	261
262, DDD	D	E	D
263, DE	E	E	E
264, EE	E	E
	EE

EE est dans le dictionnaire, on ajoute le symbole E au mot en cours

11.29 LZW : ABBCCCDDDDEEEEE : 27

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C	C	C
259, CC	C	C
	CC	D	259
260, CCD	D	D	D
261, DD	D	D
	DD	D	261
262, DDD	D	E	D
263, DE	E	E	E
264, EE	E	E
	EE	E

On lit le quatorzième symbole E

11.30 LZW : ABBCCCDDDDEEEEE : 28

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C	C	C
259, CC	C	C
	CC	D	259
260, CCD	D	D	D
261, DD	D	D
	DD	D	261
262, DDD	D	E	D
263, DE	E	E	E
264, EE	E	E
	EE	E	264
265, EEE	E

EEE n'est pas dans le dictionnaire, on affiche 264 en sortie
On ajoute EEE dans le dictionnaire avec l'index 265
On ajoute E au mot en cours

11.31 LZW : ABBCCCDDDDEEEEE : 29

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C	C	C
259, CC	C	C
	CC	D	259
260, CCD	D	D	D
261, DD	D	D
	DD	D	261
262, DDD	D	E	D
263, DE	E	E	E
264, EE	E	E
	EE	E	264
265, EEE	E	E

On lit le dernière symbole E

11.32 LZW : ABBCCCDDDDEEEEE : 30

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C	C	C
259, CC	C	C
	CC	D	259
260, CCD	D	D	D
261, DD	D	D
	DD	D	261
262, DDD	D	E	D
263, DE	E	E	E
264, EE	E	E
	EE	E	264
265, EEE	E	E
	EE

EE est dans le dictionnaire, on ajoute le symbole E au mot en cours

11.33 LZW : ABBCCCDDDDEEEEE : 31

Dictionnaire	Mot en cours	Symbole	Sortie	Taille dico
		A		8
	A	B	A
256, AB	B	B	B	9
257, BB	B	C	B
258, BC	C	C	C
259, CC	C	C
	CC	D	259
260, CCD	D	D	D
261, DD	D	D
	DD	D	261
262, DDD	D	E	D
263, DE	E	E	E
264, EE	E	E
	EE	E	264
265, EEE	E	E
	EE		264

On affiche l'index du mot en cours 264

11.34 LZW : Résumé

A, B, B, C, 259, D, 261, D, E, 264, 264
8 + 9*10 = 98 bits

11.35 LZW : Décodage

A, B, B, C, 259, D, 261, D, E, 264, 264

A : Lire A
B : Lire B, afficher A et ajouter AB au dico à l'index 256
B : Lire B, afficher B et ajouter BB au dico à l'index 257
C : Lire C, afficher B et ajouter BC au dico à l'index 258
259 : Lire 259, afficher C et ajouter CC au dico à l'index 259 (quand l'index est égal à la taille du dico en cours, on concatène le mot en cours ici C avec la première lettre du mot en cours ici C)
D : Lire D, afficher CC et ajouter CCD au dico à l'index 260
261 : Lire 261, afficher D et ajouter DD au dico à l'index 261
D : Lire D, afficher DD et ajouter DDD au dico à l'index 262
E : Lire E, afficher D et ajouter DE au dico à l'index 263
264 : Lire 264, afficher E et ajouter EE au dico à l'index 264
264 : Lire 264, afficher EE et ajouter EEE au dico à l'index 265
afficher EE

12 Rappel général

ABBCCCDDDDEEEEE : 15*8 = 120 bits
Entropie H(ABBCCCDDDDEEEEE) : 2.14925539717
Huffman : 49+33 = 82 bits
Huffman adaptatif : 5*8+32 = 72 bits
Codage arithmétique : 55+33 = 88 bits
RLE : 80 bits
RLE! : 96 bits
LZ77 : 78 bits
LZ78 : 98 bits
LZW : 98 bits