Compression Compression statistique

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