CompressionCompressionBruno MARTIN,Universit´e Cˆote d"AzurBruno MARTIN, Universit´e Cˆote d"AzurCompression 1CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesPlan1CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesBruno MARTIN, Universit´e Cˆote d"AzurCompression 2CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesPourquoi la compression de donn´ees?les supports de stockage de donn´ees se remplissent en mˆemetemps que leur taille croˆıt.formats de fichiers int`egrent la compression :images (gif, jpeg)texte (pdf)r´eseaux : augmenter la bande passante en diminuant lenombre de bits transmis (pb des chiffres)t´el´ecommunications : utilis´ee dans le fonctionnement desmodems (protocole V42 par exemple) et pour lestransmissions par t´el´ecopie.Bruno MARTIN, Universit´e Cˆote d"AzurCompression 3CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesCompression & d´ecompression001011010010011000111111011101001000101101001001100011111101110100100010110100100110001111110111010010d´ecompressioncompressionBCRRn"est pas forc´ement identique `aB.
QuandB=Ron parle de compressionsans perteB?=Ron parle de compressionavec pertes(plus efficace)Bruno MARTIN, Universit´e Cˆote d"AzurCompression 4CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesTypes d"algorithmes de compressionalgorithmes statistiques :codes de Huffman, construisentun dictionnaire en effectuant une analyse statistique pr´ealablealgorithmes dynamiques :Lempel et Ziv, construisentdynamiquement un dictionnaire qui remplace les donn´eesr´ep´et´ees par des liens vers une entr´ee pr´ec´edentem´ethodes heuristiquesessayent de?deviner?les ´el´ementsdu bloc de donn´ees.
Ce sont les plus r´ecentes.Bruno MARTIN, Universit´e Cˆote d"AzurCompression 5CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesMesures d"efficacit´erapport de compression,|C||B|normalement<1.
Une valeurde 0,6 signifie que|B|a ´et´e r´eduit de 40%.facteur de compression, rapport inverse du rapport decompression est normalement>1.
Plus la compression estgrande, plus le facteur de compression croˆıt.l"expression 100×(1-rapport de compression) est souventutilis´ee.
Une valeur de 40 signifie que|B|`a ´et´e r´eduit de 40%.Bruno MARTIN, Universit´e Cˆote d"AzurCompression 6CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesM´ethodes na
ıves - Compression des espacesRetirer les espaces d"un texte en m´emorisant leur position par unmot binaire : 1 = un espace et 0 = autre caract`erePour r´eduire la longueur?→000010000000100100000000le texte comprim´e est :000010000000100100000000|Pourr´eduirelalongueurFaible nombre d"espaces dansm:?1m<< ?0metmpourra ˆetrecomprim´e, p.e. 04107102108.Bruno MARTIN, Universit´e Cˆote d"AzurCompression 7CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesM´ethodes na
ıves - Compression de tˆeteListe de mots tri´es dans l"ordre lexicographique (p.e. dictionnaire),2 mots cons´ecutifs partagent souvent un mˆemen-pr´efixep.
Onremplacepdans le second mot parn, longueur du pr´efixe commun.Coda CodaCod´e 3´eCode-Barres 3e-BarresCoder 4rCodeur 4urCodicille 3icilleBruno MARTIN, Universit´e Cˆote d"AzurCompression 8CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesRLE (pourRun Length Encoding)Id´ee :r´ep´etition den?a?remplac´ee parna. (long. de r´ep´etitionouRun length)les chaussettes de l"archiduchesseet la transforme enles chau@2se@2tes de l"archiduche@2seObservationSortie>entr´ee : dans l"entr´ee, on n"a que des r´ep´etitions delongueur 2 compress´ees avec 3 caract`eres!Tactique valable quand un caract`ere est r´ep´et´e plus de 3fois.Parmi les m´ethodes dans la compression MNP5 des modems [3].Bruno MARTIN, Universit´e Cˆote d"AzurCompression 9CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesM´ethode statistique, le code de HuffmanBut :construire un codepr´efixeoptimal pour une sourceSrcomprenantrsymboles sur un alphabet binaire bas´e sur :r´eduction :transformeSren une source `ar-1 symbolesSr-1pour obtenir finalement une source `a deux symboles :son code pr´efixe optimal est{0,1}propri´et´e :sur{0,1}siC={c1, ,cr}code pr´efixe optimalpour une sourceSr, alorsC?={c?1, ,c?r,c?r+1}:???c?i=ci1≤i≤r-1c?r=cr.0c?r+1=cr.1est un code pr´efixe optimal pour la sourceS?r+1.Bruno MARTIN, Universit´e Cˆote d"AzurCompression 10CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesPrincipe de r´eduction1ordonner les symboles de source par proba. d´ecroissantes2fusionner les 2 derniers symboles, avec proba = somme desproba des 2 derniers symboles3r´eordonner la liste et r´ep`eter le processus4arrˆet quand il n"y a plus que 2 ´el´ementsensuite, appliquer successivement la propri´et´e en remontant de lasource `a 2 symboles cod´es par 0 et 1 versSrpour avoir un codepr´efixe optimal pourSr.Bruno MARTIN, Universit´e Cˆote d"AzurCompression 11CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesExemple de code optimalA,BetCt.q.P(A) = 1/2,P(B) =P(C) = 1/4.apr`es l"´etape (4) de l"algorithme,on obtient :A1/2 1/2→0B1/4 1/2→1C1/4?C(1/4)11B(1/4)10CB(1/2)A(1/2)00101A?→0,B?→10C?→11.ABAACABC?→010001101011.Bruno MARTIN, Universit´e Cˆote d"AzurCompression 12CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesPrincipe des algorithmes dynamiquesRemplacer desfacteurspar des codes courts : indices des facteursdans un dictionnaire construit dynamiquement.Reposent sur une des m´ethodes propos´ees par Lempel et Ziv [5, 6].LZ77 et LZ78 parcourent l"entr´ee `a compresser de la gauche vers ladroite en rempla¸cant les facteurs r´ep´et´es par des pointeurs versl"endroit o`u ils sont d´ej`a apparus dans le texte.Nombreuses variantes sur la mani`ere de m´emoriser et rep´erer lesfacteurs r´ep´et´es.LZ77 : utilis´e danspkzip,gzip;LZ78 : utilis´e danscompressd"UNIX et le format d"imagesgif.Bruno MARTIN, Universit´e Cˆote d"AzurCompression 13CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesPrincipe de LZ77Utilise une partie de la donn´ee d"entr´ee comme un dictionnaire.L"algorithme fait glisser une fenˆetre deNcaract`eres sur la chaˆıned"entr´ee de gauche `a droite.
Fenˆetre en deux parties :`a gauche : fenˆetre de recherche,N-Fcaract`eres :dictionnaire des lettres lues et comprim´ees r´ecemment;`a droite : fenˆetre de lecture,Fcaract`eres `a comprimer.Bruno MARTIN, Universit´e Cˆote d"AzurCompression 14CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesExemple←texte comprim´e aabbabababababb????ababbbbabbbabb???? ←texte `a fenˆetre de recherche fenˆetre de lecture←texte comprim´e aabbabababababb????ababbbbabbbabb???? ←texte `a recherche (N-F) lecture (F)Bruno MARTIN, Universit´e Cˆote d"AzurCompression 15CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesAlgorithme de compression LZ77Chercher dans lesN-Fpremiers caract`eres de la fenˆetre derecherche le plus long facteur qui est un pr´efixe de la fenˆetre delecture de taille au plusF.
Le codage est (p,?,c) o`u :p: distance entre le d´ebut du fenˆetre de lecture et la positionde r´ep´etition dans le dictionnaire;?: la longueur de la r´ep´etition;c: 1ercaract`ere de la fenˆetre de lecture diff´erent du caract`erecorrespondant dans la fenˆetre de recherche.R´ep´etition peut chevaucher le dictionnaire et la fenˆetre de lecture.Apr`es le codage, la fenˆetre glisse de?+ 1 caract`eres vers la droite.Si on ne trouve pas de r´ep´etition, on code (0,0,c).Bruno MARTIN, Universit´e Cˆote d"AzurCompression 16CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiqueslemageditabracadabra(0,0,l)lemageditabracadabra(0,0,e)lemageditabracadabra(3,1,m)lemageditabracadabra(0,0,a)lemageditabracadabra(0,0,g)lemageditabracadabra(5,2,d)lemageditabracadabra(0,0,i)lem ageditabracadabra(0,0,t)lema geditabracadabra(4,1,a)lemageditabracadabra(0,0,b)lemageditabracadabra(0,0,r)lemaged itabracadabra(3,1,c)lemageditabracadabra(5,1,d)lemagedita bracadabra(4,1,b)lemageditabr acadabra(0,0,r)lemageditabra cadabra(5,1,"")Bruno MARTIN, Universit´e Cˆote d"AzurCompression 17CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesD´ecompression de LZ77A partir des triplets (p,?,c), le d´ecodage se fait en faisant glisserla fenˆetre comme pour le codage.
Le dictionnaire est reconstruit.Algorithme1. lire un l´ex`eme2. chercher la correspondance dans la fenˆetre de recherche3. ´ecrire le facteur trouv´e au d´ebut de la fenˆetre de lecture4. ´ecrire la 3ecomposante du l´ex`eme `a la suite5. d´ecaler le contenu des fenˆetres de?+ 1cases vers la gaucheBruno MARTIN, Universit´e Cˆote d"AzurCompression 18CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesl(0,0,l)le(0,0,e)lem(3,1,m)lema(0,0,a)lemag(0,0,g)lemaged(5,2,d)lemagedi(0,0,i)lem agedit(0,0,t)lema gedita(4,1,a)lemageditab(0,0,b)lemageditabr(0,0,r)lemaged itabrac(3,1,c)lemageditabracad(5,1,d)lemagedita bracadab(4,1,b)lemageditabr acadabr(0,0,r)lemageditabra cadabra(5,1,"")Bruno MARTIN, Universit´e Cˆote d"AzurCompression 19CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesFaiblesses de LZ77LZ77 suppose que les motifs r´ep´et´es sont proches dans l"entr´ee.Autre inconv´enient : la taille limit´eeFde la fenˆetre de lecture.
Dece fait, la taille de la plus longue correspondance ne peut exc´ederF-1.Fne peut croˆıtre beaucoup, car le temps de compressioncroˆıt proportionnellement `aF.
Il en est de mˆeme avec la taille dela fenˆetre de recherche.Bruno MARTIN, Universit´e Cˆote d"AzurCompression 20CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesAlgorithme de compression LZ78Fonctionnement analogue `a LZ77; dictionnaire n"est plus unefenˆetre coulissante.
Constitu´e de l"int´egralit´e du texted´ej`a trait´e.Au d´epart, aucun facteur n"est connu; ajouter au dictionnairetousles facteurs rencontr´es en les num´erotant.
Chercher le pluslongpr´efixepen correspondance avec un facteurfdu dictionnaire.Deux cas :f/?dictionnaire; le texte restant `a traiter s"´ecritc.mavecccaract`ere inconnu au dictionnaire etmle reste du texte.L"algorithme rend (0,c) et ajoutecau dictionnaire.f?dictionnaire `a l"indicei>0; le texte restant `a traiters"´ecrit alors commef.c.m.
L"algorithme rend (i,c) et ajoutef.cau dictionnaire.Bruno MARTIN, Universit´e Cˆote d"AzurCompression 21CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesExempleSoit la chaˆıneaabbabababbbbabbbabb`a comprimer.Dictionnairel´ex`eme0null1a(0,a)2ab(1,b)3b(0,b)4aba(2,a)5ba(3,a)6bb(3,b)7bba(6,a)8bbb(6,b)9abb(2,b)Bruno MARTIN, Universit´e Cˆote d"AzurCompression 22CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesAlgorithme de d´ecompression de LZ78Reconstruire le dictionnaire au fur et `a mesure du d´ecodage.
Lesindices des facteurs seront identiques `a ceux du codage et lesfacteurs pourront ˆetre interpr´et´es.Compression et d´ecompression utilisent le mˆeme dictionnaire sansque celui-ci soit transmis.
Il est enti`erement reconstruit au cours dela d´ecompression.Bruno MARTIN, Universit´e Cˆote d"AzurCompression 23CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesLa suite (0,a)(1,b)(0,b)(2,a)(3,a)(3,b)(6,a)(6,b)(2,b)reconstruit le dictionnaire :Dictionnairel´ex`eme0null1a(0,a)2ab(1,b)3b(0,b)4aba(2,a)5ba(3,a)6bb(3,b)7bba(6,a)8bbb(6,b)9abb(2,b)Bruno MARTIN, Universit´e Cˆote d"AzurCompression 24CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesLZ78 en pratiqueEn pratique, LZ78 a un dictionnaire de taille born´ee; quand ilestplein, on l"efface et on continue avec un nouveau dictionnaire.Compression moins bonne mais cette m´ethode peut ˆetre employ´ee,mˆeme si le dictionnaire n"est pas de taille suffisante pour contenirl"ensemble des facteurs du texte.LZ78 a un grand nombre de variantes, p.e. :LZW par par T.
Welch [4] (contrˆoleurs de disque dur)LZC danscompressd"UNIX.Bruno MARTIN, Universit´e Cˆote d"AzurCompression 25CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesLimites de la compression : donn´ees incompressibles?n?N:2nmots binaires distincts de longueurn?n-1i=02i=2n-1 descriptions plus courtes (mots comprim´es delongueur strictement inf´erieure `an)Pour toutn, il existe donc au moins un mot binaire de longueurnincompressible.Cas des suites finies (vraiment) al´eatoires [2].On ne peut trouver aucune r´egularit´e dans une suite al´eatoire(complexit´e de Chaitin-Kolmogorov).Bruno MARTIN, Universit´e Cˆote d"AzurCompression 26CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesLe meilleur algorithme de compression1000 algorithmes de compression et de d´ecompression :C1,C2, ,C1000D1,D2, ,D1000; on construit un algorithme de compression capable decomprimer toute suite de symbolesBaussi bien, `a 10 bits pr`es que lemeilleur des 1000 compresseurs [1].ComprimerB: essayer chacun des 1000 compresseurs.
M´emoriserk,num´ero du meilleur algorithme de compression qui a comprim´eBenC.Nouvelle donn´ee comprim´ee: suiteC?compos´ee du codage en binairedeksuivi du r´esultat de l"algorithme de compressionCk(B) =C.
Coderkn´ecessite 10 bits =?log21000?+ 1.D´ecomprimer: algorithme de d´ecompression effectue le travail inverse.Il d´ecodek, le nombre binaire port´e sur les 10 premiers bits deC?puisappliqueDksur la donn´ee deC?priv´e de ses 10 premiers bits.Bruno MARTIN, Universit´e Cˆote d"AzurCompression 27CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesG´en´eralisation `a un nombreNquelconqueAlgorithme de compression construit sera aussi efficace que lesNcompresseurs `a =?log2N?+ 1 bits pr`es.Remarque : le temps de fonctionnement de notre algorithmecorrespond au temps cumul´e desNalgorithmes de compressionBruno MARTIN, Universit´e Cˆote d"AzurCompression 28CompressionM´ethodes na
ıvesCodage d"HuffmanAlgorithmes dynamiquesJ.P. Delahaye.La compression des donn´ees.Pour la science, 217 :177-189, 1995.M. Li and P. Vit´anyi.An introduction to Kolmogorov complexity and its applications.Springer Verlag, 1993.D. Salomon.Data compression, the complete reference.Springer Verlag, 1998.T.A. Welch.A technique for high performance data compression.Computer, 17(6) :8-19, 1984.J. Ziv and A.
Lempel.A universal algorithm for sequential data compression.IEEE Transactions on Information Theory, IT-23(3) :337-343, 1977.J. Ziv and A.
Lempel.Compression of individual sequences via variable-rate coding.IEEE Transactions on Information Theory, IT-24(5) :530-536, 1978.Bruno MARTIN, Universit´e Cˆote d"AzurCompression 28
