X Informatique MP/PC 2007

Thème de l'épreuve Compression bzip
Principaux outils utilisés boucles for et while, tableaux et indirections, récursivité, calculs de complexité
Mots clefs compression, bzip, redondance, Burrows, Wheeler, codage, transformation de Burrows-Wheeler

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
           

Rapport du jury

(télécharger le PDF)
              

Énoncé obtenu par reconnaissance optique des caractères


ECOLE POLYTECHNIQUE
ÉCOLE SUPÉRIEURE DE PHYSIQUE ET CHIMIE INDUSTRIELLES

CONCOURS D'ADMISSION 2007

FILIÈRE MP - OPTION PHYSIQUE ET SCIENCES DE L'INGÉNIEUR FILIÈRE PC

COMPOSITION D'INFORMATIQUE

(Durée : 2 heures)

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête 
de la copie.

On attachera une grande importance a la concision, a la clarté, et a la 
précision de la rédaction.

***

Compression bzip

Le temps d'exécution T( f ) d'une fonction f est le nombre d'opérations 
élémentaires (addition,
soustraction, multiplication, division, affectation, etc.) nécessaire au calcul 
de f. Lorsque ce temps
d'exécution dépend d'un paramètre n, il sera noté Tn( f ) On dit que la 
fonction f s'exécute :

en temps O(n°'), s'il existe K > 0 tel que pour tout n, T,,(f) £ KnO'.

Dans ce sujet, il sera question de l'algorithme de Burrows--Wheeler qui 
compresse très effica--
cement des données textuelles. Le texte d'entrée a compresser sera représenté 
par un tableau 15
contenant des entiers compris entre 0 et 255 inclus.

1 Compression par redondance

La compression par redondance compresse un texte d'entrée qui possède des 
répétitions consé--
cutives de lettres (ou d'entiers dans notre cas). Dans un premier temps, on 
calcule les fréquences
d'apparition de chaque entier dans le texte d'entrée. Puis on compresse le 
texte.

Question 1 Écrire la fonction occurrences(t, 77.) qui prend en argument un 
tableau d'entrée 15 de
longueur n, et qui retourne un tableau 7" de taille 256 tel que r[i] est le 
nombre d'occurrences de i
dans 15 pour 0 S i < n.

Question 2 Écrire la fontion min(t, 77.) qui prend en argument le tableau 15 de 
longueur n, et qui
retourne le plus petit entier de l'intervalle [O, 255] qui apparaît le moins 
souvent dans le tableau 15.
(Le nombre d'occurrences de cet entier peut être nul)

L'entier min(t,n) servira de marqueur. On note # pour ce marqueur et, pour 
simplifier, on

suppose que son nombre d'occurrences est nul. Donc r[#] = 0 quand 7" : 
occurrences(t,n). La
compression par redondance du texte 15 fonctionne comme suit : toute répétition 
maximale contigüe
d'une lettre où t[i] = t[i + 1] = : t[j] : k est codée par les trois entiers #, 
(j -- i),k; toute

apparition unique d'une lettre k est codée par cette même lettre.

1

Par exemple, si le tableau 15 contient les valeurs <0, 0, 3, 2, 3, 3, 3, 3, 3, 
3, 5). Le marqueur est donc
1 car 1 n'apparaît pas dans ce tableau. Le texte t' compressé est alors

1 ,1,1,0, 3 , 2 , 1,5,3, 5
v, *VV \ , V
# 0,0 3 2 3,3,3,3,3,3 5

Question 3 Écrire la fonction tailleCodage(t, 77.) qui prend comme argument le 
tableau 15 et calcule
la taille n' du texte compressé (n' = 10 dans l'exemple ci--dessus).

Question 4 Écrire la fonction codage(t, 77.) qui prend comme paramètre le 
tableau 15 et retourne
un tableau d'entiers t' représentant le texte compressé.

Pour pouvoir décoder un texte t' ainsi compressé, il suffit de connaître le 
marqueur utilisé. Or
ce marqueur est le premier entier du texte compressé.

2 Transformation de Burrows-WheeIer

Le codage par redondance n'est efficace que si le texte présente de nombreuses 
répétitions consé--
cutives de lettres. Oe n'est évidemment pas le cas pour un texte pris au 
hasard. La transformation
de Burrows--Wheeler est une transformation qui, a partir d'un texte donné, 
produit un autre texte
contenant exactement les mêmes lettres mais dans un autre ordre où les 
répétitions de lettres ont
tendance a être contigües. Cette transformation est bijective.

Considérons par exemple le texte d'entrée concours. Pour simplifier la 
présentation, nous uti--
lisons ici des caractères pour le tableau d'entrée. Cependant, dans les 
programmes, on considère
toujours (comme dans la première partie) que le texte d'entrée est un tableau 
d'entiers compris
entre 0 et 255 inclus. Le principe de la transformation suit les trois étapes 
suivantes :

1 -- On regarde toutes les rotations du texte. 2 -- On trie ces rotations par 
ordre lexi--
Dans notre cas, il y en a 8 qui sont : cographique (l'ordre du dictionnaire).

concours concours

oncoursc courscon

ncoursco ncoursco

courscon oncoursc

oursconc oursconc

ursconco rsconcou

rsconcou sconcour

sconcour ursconco

3 -- Le texte résultant est formé par toutes les dernières lettres des mots 
dans l'ordre précédent,
soit snoccuro dans l'exemple, ainsi que de l'indice de la lettre dans ce texte 
résultant qui est la
première lettre du texte original, soit 3 dans notre exemple. On appelle cet 
entier la clé de la
transformation.

On remarque que les deux c du texte de départ se retrouvent côte a côte après 
la transforma--
tion. En effet, comme le tri des rotations regroupe les mêmes lettres sur la 
première colonne, cela
conduit a rapprocher aussi les lettres de la dernière colonne qui les précédent 
dans le texte d'entrée.

2

On le constate aussi sur la chaîne : concours...de...l...ecole...polytechnique 
dont la transformée par
Burrows--Wheeler est sleeeeen...dlt...ucn...ooohcpcc...iuryqo.

En pratique, on ne va pas calculer et stocker l'ensemble des rotations du mot 
d'entrée. On se
contente de noter par rot[i] la i--ème rotation du mot. Ainsi, dans l'exemple, 
rot[0] représente le
texte d'entrée concours, rot... représente oncoursc, rot[2] représente 
ncoursco, etc.

Question 5 Écrire la fonction comparerRotations(t, n, i, j) qui prend comme 
arguments le texte 15
de longueur 77. et deux indices @, j , et qui renvoie, en temps linéaire par 
rapport a n :

1 si rot[i] est plus grand que rot[j] dans l'ordre lexicographique,
--1 si rot[i] est plus petit que rot[j] dans l'ordre lexicographique,

0 sinon.

On suppose disposer d'une fonction triRotations(t, 77.) qui trie les rotations 
du texte donné dans le
tableau 15 en utilisant la fonction com parerRotation. Elle retourne un tableau 
d'entiers 7" représentant
les numéros des rotations (rot[r[0H £ rot[r[1]] £ £ rot[r[n -- 1]]). Cette 
fonction réalise dans le
pire des cas O(n ln 77.) appels a la fonction de comparaison.

Question 6 Écrire une fonction codageBW(t,n) qui prend en paramètre le tableau 
15, et qui
renvoie un tableau contenant le texte après transformation. (La clé sera 
stockée dans la dernière
case de ce tableau)

Question 7 Donner un ordre de grandeur du temps d'exécution de la fonction 
codageBW en
fonction de n.

Pour réaliser l'ensemble du codage, il ne reste plus qu'à réaliser la 
compression par redondance
sur la transformée t' du texte d'entrée 15.

3 Transformation de Burrows-WheeIer inverse

Pour décoder le texte t' (snoccur03 dans l'exemple) de taille n' = n + 1 obtenu 
après transfor--
mation, on construit d'abord un tableau triCars de taille 77. qui contient les 
mêmes lettres que le
texte t' mais dans l'ordre lexicographique croissant. Dans l'exemple, triCars : 
.

Question 10 Écrire la fonction trouverlndices(t' ,n' ) prenant en paramètre le 
texte t' codé de
longueur n' , et qui retourne le tableau indices précédemment décrit. Quel est 
son temps d'exécution
en fonction de n' ?

Question 11 Écrire une fonction decodageBW(t' , n' ) qui prend comme paramètre 
un texte t' de
longueur n' , et retourne le texte 15 d'origine. Quel est son temps d'exécution 
en fonction de n' ?

Extrait du corrigé obtenu par reconnaissance optique des caractères



X Informatique MP/PC 2007 -- Corrigé
Ce corrigé est proposé par Jean-Baptiste Rouquier (ENS Lyon) ; il a été relu par
Vincent Danjean (ENS Lyon) et Vincent Puyhaubert (Professeur en CPGE).

Ce sujet traite de compression de données, comme c'était déjà le cas en 2004.
L'algorithme, présenté ici dans une version simplifiée, est couramment utilisé 
sous
Linux par le programme bzip2.
· La partie 1 concerne la compression de textes ayant des séquences de lettres
identiques. Cette compression pourrait être utilisée comme une deuxième passe
pour compresser un texte, après la transformation de Burrows-Wheeler.
Mais les techniques employées en pratique sont plus efficaces.
· La partie 2 étudie la transformation de Burrows-Wheeler, astucieuse 
transformation bijective qui, à un texte « naturel », tend à associer un texte 
plus facile
à compresser.
· La partie 3 explique comment calculer la transformée inverse, qu'il faut alors
implémenter.
À part la question 7, toutes les questions exigent d'écrire du code. La 
difficulté
va croissant si l'on excepte les questions 8 (facile) et 10 (difficile, et même 
ardue si
l'on cherche la meilleure complexité à une constante multiplicative près).
Les connaissances nécessaires sur le langage se limitent aux boucles for et 
while.
Bien qu'elles simplifient l'écriture de certaines réponses, les fonctions 
locales ne sont
pas indispensables. Il en va de même pour les fonctions récursives, mais sur ce 
point
le site polytechnique.fr précise que « Les candidats devront être familiers avec
l'existence de l'écriture récursive. »
Les difficultés portent sur la longueur exacte des tableaux et sur une 
compréhension claire des indices, le contenu d'une case étant régulièrement 
utilisé comme
l'indice d'une case d'un autre tableau (ce que l'on appelle une indirection).
Ce sujet intéressera également les élèves qui suivent l'option informatique, en 
particulier la question 10 pour son point de vue algorithmique si l'on veut 
trouver un
algorithme efficace. Connaître la transformation de Burrows-Wheeler et plus 
généralement les techniques de compression, dont deux sont abordées dans le 
sujet, est un
bon apport à la culture générale en informatique.

Indications
Partie 1
2 On cherche l'élément # de t qui apparaît le moins souvent (# est donc un 
entier
de [0; 255]). En cas d'égalité, on choisit le plus petit.
Chercher d'abord le nombre d'occurrences minimal (utiliser la question 1).
3 Calculer séparément le coût de chaque lettre (ie le nombre d'entiers 
nécessaires à
son codage). Quand un bloc de lettres identiques est codé par un triplet, 
attribuer
le coût de ce triplet à la première lettre du bloc.
Traiter séparément la première et la dernière lettre.
4 Créer un tableau resultat de la bonne taille. Lire les lettres une à une et 
s'assurer
après avoir lu chaque lettre que le début de resultat code les lettres lues 
jusqu'ici.
Distinguer les mêmes cas qu'à la question précédente et traiter de nouveau la
première et la dernière lettre à part.
Créer les variables suivantes : curseur pointe sur la première case vierge de
resultat, et a_encoder pointe sur la lettre de t que l'on est en train de 
traiter
(on les traite une par une).
Partie 2
5 Si t[i] = t[j], il suffit de comparer rot[i+1 mod n] et rot[j+1 mod n]. Sinon,
on connaît déjà le résultat.
Mémoriser le nombre de lettres restant à comparer pour savoir quand s'arrêter.
6 Montrer que resultat[i] = t[r[i] - 1 mod n].
7 Compter le temps d'exécution des boucles et de l'appel à triRotations
(qui appelle plusieurs fois comparerRotations).
Partie 3
8 Utiliser le programme de la question 1 avec les bons arguments.
9 Utiliser la question précédente.
Définir un tableau resultat (ou triCars) de la bonne taille et une variable
curseur pointant sur la première case vierge de ce tableau. Pour chaque lettre 
de
0 à 255, l'écrire autant de fois que nécessaire, au fur et à mesure, dans 
resultat.
10 Version simple en O(n2 ) : créer un tableau rangs, tel que rangs[i] contient 
le
rang de la lettre triCars[i]. Pour trouver la lettre  de rang r dans t, 
initialiser
une variable rang à r et parcourir t en décrémentant rang chaque fois que l'on
rencontre une lettre égale à .
Version avancée en O(n) : créer un tableau p, dont la case  contient la position
de la première occurrence de la lettre  dans triCars. Lire une à une les lettres
de t et écrire à chaque fois une case du tableau triCars (qui ne sera pas rempli
dans l'ordre).
Quand on « utilise » la lettre à la position p[], ie que l'on remplit la case de
indices à cette position, modifier la case en position  de p afin qu'elle 
pointe toujours sur une lettre  non utilisée de triCars (et donc une case vide 
de indices).
11 Suivre la méthode détaillée par l'énoncé, à l'aide de trois variables : le 
tableau
indices calculé grâce à la question précédente, un tableau resultat que l'on
renverra et une variable position_courante initialisée à la valeur de la clé.
La variable position_courante est mise à jour chaque fois qu'on lit une lettre,
grâce au tableau indices.

Les codes source ont été rédigés en Maple, car c'est le langage le plus
enseigné en classes préparatoires à ceux qui ne suivent pas l'option 
informatique. Cependant, comme il s'agit d'un logiciel destiné au calcul formel
(qui se trouve offrir quelques possibilités de programmation), nous vous
recommandons de choisir un autre langage quand vous aurez besoin de
programmer plus efficacement. D'autres langages sont autorisés pour cette
épreuve, dont Caml (camllight et OCaml), C, C++, Java et Pascal.
Les fonctions écrites n'utilisant que de la syntaxe simple, le code est donc
facile à traduire dans le langage de votre choix (en se passant éventuellement
des fonctions locales).
Dans l'énoncé, un tableau de taille n est indexé par les entiers de 
l'intervalle [0; n - 1], comme c'est le cas pour la plupart des langages de 
programmation. Cette convention est respectée dans le corrigé (au moyen de la
syntaxe array(0..255)), même si Maple commence les indices des tableau
à 1 quand le programmeur ne demande rien.

Le rapport du jury signale qu'il est tout à fait possible de mentionner les
limitations du langage choisi et d'utiliser dans toute la copie des tableaux
dont les indices commencent à 1.

1. Compression par redondance
1 On crée un tableau resultat de taille 256. Puis, pour chaque lettre  de t,
on incrémente resultat[] (ie on lui ajoute 1).
occurrences := proc(t,n)
local i, r;
r := array(0..255);
for i from 0 to 255 do r[i] := 0; od;
for i from 0 to n-1 do
r[t[i]] := r[t[i]] +1;
od;
r;
end;
Ne pas oublier d'initialiser le tableau r, c'est-à-dire d'en remplir toutes les
cases à la création. C'est le rôle de la première boucle for, qui écrit 0 
partout.
2 Commençons par calculer le tableau r contenant le nombre d'occurrences de
chaque lettre grâce à la question 1. Définissons ensuite deux variables :
· minimum, qui contient le plus petit nombre d'occurrences d'une lettre 
rencontré
jusqu'ici. Initialement, c'est donc r[0] ;
· resultat, qui est ce que l'on va renvoyer, c'est-à-dire une lettre ayant 
minimum
occurrences (et, en cas d'égalité, la plus petite).
On tient à jour ces variables pendant le parcours de r.

mini := proc(t,n)
local i, r, minimum, resultat;
r := occurrences(t,n);
minimum := r[0];
resultat := 0;
for i from 0 to 255 do
if r[i] < minimum
then minimum := r[i]; resultat := i;
fi;
od;
resultat;
end;
Le nom de fonction imposé par l'énoncé, « min », n'est pas très heureux.
Il s'agit en effet du nom d'une fonction déjà existante dans la plupart des
langages. Cela provoque même une erreur en Maple. Nous avons donc remplacé ce 
nom par « mini ». Dans une copie écrite, il est préférable de se
conformer au choix de l'énoncé.
3 Calculons pour chaque lettre le nombre d'entiers nécessaires à son codage 
(nombre
que l'on appellera le coût de la lettre). Lorsque l'on code un bloc de lettres 
identiques
par un triplet, on impute arbitrairement le coût à la première lettre. Ainsi, 
dans
l'exemple de l'énoncé, le coût du premier « 0 » est 3, celui du second est 0 et 
le coût
de l'unique « 2 » est 1. Le coût d'une lettre est donc :
· 1 si elle est différente de la précédente et de la suivante ;
· 3 si elle est distincte de la précédente et identique à la suivante ;
· 0 si elle est identique à la précédente.
Puisque l'on a besoin de comparer la lettre à la précédente et la suivante, il 
faut
traiter à part le coût de la première lettre :
· 3 si elle identique à la suivante ;
· 1 sinon ;
et celui de la dernière lettre :
· 1 si elle est distincte de la précédente ;
· 0 sinon.
Enfin, puisque ce traitement suppose qu'il y ait au moins deux lettres, on 
vérifie au
début que n est au moins égal à 2. Et l'on ajoute 1 pour la case occupée par la 
clef.
tailleCodage := proc(t,n)
local i, resultat;
if n=0 then 1;
elif n=1 then 2;
else
resultat := 0;
#première lettre :
if t[0] = t[1]
then resultat := resultat+3;
else resultat := resultat+1;
fi;