Outils Informatique Compression Compression statistique

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