|
|
|
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) |
|
|
|
|
|
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 |
|
|
|
|
|
|
|
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. |
|
|
|
|
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? |
|
|
|
|
|
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. |
|
|
|
|
|
|
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! |
|
|
|
|
|
|
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, .1t 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? |
|
|
|
|
|
|
|
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 frequence ou le poids 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 frequences les plus
petites sont les elements places le plus loin de la racine, |
|
Les elements ayant les 2 frequences les plus
petites sont frere et soeur. |
|
|
|
|
Soit un heap compose d’elements,elem, du type
suivant: |
|
|
|
|
|
|
|
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). |
|
|
|
|
|
|
|
|
|
|
|
Former un Heap a partir des lettres de
l’alphabet et de leures frequences (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 |
|
|
|
|
|
|
|
|
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 gourmant (greedy). Il est execute en temps O(n log n). |
|
La longueur moyenne du code d’une lettre est: |
|
Si fi * longueur(code pour
caractere i) |
|
|
|
|
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). |
|
|
|
|
aaababbbaaabaaaaaaabaabb |
|
|
|
e|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 |
|
|
|
|
|
|
|
|
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(e). |
|
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. |
|
|
|
|
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. |
|
|
|
|
|
|
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: |
|
S 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. |
|
|
|
|
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: |
|
|
|
|
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. |
|
Notes