Compression Compression statistique

E. Jeandel

Description

Compression statistiqueE. JeandelEmmanuel.Jeandel at lif.univ-mrs.frE. Jeandel, Lif CompressionCompression statistique 1/36CompressionUn outil de compression est la donnée de deux outils :Un programme de compression qui prend un flux de données etqui le convertit en un 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 CompressionCompression statistique 2/36Compression sans pertesPropositionAucun outil de compression n’est efficace : On peut trouver pour tout nune chaîne de longueur n qu’il ne compresse pas, même d’un seulcaractère.Démonstration.nIl y a 256 chaînes 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 CompressionCompression statistique 3/36Ce 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 bonsrésultats que dans des cas particulier :Documents textes ; produisant des ...

Informations

• Publié par: Obba
• Nombre de lectures: 29
• Langue: Français

Extrait

E.Je,liLnaedrpseCfmompCoonsinsiossreqitsitat

Compression Compression statistique

63/1eu

E. Jeandel

Emmanuel.Jeandel at lif.univ-mrs.fr

ndea,LelCoifrempoissmoCnserpnoisEJ.3/6uq2esiittsta

Compression

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 en un 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.

E.morpiLCfed,leJnaiossrempCoonsies63/3euqitsitatsn

Compression sans pertes

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

Démonstration. Il y a 256 n chaînes de longueurn. Il y a 1+256+∙ ∙ ∙+256 n−1 = 526 652 n − − 1 1 chaînes de longueur strictement inférieur àn. 256 n > 256 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.

ueiqsttitansioss

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 ;

Ce qu’on peut faire

63/4LifCdel,JeanE.pmernooCseismorp

ituq5e3/6

1

Outline

RLE (Run Length Encoding)

Compression

Compression

2

statistique

pmoCfiL,CnoissersiespromisatstonEndel.Jea

ed,liLCf.EeJna

Principe

Il arrive souvent qu’un même caractère apparaisse plusieurs fois consécutivement On remplace 10 occurences du caractèreapar la séquence (a,10)

/663tansiossueiqsttiisserpmoerpmoCno

Il reste à expliquer comment coder des couples(x,i)

7e3/6

qqqqqqqoooooabpppppppqmyyyyyyyyyyyyyyyyyyyyyyya → (q,6)(o,5)(a,1)(b,1)(p,6)(q,1)(m,1)(y,23)(a,1)

Exemple

J.aeEL,fidnletsnoisseuqitsitassrempCopromnCio

fiL,lednsserpmoCea.JE

qqqqqqqoooooabpppppppqmyyyyyyyyyyyyyyyyyyyyyyya → qg

oe aabapg qamayw

On représentenoccurences de la lettrexparxwoùwreprésente nen binaire.

aa

16 17 18 19 20 21 22 23

10000 10001 10010 10011 10100 10101 10110 10111

11000 11001 11010 11011 11100 11101 11110 11111

x y z . , ’ ! ?

01000 01001 01010 01011 01100 01101 01110 01111

h i j k l m n o

p q r s t u v w

8 9 10 11 12 13 14 15

a b c d e f g

0 1 2 3 4 5 6 7

00000 00001 00010 00011 00100 00101 00110 00111

tasiituq8e3/6

24 25 26 27 28 29 30 31

Méthode 1

ionCompressionst

l,LiandepresfCom.EeJiqsttita

Méthode 1

369/uepmoCnoissnoisser

Dans le meilleur des cas, un texte denoctets peut se retrouver compressé en . . . octets Dans le pire des cas, un texte denoctets peut se retrouver compressé en . . . octets Comment améliorer ?

Méthode 1

Dans le meilleur des cas, un texte denoctets peut se retrouver compressé en 2n/31 octets Dans le pire des cas, un texte denoctets peut se retrouver compressé en 2noctets Comment améliorer ?

9/36anJeE.fCLil,deseismorppmernooCnstassioiquetist

JeE./36ue10stiqtati

On choisit dans l’alphabet une lettre quelconque (dans l’exemple le point d’exclamation :!) On représente une occurrence de la lettrexparx On représentenoccurences de la lettrexpar!xwoùw représentenen binaire.

Méthode 2

espromfCLil,deansnoisserpmoCnois