Compression Sans PerTe [PDF]

Zitiervorschau

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