Outils Informatique Compression Compression statistique

E. Jeandel

Description

Outils InformatiqueCompression statistiqueE. JeandelEmmanuel.Jeandel at lif.univ-mrs.frE. Jeandel, Lif Outils InformatiqueCompressionCompression statistique 1/16CompressionUn outil de compression est la donnée de deux outils :Un programme de compression qui prend un flux de données etqui le convertit un en flux compressé ;Un programme de décompression qui prend un flux compressé etle décompresse.Deux types de compressionUne fois décompressé, on réobtient le flux d’origine (compressionsans pertes) ;Une fois on obtient un flux très semblable au fluxd’origine, mais eventuellement différent (compression avecpertes) ;Dans les premiers cours, on ne fait que de la compression sans pertes.E. Jeandel, Lif Outils InformatiqueCompressionCompression statistique 2/16Compression sans pertesPropositionAucun outil de compression n’est efficace : On peut trouver pour tout nune chaine de longueur n qu’il ne compresse pas, même d’un seulcaractère.Démonstration.nIl y a 256 chaines de longueur n.nn 1 256 1Il y a 1+ 256++ 256 = chaînes de longueur256 1strictement inférieur à n.nn 256 1256 > , donc si le compresseur compresse toutes les256 1chaînes de longueur n, il va en compresser deux de la mêmefaçon.Contradiction.E. Jeandel, Lif Outils InformatiqueCompressionCompression statistique 3/16Ce qu’on peut faireUn outil de compression ne peut donc pas toujours compresser,ne serait-ce que d’un octetLes outils disponibles s’efforcent donc de ne produire des ...

Informations

• Publié par: Thyam
• Nombre de lectures: 17
• Langue: Français

Extrait

.El,deanJeilutfOLiamrofnIsmoCeuqitoCpmerssrpseisnostique1/ionstati

Outils Informatique Compression Compression statistique

61

E. Jeandel

Emmanuel.Jeandel at lif.univ-mrs.fr

CnoisserpmoCeuqiisatstonsiespromleL,aednEJ.rmatInfotilsifOu6

Un outil de compression est la donnée de deux outils : Un programme de compression qui prend un flux de données et qui le convertit un en flux compressé ; Un programme de décompression qui prend un flux compressé et le décompresse. Deux types de compression Une fois décompressé, on réobtient le flux d’origine (compression sans pertes) ; Une fois décompressé, on obtient un flux très semblable au flux d’origine, mais eventuellement différent (compression avec pertes) ; Dans les premiers cours, on ne fait que de la compression sans pertes.

Compression

ituq2e1/

qieuitts

Démonstration. Il y a 256 n chaines de longueurn. Il y a 1+256+∙ ∙ ∙+256 n−1 = 625 526 n − − 1 1 chaînes de longueur strictement inférieur àn. 256 n > 526 526 n − − 1 1 , donc si le compresseur compresse toutes les chaînes de longueurn, il va en compresser deux de la même façon. Contradiction.

Proposition Aucun outil de compression n’est efficace : On peut trouver pour tout n une chaine de longueur n qu’il ne compresse pas, même d’un seul caractère.

/361.EeJnaedl,LifOutilsInforitamCeuqrpmoisseCoonrempiosstans repsnasnsetCoiossremp

oCpmerssoisnatitstique4/16

Ce qu’on peut faire

Un outil de compression ne peut donc pas toujours compresser, ne serait-ce que d’un octet Les outils disponibles s’efforcent donc de ne produire des bons résultats que dans des cas particulier : Documents textes ; Documents produisant des structures repérables ; Aujourd’hui, on étudie une première méthode de compression, la compression statistique.

lituOfiLamrofnIsomeCqutionsiesprE.del,Jean

ueiqatrmfoInlstiuOfiL,lednaeJ.EmpCossrenCiopromissetsnositauqite5/16

Représentation des caractères

11000 11001 11010 11011 11100 11101 11110 11111

x y z . , ’ ! ?

10000 10001 10010 10011 10100 10101 10110 10111

p q r s t u v w

01000 01001 01010 01011 01100 01101 01110 01111

h i j k l m n o

00000 00001 00010 00011 00100 00101 00110 00111

a b c d e f g

Un flux de données est constitué de caractères ; Chacun des caractères fait partie d’un ensemble donné de 256 caractères (pour simplifier seulement 32 dans ce cours) ; Chaque caractère est représenté par la donnée de 8 bits (dans le cours, seulement 5) ; Finalement, un flux de données n’est qu’une suite de 0 et 1.

Compression statistique

mon mur sonne sous mes mains usees.

Principe La compression statistique utilise comme principale source d’information pour compresser la répartition des lettres dans le texte, et plus précisément leur fréquence d’apparition.

/661qieuitts

Taille du texte :35octets Comment compresser ce texte ?

4 3 1 7 1

n u r s .

6 1 4 1 4 3

a e i m o

isserpmoCeuqitamtansiossrempCoonE.Jeande,liLOftuliIsfnro

qitaoCeuerpmoissomnCespronsiatstsiituq7e1/6

m o n mu o nr sne 0100011001010000010010010111000010000110010101010010 h yh j td r d f , Taille du texte : 4×35 bits, soit28octets

Comment compresser ce texte ?

Il n’y a que 11 caractères, donc au lieu de représenter chacun sur 5 bits, on peut les représenter seulement sur 4 bits : 0000m0100s1000w1100 a0001n0101u1001x1101 e0010o0110.1010y1110 i0011r0111v1011z1111

ndel.JeaEofmrslnIuOitL,fi

siittsta1/6uq8e

10 110 111

Comment compresser ce texte ?

mon murso n n e 0100011001010000010011001110000100100010101010010 Taille du texte : 2×7+3×(3+1) +4×24=122 bits soit24.4 octets Pourquoi est-ce qu’on arrive à décompresser le texte ?

On peut encore changer le codage : 0000m0100 a0001n0101 e0010o0110 i0011r0111

s u .

qitamroferpmoCeuomnCiossonsiesprE.JeauOitslnIdnleL,fi

eComtiqusionprestuliiLOfroamIsfnE.l,deanJe

e

i

m

n

o

r

u

s

Codages préfixes

61

a

Définition Un codage préfixe est un codage tel qu’aucun code ne soit le début d’un autre code.

Les codes préfixes sont non-ambigus : On sait à quel moment s’arrêter et décoder quand on lit le texte. On peut représenter les codes préfixes par des arbres :

.

qits/9eunsiotitampCossre

isatston0/e1qutiCnoisserisserpmo

L’objectif de la compression statistique est De construire un code préfixe Qu’il soit le plus possible adapté Il faut donc s’arranger pour obtenir des codespetitspour des lettres fréquentes. On va ici indiquer la méthode de Huffman pour obtenir un tel code

61

Compression statistique

EJ.Ouiflstindea,LeleuqipmoCofnItamr

/11euqitsitatsno

Principe de l’algorithme On représente chaque lettre par un sommet. Lepoidsd’un sommet est la fréquence de la lettre. A chaque étape, on relie ensemble les deux sommets les plus petits pour former un nouveau sommet dont le poids est la somme des poids.

Codage de Huffman

16oCpmqieumrtanIofessiomprionCressJ.EOuiflstindea,Lel