Compression - Exercices

Répétition.

Un contenu régulier.

Créez, à l'aide d'un programme python, un fichier contenant n fois la lettre 'a' (n étant un entier>0, paramètre de la fonction créant le fichier).
Avec un logiciel de compression adéquat, compressez au format zip le fichier obtenu (on prendra par exemple n=10 000). Notez le poids en octets de ce fichier avant compression et après compression.

Un contenu irrégulier.

Créez, à l'aide d'un programme python, un fichier contenant n lettres, chaque lettre étant choisie au hasard.
Avec un logiciel de compression adéquat, compressez au format zip le fichier obtenu (on prendra la même valeur de n que précédemment). Notez le poids en octets de ce fichier.

Comparaison

Cherchez à donner une explication aux poids comparés des deux fichiers zip précédents.

Un contenu régulier.

Un programme de création du fichier demandé :


def regulier(n) :	
	ch=''
	for i in range(n) : ch+='a'
	f=open('reg.txt','w')
	f.write(ch)
	f.close()
	
regulier(10000)

Le fichier obtenu a un poids de 10 000 octets. Après compression zip, nous obtenons un poids de 139 octets (soit 1,39 % du poids initial !)

Un contenu irrégulier.

On modifie le programme précédent en tirant au hasard les lettres parmi les symboles de code compris entre 97 et 122 (ce sont les minuscules de l'alphabet latin).


from random import randint
	
def irregulier(n) :	
	ch=''
	for i in range(n) : ch+=chr(randint(97,122))
	f=open('irreg.txt','w')
	f.write(ch)
	f.close()
	
	
irregulier(10000)

Le fichier obtenu pèse bien entendu 10 000 octets comme le précédent. Après compression zip, nous obtenons un fichier zip de 6229 octets (vous obtiendrez sans doute un autre poids, mais voisin). Soit un fichier nettement plus lourd que le précédent zip alors que les fichiers de départ étaient a priori tout à fait similaires.

Recherche d'explications

Nous ne rentrerons pas dans le détail (assez complexe) de la compression zip. Nous pouvons toutefois affirmer sans trop de doute que la compression mesure la régularité des informations pour tenter de réduire.

Le principe de base est le suivant : si une ligne est constituée de dix-mille caractères 'a', il me suffit d'écrire le texte " 10000 'a' " pour décrire ce fichier. Tandis que si ces dix-mille caractères ne présentent aucune régularité (ou peu), je n'ai pas d'autre moyen que d'énoncer un à un ces caractères.

Par exemple aaaabbbbbcccccc peut s'écrire 4a5b6c, tandis que réduire la ligne (de même longueur) abcdefwsqdfghyt suivant le même principe ne réduira pas la ligne (et même l'augmentera si on ajoute 1 devant chaque lettre).

Répétition (2).

L'objectif est de constater le même phénomène qu'à l'exercice précédent sur un fichier image.

Créer une image régulière (par exemple constituée uniquement de pixels rouges) au format ppm.
Créer une seconde image de mêmes dimensions mais avec des couleurs tirées au hasard pour chaque pixel.
Compresser les images obtenues au format zip et comparer.
En utilisant par exemple gimp, enregistrer les images au format jpg (en utilisant la même 'qualité' pour les deux images) et vérifier que l'on retrouve à nouveau le même phénomène.

Le programme ci-dessous permet de créer deux fichiers ppm de mêmes dimensions.


from random import randint

largeur, hauteur = 300, 300

f=open('regulier.ppm','w')
f.write('P3\n')
f.write(str(largeur)+' '+str(hauteur)+'\n')
f.write('255\n')

for j in range(hauteur) :
	for i in range(largeur) :
		f.write('255 100 100\n')
f.close()


 

f=open('irregulier.ppm','w')
f.write('P3\n')
f.write(str(largeur)+' '+str(hauteur)+'\n')
f.write('255\n')

for j in range(hauteur) :
	for i in range(largeur) :
		f.write(str(randint(0,255))+' '+str(randint(0,255))+' '+str(randint(0,255))+'\n')
f.close()

Le fichier régulier a de fortes chances de peser un peu plus lourd que le fichier non régulier (car nous avons ici imposé des pixels codés avec des nombres de 3 chiffres, tandis que certains nombres du fichier irrégulier auront moins de chiffres). On constatera pourtant après compression zip que le fichier régulier fournit un zip beaucoup plus léger. Idem pour des compressions jpg (aux mêmes qualités).

Le principe du run length encoding.

On dispose d'un fichier au format pbm ascii à charger ici.

Pour chercher à compresser ces données, on décrit les 9 lignes correspondants aux pixels par le texte suivant :

Expliciter le lien entre le fichier précédent et ce texte.

Le contenu du fichier pbm ascii est le suivant (vérifier ceci en ouvrant le fichier avec un éditeur de texte) :

La partie qui nous intéresse (les lignes des codes des pixels) est la suivante :

La première ligne est constituée de 0 blanc suivi de 9 noirs. Les lignes 2 et 3 idem.
Les lignes 4 à 9 sont constituées de 3 blancs suivis de 3 noirs puis 3 blancs.
Ce descriptif nous donne le code de l'énoncé.

Remarque. On peut constater sur cet exemple que le descriptif donné dans l'énoncé est effectivement moins lourd en poids que le fichier pbm ascii (il comporte moins de caractères).

Compresse ou pas ?

On reprend la méthode de description de fichier pbm exposée à l'exercice précédent.

Donner un exemple de fichier pbm tel que ce descriptif permette de diviser au moins par deux la taille du fichier.
Donner un exemple de fichier tel que le descriptif augmente la taille du fichier au lieu de la réduire.

On pourra ne pas tenir compte des entêtes pour répondre.

Diviser par 2 le poids

Prenons une simple ligne noire de 9 pixels, codé en pbm ascii. On a une ligne de 9 caractères 1. Elle sera remplacée par la ligne 0 1. Le nombre de caractères est donc inférieur à la moitié du nombre initial.

Augmenter le poids

Prenons un fichier dont l'unique ligne de pixels (codage pbm ascii) est :

Le codage de l'exercice précédent le traduira en

0 1 1 1 1

(0 blanc, 1 noir, 1 blanc, 1 noir, 1 blanc).

Le nombre de caractères de la ligne a donc été augmenté.

Compresse ou pas ? (2)

Les deux exercices précédents ont présenté un exemple simple de transformation de fichier sans perte d'information. Nous avons vu dans l'exercice précédent que la transformation compresse le fichier dans certains cas mais augmente au contraire son poids dans d'autres cas.

L'objectif est ici d'établir que le problème est général et non lié à cette transformation particulière si l'on impose qu'il n'y ait pas de perte d'information.

Combien peut-on créer de fichiers distincts de taille n bits ?
Combien peut-on créer de fichiers distincts de taille < n bits ?
Conclure.

Chaque bit peut prendre deux valeurs (0 ou 1) : 2ⁿ fichiers distincts.
2⁰+2¹+...+2^n-1=2ⁿ-1 fichiers distincts.
Dans une transformation donnée, si tous les fichiers de taille n sont transformés en un fichier de taille <n, alors au moins deux fichiers de taille n sont envoyés sur le même fichier d'après ce qui précède : il y aura donc perte d'informations.