Polytechnique Informatique Commune MP PC 2007

ÉCOLE 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 à la concision, à la clarté, et à la précision de la rédaction.

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

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

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 qui prend en argument un tableau d'entrée de longueur ; et qui retourne un tableau de taille 256 tel que est le nombre d'occurrences de dans pour .

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

L'entier servira de marqueur. On note # pour ce marqueur et, pour simplifier, on suppose que son nombre d'occurrences est nul. Donc quand . La compression par redondance du texte fonctionne comme suit : toute répétition maximale contigüe d'une lettre où est codée par les trois entiers , ; toute apparition unique d'une lettre est codée par cette même lettre.

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

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

Question 4 Écrire la fonction qui prend comme paramètre le tableau et retourne un tableau d'entiers représentant le texte compressé.

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

Le codage par redondance n'est efficace que si le texte présente de nombreuses répétitions consécutives de lettres. Ce n'est évidemment pas le cas pour un texte pris au hasard. La transformation de Burrows-Wheeler est une transformation qui, à 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 à être contigües. Cette transformation est bijective.

Considérons par exemple le texte d'entrée concours. Pour simplifier la présentation, nous utilisons 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.
Dans notre cas, il y en a 8 qui sont :

2 - On trie ces rotations par ordre lexicographique (l'ordre du dictionnaire).

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 à côte après la transformation. En effet, comme le tri des rotations regroupe les mêmes lettres sur la première colonne, cela conduit à rapprocher aussi les lettres de la dernière colonne qui les précèdent dans le texte d'entrée.

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

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 la -ème rotation du mot. Ainsi, dans l'exemple, rot représente le texte d'entrée concours, rot[1] représente oncoursc, rot[2] représente ncoursco, etc.

Question 5 Écrire la fonction comparerRotations( ) qui prend comme arguments le texte de longueur et deux indices ; et qui renvoie, en temps linéaire par rapport à :

1 si est plus grand que dans l'ordre lexicographique,
-1 si est plus petit que dans l'ordre lexicographique,
0 sinon.

On suppose disposer d'une fonction triRotations qui trie les rotations du texte donné dans le tableau en utilisant la fonction comparerRotation. Elle retourne un tableau d'entiers représentant les numéros des rotations . Cette fonction réalise dans le pire des cas appels à la fonction de comparaison.

Question 6 Écrire une fonction codageBW qui prend en paramètre le tableau ; 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 .

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

Pour décoder le texte (snoccuro3 dans l'exemple) de taille obtenu après transformation, on construit d'abord un tableau triCars de taille qui contient les mêmes lettres que le texte mais dans l'ordre lexicographique croissant. Dans l'exemple, triCars .

Question 8 Écrire une fonction frequences qui prend comme argument un tableau de taille correspondant au texte codé (avec la clé dans la dernière case); et qui renvoie un tableau de taille 256 contenant le nombre d'occurrences de chaque lettre dans .

Question 9 Écrire la fonction triCarsDe qui part du texte codé de taille ; et qui renvoie, en temps linéaire par rapport à , le tableau triCars décrit précédemment.

Puis on considère le texte codé et le tableau triCars précédent (la clé est représentée en gras).

À chaque lettre de la première ligne, on associe la lettre de la seconde à la même position. À chaque lettre de la deuxième ligne, on associe la même lettre de même rang dans la première ligne. La figure suivante montre ces deux correspondances.

On retrouve le texte de départ concours en partant de la clé (position de la lettre en caractère gras) et en suivant les flèches du dessin précédent.

Il faut donc construire le tableau indices tel que indices est l'indice de la lettre triCars dans le texte . Si plusieurs occurrences de cette lettre figurent dans , on fait correspondre celle qui figure au même rang dans . Le tableau indices donne donc la correspondance représentée par les flèches de la seconde ligne vers la première. Sur l'exemple, le tableau indices contient les valeurs .

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

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