Compression de données par l'algorithme de Burrows-Wheeler (principe du bzip)
Afficher ou masquer la section
Le sujet programme un algorithme de compression de données textuelles inspiré du format bzip. Une première partie compresse un texte par redondance en codant les répétitions consécutives de caractères. La deuxième partie implémente la transformation de Burrows-Wheeler, qui réordonne le texte à partir du tri lexicographique de ses rotations pour regrouper les lettres identiques. La troisième partie programme la transformation inverse permettant de retrouver le texte d'origine.
1Partie 1 : compression par redondanceCalculer les fréquences d'apparition des caractères, choisir un marqueur, puis coder les répétitions consécutives de lettres.
2Partie 2 : transformation de Burrows-WheelerTrier les rotations du texte par ordre lexicographique et construire le texte transformé à partir de leurs dernières lettres.
3Partie 3 : transformation de Burrows-Wheeler inverseReconstruire le texte d'origine à partir du texte transformé, à l'aide d'un tableau de correspondance des indices.
Difficile. Le taux de réussite chute fortement en fin de sujet : seulement 7 % pour la question 10 (moyenne de 2,7/10) et 18 % pour la question 11 (moyenne de 2,29/10), contre plus de 60 % pour les premières questions.
Deux tiers des copies environ (moyenne ± écart-type)
Votre note sur 20 à ce sujet, en conditions de concours.
Source : rapport du jury. Notes publiées par le concours (après harmonisation le cas échéant). Courbe : estimation par une loi normale.
Ce qu'a observé le jury
6 erreurs relevées
Intervalle restreint non exploité · Énoncé de la question 2 non lu · Intérêt d'un algorithme en deux passes non vu
Afficher ou masquer la section
Le sujet traitait de compression de données et ne nécessitait, en pratique, que de savoir effectuer des parcours simples de tableau à une dimension. Le critère principal d'évaluation des questions de programmation était la conformité du programme aux spécifications de l'énoncé, tant sur la forme que sur le fond (algorithmes employés, complexité en temps et en espace).
Les erreurs les plus sanctionnées
1
Intervalle restreint non exploitéQ1
À la question 1, certains candidats ont remarqué qu'on pouvait limiter les indices entre 0 et 255 comme le préambule le suggérait, ce qui donnait un bonus ; de manière étonnante, certains candidats ont malgré tout échoué à cette question.
2
Énoncé de la question 2 non luQ2
La seule difficulté de la question 2 était de lire l'énoncé, et 12 % des candidats ne l'ont pas fait.
« Cette question ne comportait qu'une difficulté, celle de lire l'énoncé et 12% des candidats ne l'ont pas fait. »
3
Intérêt d'un algorithme en deux passes non vuQ4
À la question 4, trop de candidats ne se sont pas rendu compte qu'il pouvait être intéressant de faire deux passes sur le tableau, l'une pour connaître la taille du tableau à créer, l'autre pour le remplir.
« Dans cette question, trop de candidats ne se sont pas rendu »
4
Fonction triRotations mal exploitéeQ6
La question 6 nécessitait de bien comprendre la fonction triRotations décrite dans l'énoncé, et peu de candidats ont pensé à réaliser l'ensemble des opérations nécessaires, notamment aller chercher le dernier caractère de chaque rotation.
« Peu de candidats ont pensé à réaliser l'ensemble des opérations. »
5
Question la plus difficile du sujetQ10
La question 10 était sans doute la plus difficile de l'énoncé, car elle nécessitait la compréhension de toutes les questions précédentes.
« Sans aucun doute la question la plus difficile de l'énoncé. »
6
Indépendance de la question 11 non identifiéeQ11
La question 11 était réalisable même sans avoir réussi la question précédente, ce que peu de candidats ont remarqué.
« Elle était réalisable même sans avoir réussi la question précédente ce que »
Ce qui a été bien réussi
Peu de grosses erreurs sont relevées à la question 3, hormis quelques petits problèmes en début ou en fin de texte.
La question 8, très similaire à la question 1, a permis d'y faire directement appel.
La question 9 était assez simple : il suffisait de réutiliser la question précédente pour connaître la fréquence d'apparition de chaque lettre.
Une bonne partie des candidats a adopté la solution consistant à préciser en tête de copie la convention retenue pour la numérotation des indices de tableaux.
Conseils du jury
Préciser en tête de copie les conventions adoptées pour pallier les contraintes du langage choisi (par exemple le décalage des indices de tableaux).
Respecter strictement les spécifications de forme et de fond de l'énoncé, y compris les algorithmes employés et leur complexité en temps et en espace.
Chercher la solution optimale plutôt qu'une solution fonctionnelle mais coûteuse en mémoire ou en temps.
Comprendre entièrement le fonctionnement d'une fonction décrite dans l'énoncé avant de l'utiliser dans une question suivante.
Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.
É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.
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é T_n(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_n(f) ≤ Kn^α.
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 t 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, n) qui prend en argument un tableau d'entrée t de longueur n; et qui retourne un tableau r de taille 256 tel que r[i] est le nombre d'occurrences de i dans t pour 0 ≤ i < n.
Question 2 Écrire la fontion min(t, n) qui prend en argument le tableau t de longueur n; et qui retourne le plus petit entier de l'intervalle [ 0,255 ] qui apparaît le moins souvent dans le tableau t. (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 r = occurrences(t, n). La compression par redondance du texte t 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.
Par exemple, si le tableau t 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
Question 3 Écrire la fonction tailleCodage (t, n) qui prend comme argument le tableau t et calcule la taille n^′ du texte compressé ( n^′ = 10 dans l'exemple ci-dessus).
Question 4 Écrire la fonction codage(t, n) qui prend comme paramètre le tableau t 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-Wheeler
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 :
concours
oncoursc
ncoursco
courscon
oursconc
ursconco
rsconcou
sconcour
2 - On trie ces rotations par ordre lexicographique (l'ordre du dictionnaire).
concours
courscon
ncoursco
oncoursc
oursconc
rsconcou
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 à 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 ⌟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[1] 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 t de longueur n et deux indices i, j; et qui renvoie, en temps linéaire par rapport à 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, n) qui trie les rotations du texte donné dans le tableau t en utilisant la fonction comparerRotation. Elle retourne un tableau d'entiers r représentant les numéros des rotations (rot[r[0]] ≤ rot[r[1]] ≤ ⋯ ≤ rot[r[n − 1]]). Cette fonction réalise dans le pire des cas O(nlnn) appels à la fonction de comparaison.
Question 6 Écrire une fonction codageBW (t, n) qui prend en paramètre le tableau t; 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 t.
3 Transformation de Burrows-Wheeler inverse
Pour décoder le texte t^′ (snoccuro3 dans l'exemple) de taille n^′ = n + 1 obtenu après transformation, on construit d'abord un tableau triCars de taille n qui contient les mêmes lettres que le texte t^′ mais dans l'ordre lexicographique croissant. Dans l'exemple, triCars = ⟨c, c, n, o, o, r, s, u⟩.
Question 8 Écrire une fonction frequences (t^′, n^′) qui prend comme argument un tableau t^′ de taille n^′ 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 t^′.
Question 9 Écrire la fonction triCarsDe (t^′, n^′) qui part du texte codé t^′ de taille n^′; et qui renvoie, en temps linéaire par rapport à n, le tableau triCars décrit précédemment.
Puis on considère le texte codé t^′ et le tableau triCars précédent (la clé est représentée en gras).
s
n
o
c
c
u
r
o
c
c
n
o
o
r
s
u
À 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 [i] est l'indice de la lettre triCars [i] dans le texte t^′. Si plusieurs occurrences de cette lettre figurent dans t^′, on fait correspondre celle qui figure au même rang dans t^′. 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 ⟨3, 4, 1, 2, 7, 6, 0, 5⟩.
Question 10 Écrire la fonction trouverIndices( 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 t d'origine. Quel est son temps d'exécution en fonction de n^′ ?
Questions fréquentes
4 questions
Sur quels chapitres porte l'épreuve d'informatique commune X MP-PC 2007 ?
Afficher ou masquer la section
Sur quels chapitres porte l'épreuve d'informatique commune X MP-PC 2007 ?
+
Elle porte sur l'algorithmique des tableaux, la complexité en temps, le tri et la comparaison de chaînes de caractères, à travers la programmation de l'algorithme de compression de Burrows-Wheeler utilisé notamment par bzip.
Quelles erreurs le jury a-t-il le plus relevées sur cette épreuve d'informatique X MP-PC 2007 ?
+
Un énoncé de question non lu, l'intérêt d'un algorithme en deux passes non identifié, une fonction de tri des rotations mal exploitée, et l'indépendance de la dernière question par rapport à la précédente non remarquée.
Cette épreuve d'informatique commune X MP-PC 2007 sur la compression de données est-elle difficile ?
+
Oui, le taux de réussite chute fortement en fin de sujet, avec seulement 7 % de réussite à la question 10 et 18 % à la question 11, contre plus de 60 % sur les premières questions.
Quelle est la moyenne de l'épreuve d'informatique commune X MP-PC 2007 ?
+
D'après le rapport, la moyenne est de 10,73/20 pour les 135 candidats français admissibles de la filière MP, et de 9,82/20 pour les 446 candidats français admissibles de la filière PC.
Pas de description pour le moment
Commentaires• Polytechnique Informatique Commune MP PC 2007
Connectez-vous pour participer aux discussions
Partagez vos avis, posez des questions et échangez avec la communauté
Même chapitre : Compression de données sans perteCCINP Option Informatique MP 2018CCINP · 2018Corrigé
Même chapitre : Complexité en temps (notation O)X ENS Option Informatique MP 2017X-ENS · 2017Corrigé
Même année, MinesMines Option Informatique MP 2007Mines · 2007Corrigé
Même année, CentraleCentrale Option Informatique MP 2007Centrale · 2007Corrigé
.jpg)
