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;