Gestion de Fichiers

Compression des Données

2

Plan du cours d’aujourd’hui

Une vue générale sur la compression des données

Réduction des redondances: Utilisation d’une notation différente Suppression de répétition de séquences

Codes à longueur variable Code Huffman (pack /unpack en Unix) Code Lempel-Ziv (compress /uncompress en Unix)

Compression irreversible

3

Vue générale Comprimer des données c’est encoder celles-

ci de façon à réduire leur taille. Pourquoi reduire la taille de fichiers?

Afin d’utiliser moins de stockage et réduire le cout

Afin de rendre la transmission plus efficace: ou bien en diminuant le temps d’accès ou en utilisant le même temps d’accès mais avec un débit (“bandwidth”) plus petit et moins cher

Afin de traiter le fichier de façon séquentielle plus rapidement

4

Utilisation d’une notation différente

Un exemple: en créant des enregistrements de personnes, on crée un champ spécifiant l’état dans lequel la personne réside. Les états (aux USA) sont spécifiés en utilisant 2 lettres de l’alphabet. Ainsi, OK est utilisé pour Oklahoma. On réserve 2 octets pour ce champ.

Question: Cela était-il vraiment nécessaire? Réponse: Non: Puisqu’il n’y a que 50 états, on

peut tous les encoder avec 6 bits, et sauvegarder, ainsi, un octet par champ spécifiant l’état.

Quels sont les désavantages de cette solution?

5

Utilisation d’une notation différente (suite)

Désavantages: Les codes ne sont pas compréhensible Il y a un coût associé à l’encodage et au

décodage (le traitement des fichiers prend plus de temps)

La complexité du Logiciel est accrue car il est désormais nécessaire d’avoir un module d’encodage et de décodage.

6

Suppression de répetition de séquences

Lorsque les données sont represéntées dans un tableau très épars, on utilise souvent l’encodage de plage (“run-length encoding”).

Procédure: Lire le tableau séquentiellement et copier les valeurs dans

un fichier séquentiellement, sauf s’il y a répétition de séquence.

Si une valeur apparaît plus d’une fois en (longue) succession, remplacer la répétition par 3 octets:

Un indicateur de répetition spécial, La valeur repétée, et Le nombre de fois qu’elle est répétée (jusqu’à256 fois).

Il n’y a pas de garantie de gain d’espace (quand?) !

7

Encodage de plage: application En général, les images composées à partir de

surfaces contiennent de larges plages de couleurs uniformes représentées par une valeur de pixel précise (p.ex. le fond noir = 0).

Plutôt que de stocker tous les pixels de la plage, il est préférable de les représenter d'une façon bien plus compacte.

En balayant l’image ligne par ligne, il est possible d‘appliquer l’encodage de plage sur toutes les séquences de points qui ont la même couleur (Voir Fig. 6.1)

8

Encodage de plage: exemples Indicateur de répétition: FF (hexadécimal) ou 11111111 (binaire) Séquence: 22 23 24 24 24 24 24 24 24 25 26 26 26 26 26 26 25

24 Encodage de plage: 22 23 FF 24 07 25 FF 26 06 25 24 Séquence: 07 08 08 23 23 24 24 23 23 25 25 Encodage de plage (plus long que l’original !!): 07 FF 08 02 FF 23 02 FF 24 FF 23 02 FF 25 02

9

Codage Huffman Réminiscent du fameux code Morse. Supposez les messages envoyés d’une source

à une destination contiennent les lettres a, b, c, d qui sont représentées par les probabilités 0.05, 0.2, 0.4, 0.17 et 0.18, respectivement.

Notre but est d’encoder chaque caractère en une séquence de 1s et 0s de manière à ce qu’aucun code représentant un caractère ne soit le préfixe d’un autre code. Ainsi, on ne peut avoir les codes “110” et “1101” car “110” préfixe de “1101”.

10

Arbre Huffman suivi du codage

a do.05 0.17

0.22

e b0.18 0.2

0.38

0.60.4

10 1

0 1

0 1 0 1

c

Code

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

11

Définitions et propriétés Definition: Un arbre Huffman est un arbre binaire

qui minimise la somme des f(i)D(i) de toutes les feuilles i, où f(i) est la probabilité de la feuille i et D(i) est la longueur du chemin allant de la racine de l’arbre à la feuille i.

Propriétés: chaque node interne a deux enfants Les éléments ayant les probabilité les plus petites

sont les éléments placés le plus loin de la racine, Les éléments ayant les 2 probabilités les plus

petites sont frère et soeur.

12

Algorithme Hu-Tucker: structure de donnée

Soit un tas (“heap”) composé d’éléments du type suivant:

clé

probabilité

Gauche Droite

13

Revision sur les heaps (FZR pp.312-318)

Un heap est un arbre binaire aux propriétés suivantes: Chaque noeud a une seule clé, et cette clé est

plus large ou égale à la clé 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 clés du niveau inférieur sont sur la gauche.

Le heap peut être mis en stockage dans un tableau de façon à ce que la racine soit sauvegardé à la position 1 et que les enfants du noeud à la position i soient sauvegardés aux positions 2i et 2i+1. Inversement, l’index du parent du noeud j est floor(j/2).

14

Revisions sur les heaps: “insert”

A Voir Fig. 8.18 B C

E K I D

G F

A B C E K I D G F H

H

15

Revisions sur les heaps: “delete”

A

B C

E H I D

G F

A B C E H I D G F

DeleteMin

1

2

5

3

4

16

Algorithme Hu-Tucker Former un Heap à partir des lettres de l’alphabet

et de leurs probabilités (a, fa), (b, fb),…. For i = n+1 to 2n –1 do

New(Elem(i)) Elem(i). left DeleteMin(Heap) Elem(i). right DeleteMin(Heap) fi fleft + fright

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

17

Autres propriétés des codes Huffman

Les Codes Huffmans donnent des nombres de bits (moyens) par caractere optimaux par rapport à toutes les autres codes à préfixe. Néanmoins, il existe d’autres méthodes de codage plus efficaces, dont le codage Lempel-Ziv.

L’algorithme Hu-Tucker est l’example d’un algorithme gourmand (greedy). Son temps est O(n log n) (le temps pour construire le heap).

La longueur moyenne du code est: i fi * longueur(code pour caractere i)

18

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

caractères peut être obtenue en formant systématiquement une nouvelle chaîne de caractères basée sur une chaîne de caractères déjà rencontrée plus un nouveau caractère. Cette nouvelle chaîne peut être utilisée de la meme façon par la suite.

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

19

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

20

Construction des codes Lempel-Ziv?

Etape 1: Traverser le texte à coder et le diviser en segments qui représentent des chaînes représentables par une chaîne précédente (un préfixe) + 1 caractère.

Etape 2: Indexer chacuns des segments obtenus. Les encoder en utilisant une représentation 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 préfixe et le nouveau caractàre nécessaire à la création du nouveau segment.

21

Nombre de bits nécessaire pour coder

Chaque segment de texte est représenté par un entier + une lettre de l’alphabet.

Au pire, le nombre de bits nécessaire pour représenter chaque entier contenu à la position n est égal au nombre de bits nécessaire pour représenter la position n-1.

Par example, le nombre de bits nécessaire pour représenter l’entier 6 de la position 8 est égal à 3 car il faut 3 bits pour exprimer l’entier 7 en notation binaire.

Chaque caractère occuppe 8 bits car il est représenté en format ASCII.

22

Nombre de bits nécessaire pour coder (suite)

Dans notre example plus haut, on a donc besoin de

((0+8)+(1+8)+2*(2+8)+4*(3+8)+2*(4+8)) = 105 Etant donné que le texte original était composé de 24

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

Théoretiquement: dans des fichiers contenant des symboles indépendents et tirés au hasard avec les probabilités p1, p2, p3, etc… le nombre anticipé de bits nécessaire par symbole tend vers l’entropie:

pi log2 (1/pi) Huffman atteint ce résultat, mais il doit connaìtre les probabilités de chaque caractère. Lempel-Ziv l’atteint également mais sans connaître les probabilités.

23

Comment decoder un texte encodés?

Une manière efficace de reconstituer un texte codé est de construire un arbre de recherche digital qui nous permet de décoder 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

24

Compression irreversible La compression irreversible est basée sur la

supposition qu’un certain montant d’information peut être sacrifié [la compression irreversible s’appelle également la réduction d’entropie].

Example: on peut réduire une image d’un format 400 x 400 pixels à 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 déterminer les 16 pixels originaux du nouveau pixel obtenu.

Bien entendu, dans les fichiers de données, la compression irreversible n’est pas très utile. Par contre, elle sert beaucoup dans le traitement des images et de la parole (pourquoi???).