30 0 3MB
Sans Perte
Techniques de compression de données
Huff RLE
Objectifs
LZ*
• Optimiser les tailles de stockage
Avec perte TDC
• Optimiser le temps de transmission
Ondelettes Fractales
• Optimiser le temps d’accès
Par Type
Professeur M.QBADOU
1
Critères de classification des techniques de compression : Sans Perte
Huff
Taux de compression (en %) : 𝑵𝒃 𝒃𝒊𝒕𝒔 𝑭𝒊𝒄𝒉. 𝒄𝒐𝒎𝒑𝒓𝒆𝒔𝒔é 𝒕𝒄 = ∗ 𝟏𝟎𝟎 𝑵𝒃 𝒃𝒊𝒕𝒔 𝑭𝒊𝒄𝒉. 𝒔𝒐𝒖𝒓𝒄𝒆
RLE LZ* Avec perte TDC
Ondelettes Fractales Par Type
Vitesse de compression. Vitesse de décompression. Usage des ressources (en moyenne et maximal). Rapport qualité/taux (pour les méthodes avec pertes). Sécurité et robustesse.
Universalité, adaptabilité. le coût d’implémentation/usage (Parfois le choix est dicté par les contraintes économiques)
Professeur M.QBADOU
2
Data Compression- Entropy Sans Perte
Huff RLE LZ* Avec perte TDC
Ondelettes Fractales Par Type
1. Entropy is the measure of information content in a message. Messages with higher entropy carry more information than messages with lower entropy.
2. How to determine the entropy Find the probability p(x) of symbol x in the message The entropy H(x) of the symbol x is : H(x) = - p(x) * log2p(x)
3. The average entropy over the entire message is the sum of the entropy of all n symbols in the message
Data Compression Methods Sans Perte
Huff RLE LZ* Avec perte TDC
Ondelettes Fractales Par Type
1. Data compression is about storing and sending a smaller number of bits. 2. There’re two major categories for methods to compress data: lossless and lossy methods
Plan du cours
Huffman RLE
Sans Perte
Sans perte
LZ* TDC
Huff
Ondelettes RLE
Avec perte
Fractales
LZ* Avec perte TDC
Techniques de compression
Ondelettes Fractales
Type de données
Par Type
Professeur M.QBADOU
5
Lossless Compression Methods Sans Perte
Huff
1. In lossless methods, original data and the data after compression and decompression are exactly the same.
RLE LZ* Avec perte
2. Redundant data is removed in compression and added during decompression.
TDC
Ondelettes Fractales Par Type
3. Lossless methods are used when we can’t afford to lose any data: legal and medical documents, computer programs.
I. compression sans perte - Huffman Sans Perte
Huff RLE LZ* Avec perte TDC
Ondelettes Fractales Par Type
1. Principe du codeur Huffman Technique de compression sans perte par David Huffman, qui repose sur le codage statistique d'un fichier octet par octet. Plus les octets apparaissent souvent, plus les codes qui les remplacent sont courts. Codeur utilisé pour la compression du son MP3 et des images PNG et JPEG. L'algorithme parcourt les données d'un fichier et détermine le nombre de répétition de chaque octet (fréquence d’apparition). Ensuite, l'algorithme construit un arbre en commençant par ses feuilles jusqu'à sa racine. Les octets sont classés par ordre croissant de fréquence. Les nœuds sont ensuite liées deux par deux pour former les nœuds de l’arbre jusqu'à ce qu'il n'y ait plus qu'un seul nœud, soit la racine. Les nœuds sont formés par la somme des fréquences des nœuds-descendants directs. Attribuer aux branches gauches et droites de l'arbre les bits 0 et 1 respectivement. En fin, les octets compressés sont codés par les bits attribués aux liens, qui sont alignés en descendant du nœud racine jusqu'aux feuilles terminales. Professeur M.QBADOU
7
I. compression sans perte - Huffman Sans Perte
Huff
2. Lire le contenu original du fichier et calcul des fréquences Considérons le texte suivant :
RLE LZ*
"Eeeir eesy eens eanr klae."
Avec perte TDC
Ondelettes Fractales Par Type
Compter les occurrences de tous les caractères dans le texte et déterminer quels sont les caractères présents :
Char E e r i espace Professeur M.QBADOU
Freq. 1 8 2 1 4
Char
Freq.
Char
y s n a l
1 2 2 2 1
k .
Freq. 1 1
8
I. compression sans perte - Huffman Sans Perte
Huff RLE LZ* Avec perte
3. Créer les nœuds de l’arbre binaire. Chaque nœud contient le caractère et sa fréquence. 4. Placer les nœuds dans une queue de priorité La plus petite fréquence a la plus grande priorité dans la queue. On utilise le nœud suivant :
TDC
Ondelettes Fractales
public class NoeudHuffman { public char car;
Par Type
public int Frequence; public NoeudHuffman g, r;
… } PriorityQueue queue; Professeur M.QBADOU
9
I. compression sans perte - Huffman Sans Perte
La queue après l’insertion de tous les nœuds
Huff RLE LZ* Avec perte TDC
E
i
y
l
k
.
r
s
n
a
sp
e
1
1
1
1
1
1
2
2
2
2
4
8
Ondelettes Fractales Par Type
Professeur M.QBADOU
10
I. compression sans perte - Huffman Sans Perte
Huff RLE LZ* Avec perte TDC
Ondelettes
5. Construction de l’arbre d’huffman Tant que la queue contient 2 nœuds ou plus faire : Créer un nouveau nœud Défiler un nœud et le prendre fils gauche du nœud
Défiler un nœud et le prendre fils droit du nœud
Fractales
La fréquence du nouveau nœud est la somme des fréquences des nœud gauche et droit
Par Type
Enfiler le nouveau nœud dans la queue
Professeur M.QBADOU
11
I. compression sans perte - Huffman Sans Perte
5. Construction de l’arbre d’Huffman - Simulation
Huff RLE LZ* Avec perte TDC
y
l
k
i
E
.
s
r
n
a
sp
e
1
1
1
1
1
1
2
2
2
2
4
8
Ondelettes Fractales Par Type
Professeur M.QBADOU
12
I. compression sans perte - Huffman Sans Perte
5. Construction de l’arbre d’Huffman - Simulation
Huff RLE LZ* Avec perte TDC
k
i
E
.
s
r
n
a
sp
e
1
1
1
1
2
2
2
2
4
8
Ondelettes Fractales
2
Par Type
Professeur M.QBADOU
y
l
1
1
13
I. compression sans perte - Huffman Sans Perte
5. Construction de l’arbre d’Huffman - Simulation
Huff RLE LZ* Avec perte TDC
k
i
E
.
s
r
n
a
1
1
1
1
2
2
2
2
2
sp
e
4
8
Ondelettes Fractales Par Type
Professeur M.QBADOU
y
l
1
1
14
I. compression sans perte - Huffman Sans Perte
5. Construction de l’arbre d’Huffman - Simulation
Huff RLE LZ* Avec perte TDC
E
.
s
r
n
a
1
1
2
2
2
2
2
sp
e
4
8
Ondelettes Fractales Par Type
2
Professeur M.QBADOU
k
i
1
1
y
l
1
1
15
I. compression sans perte - Huffman Sans Perte
5. Construction de l’arbre d’Huffman - Simulation
Huff RLE LZ* Avec perte TDC
E
.
s
r
n
a
1
1
2
2
2
2
2
2
sp
e
4
8
Ondelettes Fractales Par Type
Professeur M.QBADOU
y
l
k
i
1
1
1
1
16
I. compression sans perte - Huffman Sans Perte
5. Construction de l’arbre d’Huffman - Simulation
Huff RLE LZ* Avec perte TDC
s
r
n
a
2
2
2
2
2
2
sp
e
4
8
Ondelettes Fractales Par Type
2
E
.
1
1
Professeur M.QBADOU
y
l
k
i
1
1
1
1
17
I. compression sans perte - Huffman Sans Perte
5. Construction de l’arbre d’Huffman - Simulation
Huff RLE LZ* Avec perte TDC
s
r
n
a
2
2
2
2
2
2
2
sp
e
4
8
Ondelettes Fractales Par Type
Professeur M.QBADOU
y
l
k
i
E
.
1
1
1
1
1
1
18
I. compression sans perte - Huffman Sans Perte
5. Construction de l’arbre d’Huffman - Simulation
Huff RLE LZ* Avec perte TDC
n
a
2
2
2
2
2
sp
e
4
8
Ondelettes Fractales Par Type
y
l
k
i
E
.
1
1
1
1
1
1
4
s
r
2
2
Professeur M.QBADOU
19
I. compression sans perte - Huffman Sans Perte
5. Construction de l’arbre d’Huffman - Simulation
Huff RLE LZ* Avec perte TDC
n
a
2
2
sp 2
2
2
e
4
8
4
Ondelettes Fractales Par Type
y
l
k
i
E
.
s
r
1
1
1
1
1
1
2
2
Professeur M.QBADOU
20
I. compression sans perte - Huffman Sans Perte
5. Construction de l’arbre d’Huffman - Simulation
Huff RLE LZ* Avec perte
sp
TDC
2
2
2
e
4
8
4
Ondelettes Fractales Par Type
y
l
k
i
E
.
s
r
1
1
1
1
1
1
2
2 4
Professeur M.QBADOU
n
a
2
2 21
I. compression sans perte - Huffman Sans Perte
5. Construction de l’arbre d’Huffman - Simulation
Huff RLE LZ* Avec perte
sp
TDC
2
2
2
e
4
4
8
4
Ondelettes Fractales Par Type
y
l
k
i
E
.
s
r
1
1
1
1
1
1
2
2
Professeur M.QBADOU
n
a
2
2
22
I. compression sans perte - Huffman Sans Perte
5. Construction de l’arbre d’Huffman - Simulation
Huff RLE
sp
LZ*
2
Avec perte
e
4
4
8
4
TDC
Ondelettes
E
Fractales
1
. 1
s 2
r 2
n
a
2
2
4
Par Type
2
Professeur M.QBADOU
2
y
l
k
i
1
1
1
1 23
I. compression sans perte - Huffman Sans Perte
5. Construction de l’arbre d’Huffman - Simulation
Huff RLE
sp
LZ*
2
Avec perte
e
4
4
4
4
8
TDC
Ondelettes
E
.
s
r
Fractales
1
1
2
2
n
a
2
2
2
2
Par Type
Professeur M.QBADOU
y
l
k
i
1
1
1
1
24
I. compression sans perte - Huffman Sans Perte
5. Construction de l’arbre d’Huffman - Simulation
Huff RLE
e
LZ*
4
Avec perte
4
4
8 6
TDC
Ondelettes
s
r
Fractales
2
2
n
a
2
2
2
2
sp 2
Par Type
Professeur M.QBADOU
y
l
k
i
1
1
1
1
4
E
.
1
1
25
I. compression sans perte - Huffman Sans Perte
5. Construction de l’arbre d’Huffman - Simulation
Huff RLE
e
LZ*
4
Avec perte
4
4
8
6
TDC
Ondelettes Fractales
s 2
r 2
n
a
2
2
sp 2
2
2
Par Type
Professeur M.QBADOU
4
y
l
k
i
E
.
1
1
1
1
1
1
26
I. compression sans perte - Huffman Sans Perte
5. Construction de l’arbre d’Huffman - Simulation
Huff RLE
e
LZ*
4
Avec perte
8
6
TDC
sp
Ondelettes
2
Fractales
2
2
Par Type
4
y
l
k
i
E
.
1
1
1
1
1
1
Professeur M.QBADOU
8
4
4
s
r
n
a
2
2
2
2 27
I. compression sans perte - Huffman Sans Perte
5. Construction de l’arbre d’Huffman - Simulation
Huff RLE
e
LZ*
4
Avec perte
8
6
8
TDC
sp
Ondelettes
2
Fractales
2
2
Par Type
y
l
k
i
E
1
1
1
1
1
Professeur M.QBADOU
4
4
. 1
4
s
r
n
a
2
2
2
2
28
I. compression sans perte - Huffman Sans Perte
5. Construction de l’arbre d’Huffman - Simulation
Huff RLE LZ* Avec perte
e 8
10
8
TDC
Ondelettes
4
Fractales Par Type
4
4
s
r
n
a
2
2
2
2
Professeur M.QBADOU
6
sp 2
2
2
4
y
l
k
i
E
.
1
1
1
1
1
1 29
I. compression sans perte - Huffman Sans Perte
5. Construction de l’arbre d’Huffman - Simulation
Huff RLE LZ* Avec perte
e 8
8
10
TDC
Ondelettes
4
Fractales Par Type
4
4
s
r
n
a
2
2
2
2
Professeur M.QBADOU
6 sp
2
2
2
4
y
l
k
i
E
.
1
1
1
1
1
1 30
I. compression sans perte - Huffman Sans Perte
5. Construction de l’arbre d’Huffman - Simulation
Huff RLE LZ*
10
Avec perte
16
TDC
Ondelettes
4
e
6
8
Fractales
8
sp
Par Type
2
2
2
4
4
4
y
l
k
i
E
.
s
r
n
a
1
1
1
1
1
1
2
2
2
2
Professeur M.QBADOU
31
I. compression sans perte - Huffman Sans Perte
5. Construction de l’arbre d’Huffman - Simulation
Huff RLE LZ*
16
10
Avec perte TDC
e
Ondelettes
4
6
8
Fractales
8
sp
Par Type
2
2
2
4
4
4
y
l
k
i
E
.
s
r
n
a
1
1
1
1
1
1
2
2
2
2
Professeur M.QBADOU
32
I. compression sans perte - Huffman Sans Perte
5. Construction de l’arbre d’Huffman - Simulation
Huff RLE
26 LZ* Avec perte
10
16
TDC
Ondelettes
4
Fractales
e
6
8
Par Type
8
sp 2
2
2
4
4
4
y
l
k
i
E
.
s
r
n
a
1
1
1
1
1
1
2
2
2
2
Professeur M.QBADOU
33
I. compression sans perte - Huffman Sans Perte
5. Construction de l’arbre d’Huffman - Simulation
Huff RLE
26 LZ* Avec perte
10
16
Après enfilement de ce nœud, il ne reste qu’un seul nœud à gauche dans la queue de priorité
TDC
Ondelettes
4
Fractales
e
6
8
Par Type
8
sp 2
2
2
4
4
4
y
l
k
i
E
.
s
r
n
a
1
1
1
1
1
1
2
2
2
2
Professeur M.QBADOU
34
I. compression sans perte - Huffman Sans Perte
6. Implémentation : Classe PriorityQueue :
Huff
Description
RLE LZ* Avec perte TDC
Ondelettes Fractales Par Type
Professeur M.QBADOU
35
I. compression sans perte - Huffman Sans Perte
6. Implémentation : Classe PriorityQueue :
Huff
Constructeurs :
RLE LZ* Avec perte TDC
Ondelettes Fractales Par Type
Professeur M.QBADOU
36
I. compression sans perte - Huffman Sans Perte
6. Implémentation :
Huff
Classe PriorityQueue
RLE
Méthodes
LZ* Avec perte TDC
Ondelettes Fractales Par Type
Professeur M.QBADOU
37
I. compression sans perte - Huffman Sans Perte
Huff
Implémentation : Calcul de la table des codes binaires-Classe HashTable
Utiliser l’interface Map implémentée par la classe HashTable : Les méthode de l’interface Map :
RLE LZ* Avec perte TDC
Ondelettes Fractales Par Type
Professeur M.QBADOU
38
I. compression sans perte - Huffman Sans Perte
Les Constructeurs de la classe HashTable :
Huff RLE LZ* Avec perte
Les méthodes de la classe Hashtable
TDC
Ondelettes Fractales Par Type
Professeur M.QBADOU
39
I. compression sans perte - Huffman Sans Perte
Huff RLE LZ* Avec perte TDC
Ondelettes Fractales Par Type
Implémentation : Gestion des fichiers :
Classes à utiliser : FileWriter : FileWriter fw=new FileWriter(new File(nomFichier)); fw.write(objString); BufferedReader, FileReader : BufferedReader in=new Bufferedreader(new FileReader(new File(nomFichier))); objString =in.readline(); FileInputStream : FileInputStream in=new FileInputStream(new File(NomFichier)); byte b=(byte)in.read(); FileOuputStream : FileOutputStream out=new FileOutputStream(new File(NomFichier)); out.write(Short.parseShort(codes.substring(i,i+8),2))
Professeur M.QBADOU
40
I. compression sans perte - Huffman Sans Perte
Huff RLE LZ* Avec perte TDC
Ondelettes Fractales Par Type
Implémentation : Ossature du code : Classe NoeudHuffman :
package compression; import java.util.Comparator; public class NoeudHuff implements Comparable, Comparator{ char x; int f; NoeudHuff g,d; NoeudHuff(){} NoeudHuff(char x,int f){this.x=x; this.f=f; g=d=null;} NoeudHuff(NoeudHuff g,NoeudHuff d){ f=g.f+d.f; this.g=g; this.d=d; } public int compareTo(NoeudHuff n) { if(f==n.f)return x==n.x?0:(x=1) .
Ecrire un programme qui décompressera et affichera cette image. Professeur M.QBADOU
48
III . Compression sans perte - LZ* Sans Perte
1.
Historique Les méthodes de compression LZ* de Abraham Lempel et Jacob Ziv, sont dites de type dictionnaire aussi appelées algorithmes à substitution de facteurs.
Huff RLE
Les différentes variantes sont dans l’ordre :
LZ* Avec perte
• L’algorithme LZ77,
TDC
• L’algorithme LZSS, version amélioré de LZ77 par Storer et Szymanski (la recherche des séquences dans le dictionnaire est réduite logarithmique ment)
Ondelettes
• Enfin vient l’algorithme LZ78, plus connu sous le nom LZW, amélioration faite par Terry Welch en 1984 de LZSS par le fait que les séquences sont rangées dans une arborescence.
Fractales Par Type
2.
Principe Le principe est fondé sur le fait qu’une séquence de caractères peut apparaître plusieurs fois dans un fichier. L’algorithme LZW de compression consiste à émettre à la place des séquences, les adresses de ces séquences dans un dictionnaire généré à la volée.
Professeur M.QBADOU
49
III . Compression sans perte - LZ* Sans Perte
Huff RLE LZ* Avec perte TDC
Ondelettes Fractales Par Type
3. Avantages par rapport aux méthodes statistiques Le fichier comprimé ne stocke pas le dictionnaire, ce dernier est automatiquement généré lors de la décompression. Contrairement aux méthodes statistiques qui utilisent la probabilité de présence sur un ensemble de taille fixe de symboles, l’algorithme LZW représente un algorithme d’apprentissage, puisque les séquences répétitives de symboles sont dans un premier temps détectées puis compressées seulement lors de leurs prochaines occurrences. Le taux de compression est dépendant de la taille du fichier. Plus la taille est importante, et plus le taux de compression l’est aussi. Il permet le compactage à la volée, puisqu’il n’y a pas à lire le fichier au préalable, il compresse les séquences de symboles au fur et à mesure.
Professeur M.QBADOU
50
III . Compression sans perte - LZ* Sans Perte
Huff RLE LZ* Avec perte TDC
Ondelettes Fractales Par Type
4. L’algorithme de compression LZW Principe : • L’objectif de l’algorithme de compression LZW est de construire un dictionnaire où chaque séquence sera désignée par une adresse dans celui ci. • Chaque séquence ne s’y trouvant pas y est rajoutée. Au final, on se retrouve avec une suite d’entiers, des adresses pointant vers une séquence contenue dans le dictionnaire. • Le dictionnaire est donc un tableau dans lequel sont rangées des séquences de symboles de taille variable, repérées par leurs adresses (leur position dans le tableau). • La taille de ce dictionnaire n’est pas fixe et les premières adresses de 0 à 255 du dictionnaire contiennent les codes ASCII. Les séquences ont donc des adresses supérieures à 255.
Professeur M.QBADOU
51
III . Compression sans perte - LZ* Sans Perte
4. L’algorithme de compression LZW Algorithme LZW_Compression
Huff
Données : Type_Dictionnaire Dico TypeFichier FichierSr Résultat : TypeFichier FichierCpr Début s = LireOctetFichier(FichierSr) Tant Que Non FinFichier(FichierSr) t=LireOctetFichier(FichierSr) u=Concanténer(s,t) Si EstDansDicto(Dico,u) Alors s=u Sinon AjouterDansDico(Dico,u) EcrireFichier(FichierCpr,Adresse(Dico,s)) s=t Fin Si Fin Tant Que EcrireFichier(FichierCpr, Adresse(Dico,s)) Fin
RLE LZ* Avec perte TDC
Ondelettes Fractales Par Type
Professeur M.QBADOU
52
III . Compression sans perte - LZ* Sans Perte
Huff RLE LZ* Avec perte TDC
Ondelettes Fractales Par Type
5. Exemple d’utilisation de l’algorithme de compression LZW A l’aide de l’algorithme LZW, nous voulons compresser la séquence suivante : "SISI-ET-ISIS" On lit donc le premier caractère soit ’S’. Puis on lit le suivant : ’I’. On forme la séquence u=S+I soit ’SI’, puisque celle ci n’est pas présente dans le dictionnaire, on l’ajoute dans le dictionnaire. Cette séquence aura l’adresse 256, première séquence située dans le dictionnaire après la table ASCII. Enfin on attribue l’adresse de s (valeur ASCII de ’S’) dans le fichier soit 83 ou (1010011 en binaire). On continue ensuite avec le caractère suivant. La compression effective a lieu lorsque qu’on rencontrera pour la seconde fois une paire (’SI’ par exemple) déjà présente dans le dictionnaire. Dans ce cas on émettra l’adresse de la séquence ’SI’ et non l’adresse de la séquence ’S’ et de la séquence ’I’, on ajoutera par la suite dans le dictionnaire la séquence de 3 caractères (soit ’SIS’ dans notre exemple). Professeur M.QBADOU
53
III . Compression sans perte - LZ* Sans Perte
Huff RLE
5. Exemple d’utilisation de l’algorithme de compression LZW tableau résumant les opérations effectuées sur l’exemple lors du déroulement de l’algorithme LZW de compression :
LZ* Avec perte TDC
Ondelettes Fractales Par Type
le dictionnaire résultant de l’algorithme :
Professeur M.QBADOU
54