Gestion de Fichiers

GF-7: Compression des Donnees

(Base sur la section 6.1 de Folk, Zoellick & Riccardi, File Structures, An Object-Oriented Approach with C++; ainsi que sur les notes du cours 308-251 de McGill, donne en 1997)

2

Resume du Cours de cette Semaine

Une vue generale sur la compression des donnees

Compression des redondances: Utilisation d’une notation differente Suppression de repetition de sequences

Affectation de codes a longueur variable Encodage Huffman (pack et unpack en Unix) Encodage Lempel-Ziv (compress et

uncompress en Unix) Techniques de compression irreversible

3

Vue Generale sur la Compression des Donnees

La compression des donnees consiste a coder les informations d’un fichier de facon a reduire leur taille.

Question: Pourquoi reduire la taille de fichiers? Reponse:

Afin d’utiliser moins de storage, c.a.d., reduire le cout,

Afin de rendre la transmission plus efficace: ou bien en diminuant le temps d’acces ou en utilisant le meme temps d’acces mais avec un bandwith plus petit et moins cher.

Afin de traiter le fichier de facon sequentielle plus rapidement.

4

Compression des Redondances I: Utilisation d’une notation differente

Dans notre discussion sur les enregistrements de personnes, on a cree un champ specifiant l’etat dans lequel la personne reside. Les etats (aux US) sont specifies en utilisant 2 lettres de l’alphabet. E.g., OK pour Oklahoma. On a donc reserve 2 octets pour ce champs.

Question: Cela etait-il vraiement necessaire? Reponse: Non: Puisqu’il n’y a que 50 etats, on peut

tous les encoder avec 6 bits, et sauvegarder, ainsi, un octet par champ specifiant l’etat.

Quels sont les desavantages de cette solution?

5

Compression des Redondances I: Utilisation d’une notation differente

Desavantages: Les codes ne sont pas comprehensible Il y a un cout associe a l’encodage et au

decodage (le traitement des fichiers prend plus de temps)

La complexite du Logiciel est accrue car il est desormais necessaire d’avoir un module d’encodage et de decodage.

6

Compression des Redondances II: Suppression de repetition de Sequences

Lorsque les donnees sont representees dans un tableau tres epars, on peut utiliser un mode de compression appele: run-length encoding.

Procedure: Lire le tableau sequentiellement. Si une valeur apparait plus d’une fois en succession,

remplacer la repetition par: Un indicateur de repetition special, La valeur repetee, et Le nombre de fois qu’elle est repetee.

Il n’est pas garantit que de l’espace sera effectivement gagne!

7

Codage Huffman Veuillez supposer que tous les messages

envoyes d’une source a une destination contiennent les lettres a, b, c, d et e representees par les probabilites .05, .2, .4, .17 et .18, respectivement.

Notre but est d’encoder chaque caractere en une sequence de 1s et 0s de maniere a ce qu’aucun code representant un caractere ne represente le prefix d’un autre. Example: on ne peut pas avoir les codes “110” et “1101” car “110” est un prefix de “1101”. Pourquoi?

8

Solution: Arbre Huffman suivi du Codage

a d.05 .17

.22

e b.18 .2

.38

.6.4

10 1

0 1

0 1 0 1

c

Code

a= 100b= 111c= 0d=101e=110

9

Definitions et Proprietes des Arbres Huffmans

Definition: Un arbre Huffman est un arbre binaire qui minimise la somme des f(i)D(i) de toutes les feuilles i, ou f(i) est la probabilite de la feuille i et D(i) est la longueur du chemin allant de la racine de l’arbre a la feuille i.

Proprietes: chaque node interne a deux enfants Les elements ayant les probabilite les plus petites

sont les elements places le plus loin de la racine, Les elements ayant les 2 probabilites les plus

petites sont frere et soeur.

10

Algorithme Hu-Tucker pour construire un arbre Huffman I Soit un heap compose d’elements,elem,

du type suivant:

lettre

probabilite

Gauche Droite

11

Revisions sur les (min) Heaps (voir livre pp.312-318)

Revisions: Un heap est un arbre binaire aux 3 proprietes suivantes: Chaque noeud a une seule cle, et cette cle est plus

large ou egale a la cle de son parent. L’arbre est complet, ce qui veut dire que toutes ses

feuilles se trouvent sur deux niveaux au plus et que toutes les cles du niveau inferieur sont sur la gauche.

Le heap peut etre mis en storage dans un tableau de facon a ce que la racine soit sauvegarde a la position 1 et que les enfants du noeud a la position i soient sauvegardes aux positions 2i et 2i+1. Inversement, l’index du parent du noeud j est floor(j/2).

12

Revisions sur les (min) Heaps: Insert (voir livre pp.312-318)

A

B C

E K I D

G F

A B C E K I D G F H

H

13

Revisions sur les (min) Heaps: Remove (voir livre pp.312-318)

A

B C

E H I D

G F

A B C E H I D G F

DeleteMin

1

2

5

3

4

14

Algorithme Hu-Tucker pour construire un arbre Huffman II

Former un Heap a partir des lettres de l’alphabet et de leures probabilites (a, fa), (b, fb),….

For i = n+1 to 2n –1 do New(Elem(i)) Elem(i). left Remove(Heap) Elem(i). right Remove(Heap) fi fleft + fright

Insert ( Elem(i, fi ), Heap ) Return

15

Autres Proprietes des Codes Huffman

Les Codes Huffmans donnent des nombres de bits (moyens) par caractere optimaux par rapport a toutes les autres codes “prefix” (les codes dans lesquels aucun codage est le prefixe d’un autre codage). Neanmoins, il existe d’autres methodes de codage plus efficaces. Example: codage Lempel-Ziv.

L’algorithme Hu-Tucker est l’example d’un algorithme gourmand (greedy). Il est execute en temps O(n log n).

La longueur moyenne du code d’une lettre est: i fi * longueur(code pour caractere i)

16

Encodage Lempel-Ziv Idee: la compression d’un nombre arbitraire de

caracteres peut etre obtenue en formant systematiquement une nouvelle chaine de caraceteres basee sur une chaine de caracteres deja rencontree plus un nouveau caractere. Cette nouvelle chaine peut etre utilisee de la meme facon par la suite.

Si le message original est court, cet encodage peut prendre plus d’espace que le message original. Neanmoins, pour des documents longs, il est proche de l’encodage parfait (a longueur optimale).

17

Example d’encodage Lempel-Ziv aaababbbaaabaaaaaaabaabb

|a|aa|b|ab|bb|aaa|ba|aaaa|aab|aabb

0 1 2 3 4 5 6 7 8 9 10

0a|1a|0b|1b|3b|2a|3a| 6a | 2b | 9b

Division:

index

Codage

18

Comment construire des Codes Lempel-Ziv?

Etape 1: Traverser le texte a coder et le diviser en segments qui representent des chaines representables par une chaine precedente (un prefix) + 1 caractere.

Etape 2: Indexer chacuns des segments obtenus. Les encoder en utilisant une representation binaire minimale. Il faut commencer avec le segment vide().

Etape 3: traduire le texte segment par segment en utilisant: 1) le code pour le segment prefixe et le nouveau caractere necessaire a la creation du nouveau segment.

19

Nombre de Bits necessaire pour Coder un Texte I

Chaque segment de texte est represente par un entier + une lettre de l’alphabet.

Au pire, le nombre de bits necessaire pour representer chaque entier contenu a la position n est egal au nombre de bits necessaire pour representer la position n-1.

Par example, le nombre de bits necessaire pour representer l’entier 6 de la position 8 est egal a 3 car il faut 3 bits pour exprimer l’entier 7 en notation binaire.

Chaque caractere occuppe 8 bits car il est represente en format ASCII.

20

Nombre de Bits necessaire pour Coder un Texte II

Dans notre example (diapo 17), on a donc besoin de

((0+8)+(1+8)+2*(2+8)+4*(3+8)+2*(4+8)) = 105 Etant donne que le texte original etait compose de 24

caracteres, prenant chacun 8 bits, l’encodage Lempel-Ziv ne nous offre pas de reduction car 24 * 8 – 105 = 87, une reduction de 45%!!!

Theoretiquement: dans des fichiers contenant des symboles independents et tires au hasard avec les probabilites p1, p2, p3, etc… le nombre anticipe de bits necessaire par symbole tend vers l’entropie:

pi log2 (1/pi) L’encodage Huffman atteint ce resultat, mais il doit connaitre les probabilites de chaque caractere. Lempel-Ziv l’atteint egalement mais sans connaitre les probabilites.

21

Comment Decoder les textes encodes?

Une maniere efficace de reconstituer un texte code est de construire un arbre de recherche digital qui nous permet de decoder le texte en un seul passage.

Example d’un arbre de recherche digital partiel:

0

1

2

6

4

3

5

a

a

a

b

b

b

22

Techniques de Compression Irreversible

La compression irreversible est basee sur la supposition qu’un certain montant d’information peut etre sacrifie [la compression irreversible s’appelle egalement la reduction d’entropie.].

Example: on peut reduire une image d’un format 400 x 400 pixels a 100 x 100 pixels. La nouvelle image contient 1 pixel pour chacun des 16 pixels de l’image originale.

Il est, d’habitude, impossible de determiner les 16 pixels originaux du nouveau pixel obtenu.

Bien entendu, dans les fichiers de donnees, la compression irreversible n’est pas tres utile. Par contre, elle sert beaucoup dans le traitement des images et de la parole.