X ENS Option Informatique MP MPI 2023Sujet, corrigé et rapport du jury

Compression entropique

5,0(1 vote)

Arbres binaires
Codes préfixes et algorithme de Huffman
Programmation dynamique et mémoïsation
Complexité algorithmique
Entropie de Shannon
Codage arithmétique (rANS)

Explorer les annales

BanqueX-ENS Année2023 FilièreMP/MPI MatièreInformatique

Annales X-ENS MP/MPI Informatique X-ENS MP/MPI 2023 MP/MPI Informatique Informatique 2023

Téléchargements

Télécharger le sujet (PDF)

Corrigé

Corrigé 2

Rapport du jury Lire en ligne LaTeX Word

Présentation du sujet

Difficile

Composition d'informatique X-ENS MP et MPI : compression de texte par codes préfixes et codes arithmétiques

Le sujet porte sur la compression d'un texte en fonction de la fréquence des lettres qui le composent. Il progresse du comptage des occurrences vers la représentation d'un alphabet par un arbre binaire, la construction d'un code préfixe, l'optimisation de l'arbre (approche proche de Huffman sans file de priorité), les arbres canoniques et alphabétiques, puis les codes arithmétiques de type rANS.

1Partie I : comptage des occurrencesComptage des occurrences des lettres dans un texte.
2Partie II : alphabet et arbre binaireReprésentation d'un alphabet comme feuilles d'un arbre binaire.
3Partie III : codes préfixesUn arbre binaire décrit un code préfixe, utilisé pour encoder et décoder un texte.
4Partie IV : arbre optimalConstruction d'un arbre optimal du point de vue de la taille du texte encodé, par une approche proche de l'algorithme de Huffman sans file de priorité.
5Parties V et VI : arbres canoniques et alphabétiquesÉtude de types d'arbres particuliers visant à limiter le coût de stockage de l'arbre lui-même.
6Partie VII : codes arithmétiques rANSÉtude de codes arithmétiques de type rANS, alternative aux codes préfixes dont la compression peut s'éloigner de l'entropie de Shannon.

Difficile. La moyenne des 880 candidats français en MP est de 9,68 sur 20 avec un écart-type de 3,60, et plusieurs questions de fin de sujet, comme VI.1 ou VII.2, n'ont été traitées avec succès que par une infime minorité de candidats.

L'épreuve en chiffres

Moyenne 9,68 / 20 · écart-type 3,6 · 880 présents · où vous situez-vous ?

Moyenne: 9,68/ 20
Écart-type: 3,6
Présents: 880
Durée: 4 h

Deux tiers des copies environ (moyenne ± écart-type)

Où je me situe ?

Votre note sur 20 à ce sujet, en conditions de concours.

Source : document officiel du concours, épreuve du 18 avril 2023. 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

5 erreurs relevées

Confusion entre listes et tableaux · Complexité mal évaluée pour la concaténation de listes · Récurrence non explicitée

Pour obtenir la note maximale, il n'était pas nécessaire de traiter l'intégralité du sujet. Le jury regrette que trop de candidats se jettent dans l'écriture d'algorithmes complexes sans réflexion préalable, alors que la plupart des codes attendus tiennent en moins de dix lignes.

Les erreurs les plus sanctionnées

1
Confusion entre listes et tableaux
Trop de copies transforment des listes en tableaux ou vice-versa, ce qui conduit à des codes inutilement compliqués, voire faux, et considèrent à tort ces opérations comme en temps constant.
2
Complexité mal évaluée pour la concaténation de listes
Le fait qu'une fonction effectue un nombre linéaire d'appels récursifs n'implique pas que la complexité totale soit linéaire ; la concaténation de liste n'est pas une opération élémentaire, sa complexité est linéaire en la taille de la liste de gauche.
3
Récurrence non explicitéeIII.1
Beaucoup de candidats raisonnent par récurrence en indiquant simplement et ainsi de suite ou on procède récursivement, sans indiquer sur quoi porte la récurrence.
4
Sens de parcours du tableau dynamique inverséVI.1
Beaucoup de copies donnent la bonne formule mais parcourent le tableau dynamique dans le mauvais sens, alors qu'une valeur dépend de cases situées plus loin dans le tableau.
5
Algorithme d'insertion inutilement longIV.4
Un nombre trop important de copies proposent un algorithme d'une page entière pour la fonction insert, alors qu'il s'agit d'un simple parcours de liste réalisable en moins de 5 lignes de code.

Ce qui a été bien réussi

La question I.1, très facile, a été traitée avec succès par la grande majorité des candidats des deux filières.
La question IV.1 ne présente pas de difficulté particulière et permet de se familiariser avec le type de raisonnement nécessaire pour les questions suivantes.
La question VII.1 permet, grâce à l'indication d'une borne sur la réponse attendue, de vérifier son propre résultat.

Conseils du jury

Réfléchir avant d'écrire un algorithme : la plupart des codes attendus tiennent en moins de dix à quinze lignes.
Bien distinguer listes et tableaux et leurs complexités d'accès respectives.
Donner l'intuition d'un algorithme en quelques lignes ou par un dessin lorsque son fonctionnement n'est pas évident, plutôt que de fournir un code long sans explication.

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.

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.

Sujet en PDF

ECOLE POLYTECHNIQUE ECOLES NORMALES SUPERIEURES

CONCOURS D'ADMISSION 2023

MARDI 18 AVRIL 2023
14h00-18h00
FILIERE MP-MPI - Epreuve

n^0 4

INFORMATIQUE A (XULSR)

Durée : 4 heures
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve

Cette composition ne concerne qu'une partie des candidats de la filière MP, les autres candidats effectuant simultanément la composition de Physique et Sciences de l'Ingénieur.
Pour la filière MP, il y a donc deux enveloppes de Sujets pour cette séance.

Compression entropique

Le sujet comporte 11 pages, numérotées de 1 à 11 .

Vue d'ensemble du sujet.

Ce sujet s'intéresse à la compression et à la décompression de mots sur un alphabet fini

S

de cardinal

|S| \geq 2

. Plus précisément, on se donne une fonction

q

S

dans

ℕ

et on s'intéresse aux mots de

S^*

tels que chaque lettre

σ \in S

a exactement

q(σ)

occurrences dans ces mots. On note

S^q

l'ensemble de ces mots. Remarque : les mots de

S^q

ont pour longueur

N = \sum_(σ \in S)q(σ)

Une lettre de

S

peut être représentée avec

⌈log_2|S|⌉

bits, où

⌈x⌉

désigne la partie entière supérieure de

x

, c'est-à-dire l'entier tel que

⌈x⌉ - 1 < x \leq ⌈x⌉

. Si l'on concatène les bits représentant chacune des lettres d'un mot de

S^q

, on peut donc représenter ce mot de façon non ambiguë à l'aide d'une séquence de bits de taille

\sum_(σ \in S)q(σ) \cdot ⌈log_2|S|⌉ = ⌈log_2|S|⌉ \cdot N.

Il s'agit d'une représentation non compressée.
La théorie de l'information affirme qu'il faut au moins

\sum_(σ \in S)q(σ) \cdot log_2(N/q(σ))

bits pour représenter tous les mots de

S^q

de façon non ambiguë. Ce sujet explore quelques façons de compresser les mots pour s'approcher de cette borne théorique.

La partie I s'intéresse à la fonction

q

, c'est-à-dire au comptage des lettres d'un mot. La partie II étudie les arbres binaires dont les feuilles sont étiquetées par des lettres de

S

. La partie III utilise ces arbres pour (dé)compresser des mots de

S^*

. La partie IV s'intéresse aux arbres qui donnent les meilleurs taux de compression pour les mots de

S^q

. Certains de ces arbres ont une représentation compacte ; c'est l'objet de la partie V. D'autres arbres sont encore plus compacts, mais au prix d'un moindre taux de compression, comme le montre la partie VI. Finalement, la partie VII attaque le problème d'une façon complètement différente afin de s'approcher un peu plus du taux de compression théorique optimal.

Les différentes parties sont indépendantes : il n'est pas nécessaire d'avoir répondu aux questions d'une partie pour répondre aux questions d'une autre partie; cependant les notions abordées dans une partie sont souvent utiles aux parties suivantes.

Rappels d'OCaml

On rappelle ici quelques opérations de base sur les tableaux :

Array. length t renvoie la longueur du tableau t .
Array.make n v crée un tableau de n cases qui sont toutes initialisées avec v .
Array. of list 1 renvoie un tableau initialisé avec les valeurs de la liste 1 , tandis que Array.to_list $t$ réalise l'opération inverse.
La case numéro i du tableau t peut être accédée avec t. (i). Les cases sont numérotées à partir de zéro.

Partie I. Comptage d'occurrences

Un texte non compressé est un mot de

S^*

. Dans la suite, à chaque fois qu'il s'agira de définir une fonction en OCaml, les lettres de

S

seront représentées par des entiers et un mot de

S^*

sera représenté par un tableau d'entiers (int array) ou une liste d'entiers (int list) en fonction des questions. La première étape consiste à calculer le nombre d'occurrences

q(σ)

de chaque lettre

σ

dans un mot.

Question I.1. Supposons

S = [0, 255]

. Définissez une fonction OCaml occurrences : int list -> int array qui reçoit en argument un mot représenté par une liste d'entiers et renvoie le nombre d'occurrences

q(σ)

de chaque lettre

σ \in S

sous forme d'un tableau

[ [q(0); q(1); \dots

;

q(255)] ]

Il peut être intéressant de ne considérer que le sous-ensemble des lettres qui ont au moins une occurrence. Dans la question suivante, on ne représentera pas

q

par

[ [q(0); q(1); \dots; q(|S| - 1)] ]

mais par un tableau de paires

[ [(σ_1, q(σ_1)); (σ_2, q(σ_2)); \dots] ]

avec

{σ_1, σ_2, …} = {σ ∈ S|q(σ) ≠ 0}

σ_1 < σ_2 < \dots

Question I.2. Définissez une fonction OCaml nonzero_occurrences : int array -> (int * int) array qui passe de la représentation de

q

de la question I. 1 (tableau

[ [q(0); q(1); \dots

;

q(|S| - 1)] ])

à la représentation sous forme d'un tableau de paires. Cette fonction devra avoir une complexité temporelle en

O(|S|)

Partie II. Arbres binaires

Soit

T_S

l'ensemble des arbres binaires dont les feuilles sont en bijection avec un ensemble fini

S

. Autrement dit, un arbre de

T_S

a exactement

|S|

feuilles; chacune de ses feuilles est étiquetée par un élément de

S

; toutes les feuilles sont étiquetées par des éléments différents de

S

. Ces arbres peuvent être construits comme suit:

Une feuille étiquetée par $x$ est notée $F(x)$ . C'est un arbre de $T_({x})$ .
Si $g$ et $d$ sont des arbres appartenant respectivement à $T_(S_1)$ et $T_(S_2)$ , alors l'arbre dont le sous-arbre gauche est $g$ et le sous-arbre droit est $d$ , noté $N(g, d)$ , est un arbre de $T_(S_1 \cup S_2)$ à condition que $S_1 \cap S_2 = \emptyset$ .
Remarque : un tel arbre binaire possède exactement $|S| - 1$ nœuds internes. Par ailleurs, on étiquettera implicitement les arêtes par 0 ou 1 suivant qu'elles mènent à un sous-arbre gauche (0) ou droit (1).

Figure 1 - Exemple d'arbre de

T_({A, B, C, D})

Question II.1. Montrez que l'ensemble

T_({A, B, C, D})

contient 120 arbres.
Le type OCaml utilisé pour représenter les arbres est le suivant :
type tree

= F

of int

|N

of tree

*

tree
Étant donnés un arbre

t

T_S

et un élément

σ

S

, on note

ℓ_t(σ)

la profondeur de la feuille étiquetée par

σ

, c'est-à-dire le nombre d'arêtes entre la racine de

t

et cette feuille. Par exemple, avec l'arbre de la figure 1 , on a

ℓ_t(A) = 3

Comme précédemment, soit

q

une fonction de

S

dans

ℕ

. Pour tout arbre

t \in T_(S^')

avec

S^' \subseteq S

, on note

c_q(t)

la somme pondérée suivante :

c_q(t) = \sum_(σ \in S^')q(σ)ℓ_t(σ).

Question II.2. Supposons

S = [0, n - 1]

. Définissez une fonction

OCamlcq : tree - > int

array

- >

int qui reçoit deux arguments, un arbre

t \in T_S

et un tableau

[ [q(0); q(1); \dots; q(n - 1)] ]

représentant

q

, et qui renvoie la valeur de

c_q(t)

. On cherchera à écrire une fonction efficace. Donnez et justifiez sa complexité temporelle.

Étant donné un arbre

t

T_S

, on représente une lettre

σ \in S

par la séquence des bits obtenus en parcourant

t

de la racine vers la feuille

F(σ)

. Par exemple, dans l'arbre de

T_({A, B, C, D})

de la figure 1, D est représenté par 0 tandis que

A

est représenté par 100.

Question II.3. Définissez une fonction OCaml get_path : int -> tree -> int list qui reçoit en argument un entier

σ \in S

et un arbre

t \in T_S

et qui renvoie la liste de 0 et 1 représentant

σ

dans

t

. Donnez et justifiez la complexité temporelle de cette fonction.

Considérons les séquences de bits définies de la façon suivante. Elles commencent par

k \geq 0

bits valant 1 , suivis d'un bit à 0 , suivis de

k

bits arbitraires, ce que l'on notera

1^k 0(0|1)^k

. Les dix premières séquences par ordre lexicographique sont donc

0, 100, 101, 11000, 11001, 11010

, 11011, 1110000, 1110001, 1110010. L'arbre dont les branches constituent ces séquences et dont les feuilles sont étiquetées de gauche à droite par des entiers croissants commence comme illustré sur la figure 2.

Figure 2 - Arbre des séquences

1^k 0(0|1)^k

Remarque : l'étiquette de chaque feuille correspond à l'indice de la séquence quand elles sont triées par ordre lexicographique. Les séquences croissant indéfiniment, l'arbre est a priori infini. C'est pourquoi la question suivante se limite aux séquences de bits

1^k 0(0|1)^k

pour lesquelles

k

n'excède pas une certaine borne

ℓ

, afin d'obtenir un arbre de profondeur bornée

2ℓ + 1

Question II.4. Définissez une fonction OCaml integers : int -> tree qui prend un entier

ℓ \geq 0

en argument et renvoie l'arbre dont les branches sont les séquences de la forme

1^k 0(0|1)^k

avec

k \leq ℓ

, ainsi que la séquence

1^(ℓ + 1)

. Les feuilles seront étiquetées de gauche à droite par les entiers

0, 1, 2

, etc.

Partie III. Codes préfixes

Étant donnés un alphabet

S

et un arbre

t

T_S

, un mot de

S^*

peut être représenté par la concaténation des séquences de bits représentant chacune de ses lettres dans

t

, de la gauche vers la droite. Supposons que l'arbre

t

est l'exemple de la figure 1. Le mot « ADBDCD » est alors représenté par la séquence de bits

100|0|11|0|101|0

. Remarque : les barres verticales ne servent qu'à rendre l'exemple plus lisible; elles ne font pas partie de la séquence de bits et ne sont pas nécessaires pour retrouver le mot initial.

Question III.1. Soit

t

un arbre de

T_S

. Étant donnée une séquence de bits, montrez qu'il existe au plus un mot de

S^*

qui est représenté par cette séquence.

Question III.2. Supposons

S \subseteq ℕ

. Définissez une fonction OCaml decomp1 : int list -> tree -> int list qui reçoit en argument une liste d'entiers 0 ou 1 et un arbre de

T_S

et qui renvoie la liste des éléments de

S

représentée par cette liste de bits. On sera attentif au cas où la liste en argument ne représente aucun mot de

S^*

. Donnez et justifiez la complexité temporelle de cette fonction.

Cette fonction est dite de décompression. Supposons que

S

est

{A, B, C, D}

et que la fonction

q

donne le nombre d'occurrences de chaque lettre dans le mot « ADBDCD », par exemple

q(D) = 3

. Dans ce cas,

c_q(t)

vaut 11 pour l'arbre exemple de la Figure 1. Il s'agit de la longueur de la séquence 10001101010 représentant le mot « ADBDCD ». Plus généralement,

c_q(t)

est la longueur de n'importe quelle séquence représentant un mot de

S^q

compressé avec l'arbre

t

. Il s'avère qu'il n'existe aucun arbre

t^' \in T_S

tel que

c_q(t^') < 11; t

est donc optimal.

Étant donnée une fonction

q

, l'objectif de la partie suivante sera de construire un des arbres de

T_S

offrant la meilleure compression des mots de

S^q

, c'est-à-dire un arbre qui minimise

c_q

Partie IV. Arbres optimaux

Soit

q

une fonction dont le domaine inclut

S

. Un arbre de

T_S

est dit optimal pour (

q, S

) s'il minimise

c_q

parmi tous les arbres de

T_S

. Autrement dit, un arbre optimal

t \in T_S

vérifie

c_q(t) = min_(t^' \in T_S)c_q(t^')

. De tels arbres optimaux existent et, dès lors que

|S| \geq 2

, ils ne sont pas uniques.

Question IV.1. Soit

t = N(g, d) \in T_S

un arbre optimal pour (

q, S

). Soit

S_g

l'ensemble des lettres qui étiquettent les feuilles du sous-arbre

g

. Montrez que

g

est un arbre de

T_(S_g)

optimal pour

(q, S_g)

Malheureusement, cette propriété ne permet pas d'en déduire un algorithme de type « diviser pour régner

≫

pour trouver l'arbre optimal. En effet, il faudrait que l'algorithme puisse efficacement deviner comment partitionner

S

entre les feuilles du sous-arbre gauche et celles du sous-arbre droit.

Question IV.2. Supposons qu'il existe une lettre

σ_0 \in S

telle que

q(σ_0) > ∑_(σ ∈ S∖{σ_0})q(σ)

. Montrez que, pour tout arbre de

T_S

optimal pour (

q, S

), la feuille

F(σ_0)

est à profondeur 1 , c'est-à-dire directement attachée à la racine.

Question IV.3. Soient

σ_1

σ_2

deux éléments différents de

S

tels que, pour tout

σ ∈ S∖{σ_1, σ_2}

, on a

q(σ) \geq q(σ_1)

q(σ) \geq q(σ_2)

. Soit

S^′ = S∖{σ_1, σ_2} ∪ {σ_3}

avec

σ_3

un tout nouvel élément. On définit

q^'

de telle sorte que

q^'(σ_3) = q(σ_1) + q(σ_2)

∀σ ∈ S∖{σ_1, σ_2}, q^′(σ) = q(σ)

Montrez qu'il existe un arbre $t$ de $T_S$ optimal pour ( $q, S$ ) ayant un noud $N(F(σ_1), F(σ_2))$ .
Soit un arbre $t^'$ de $T_(S^')$ optimal pour ( $q^', S^'$ ). Montrez que l'arbre $t \in T_S$ obtenu en remplaçant dans $t^'$ la feuille $F(σ_3)$ par $N(F(σ_1), F(σ_2))$ est optimal pour ( $q, S$ ).

On définit la fonction

q¯

en étendant la fonction

q

aux arbres de la façon suivante. Pour une feuille,

q¯(F(σ))

vaut

q(σ)

. Pour un nœud interne,

q¯(N(g, d))

vaut récursivement

q¯(g) + q¯(d)

. Remarque : en général,

c_q(t) \neq q¯(t)

La question précédente montre qu'il est possible de construire un arbre optimal pour (

q, S

) à l'aide de l'algorithme suivant. On initialise un ensemble d'arbres

E

avec toutes les feuilles

F(σ)

avec

σ \in S

. À chaque étape, on retire de

E

deux arbres

t_1

t_2

qui minimisent

q¯

; puis on ajoute à

E

l'arbre

N(t_1, t_2)

. On répète cette procédure jusqu'à ce qu'il ne reste qu'un seul arbre dans

E

. Il s'agit alors d'un arbre optimal pour (

q, S

Question IV.4. Implantez l'algorithme décrit ci-dessus en définissant les deux fonctions OCaml suivantes : insert et optimal.

La fonction insert : (int * tree) -> (int * tree) list -> (int * tree) list insère dans une liste son premier argument. La liste en argument est supposée triée par rapport à la première composante de chacune de ses paires. La liste renvoyée doit l'être aussi.
La fonction optimal : (int * int) list -> tree renvoie un arbre optimal. La liste passée en argument est de taille $|S|$ ; elle contient toutes les paires ( $σ, q(σ)$ ) pour $σ \in S$ ; ces paires sont triées par valeur croissante de $q(σ)$ .
Donnez et justifiez la complexité temporelle de la fonction optimal.

Les deux questions suivantes montrent que, quand la liste initiale des (

σ, q(σ)

) est triée par valeur croissante de

q(σ)

, de simples listes et/ou tableaux suffisent pour écrire une fonction optimal dont la complexité temporelle est en

O(|S|)

Question IV.5. Montrez que, lors de l'exécution de l'algorithme décrit ci-dessus, les arbres

t = N(t_1, t_2)

sont ajoutés à l'ensemble

E

par valeur croissante de

q¯(t)

Question IV.6. Expliquez comment écrire la fonction optimal pour que sa complexité temporelle soit linéaire. Le code OCaml n'est pas demandé.

Cette partie a permis de calculer un arbre qui minimise la longueur

c_q

de la séquence de bits représentant un mot de

S^q

. Mais pour décompresser ce mot, il faut disposer de l'arbre et donc l'avoir stocké quelque part. Parmi tous les arbres optimaux, il est donc important d'en choisir un qui nécessitera le moins de bits pour être représenté ; c'est l'objet de la partie suivante.

Partie V. Arbres canoniques

On suppose maintenant qu'il existe un ordre alphabétique noté

<

sur les éléments de

S

. Pour

S \subseteq ℕ

, il s'agira de l'ordre usuel sur

ℕ

. Soit

t

un arbre de

T_S

. On définit la relation

≺_t

entre éléments de

S

de la façon suivante : pour toute paire

(σ_1, σ_2) \in S^2

σ_1≺_t σ_2 \Leftrightarrow ℓ_t(σ_1) < ℓ_t(σ_2) ou (ℓ_t(σ_1) = ℓ_t(σ_2) et σ_1 < σ_2).

L'arbre

t

est dit canonique si, en parcourant les feuilles de la gauche vers la droite, leurs étiquettes respectent la relation

≺_t

. Autrement dit, plus une feuille est à gauche, plus elle est proche de la racine; et les étiquettes des feuilles à une même profondeur sont triées de gauche à droite par ordre alphabétique.

L'arbre de la figure 1 vérifie bien la deuxième partie de la propriété : les feuilles à une même profondeur sont triées de gauche à droite par ordre alphabétique. Mais il ne respecte pas la première partie : la feuille étiquetée par

A

est plus profonde que celle étiquetée par

B

alors qu'elle est plus à gauche. Cet arbre n'est donc pas canonique. L'arbre suivant est par contre canonique :

Figure 3 - Exemple d'arbre canonique.

Un arbre canonique peut être représenté par deux tableaux d'entiers. Le premier tableau associe à chaque indice

i

le nombre de lettres

σ \in S

telles que

ℓ_t(σ) = i

. Le deuxième tableau contient les éléments de

S

obtenus en parcourant les feuilles de l'arbre de gauche à droite. Ainsi, l'arbre de

T_([0, 4])

de la figure 3 est représenté par les deux tableaux

[ [0; 0; 3; 2] ]

[ [1; 3; 4; 0; 2] ]

Question V.1. Définissez une fonction OCaml canonical : int array -> int array -> tree qui, étant donnés deux tels tableaux, renvoie l'arbre canonique qu'ils représentent, s'il existe. Donnez et justifiez la complexité temporelle de cette fonction.

Partie VI. Arbres alphabétiques

L'arbre de la figure 1 était optimal pour le mot « ADBDCD ». Un autre arbre optimal pour ce mot est le suivant :

Figure 4 - Arbre à la fois optimal pour le mot « ADBDCD » et alphabétique.

Il n'est pas canonique mais il a une propriété très intéressante : ses feuilles sont dans l'ordre alphabétique. Cela signifie que lors du stockage de l'arbre, il n'est pas nécessaire de stocker les étiquettes des feuilles, il suffit de stocker la forme de l'arbre. Un tel arbre est dit alphabétique.

Plus généralement, un arbre de

T_S

est alphabétique si, en parcourant ses feuilles de gauche à droite, les étiquettes apparaissent dans l'ordre alphabétique. On note

A_S

l'ensemble de ces arbres. On dit d'un arbre qu'il est alphabétique-optimal pour (

q, S

) s'il minimise

c_q

parmi tous les arbres de

A_S

. Remarque : un arbre alphabétique-optimal pour (

q, S

) n'est pas nécessairement optimal pour (

q, S

Soit

n \in ℕ

S = [0, n - 1]

. On se donne une fonction

q : S \to ℕ

. Étant donnés deux entiers

i

j

tels que

0 \leq i \leq j < n

, on note

m_(i, j)

la valeur de

c_q(t)

pour n'importe quel arbre

t

A_([i, j])

alphabétique-optimal pour (

q, [i, j]

). En particulier, si

t

est un arbre de

A_S

alphabétique-optimal pour (

q, S

), il vérifie

c_q(t) = m_(0, n - 1)

Question VI.1. Exprimez la valeur de

m_(i, j)

en fonction des valeurs de

m_(i^', j^')

avec

[i^', j^'] ⊊ [i, j]

. Déduisez en une fonction OCaml alpha_optimal : int array -> tree qui calcule un arbre de

A_([0, n - 1])

alphabétique-optimal pour (

q, [0, n - 1]

). La fonction

q

est donnée par le tableau de taille

n

passé en argument. La complexité temporelle de la fonction devra être en

O(n^3)

Un arbre alphabétique de

A_([0, n - 1])

peut être représenté par la séquence de

2n - 1

bits obtenue en effectuant un parcours en profondeur préfixe, c'est-à-dire que la racine d'un sous-arbre est visité avant ses feuilles et qu'un sous-arbre gauche est parcouru avant un sous-arbre droit. Pour chaque nœud, les chiffres 0 et 1 indiquent respectivement s'il s'agit d'un nœud interne ou d'une feuille. Par exemple, l'arbre de la figure 4 est représenté par la séquence 0001111.

Question VI.2. Définissez une fonction OCaml alpha : int array -> tree qui reçoit en argument un tableau de 0 et 1 et renvoie l'arbre alphabétique correspondant. On sera attentif au cas où le tableau en argument ne représente aucun arbre. Cette fonction devra avoir une complexité temporelle en

O(n)

avec

n

la taille du tableau.

Partie VII. Codes arithmétiques

Soient un alphabet

S

et une fonction

q : S \to ℕ

. Comme précédemment,

S^q

est le sousensemble des mots de

S^*

qui contiennent exactement

q(σ)

occurrences de

σ

pour chaque

σ \in S

Question VII.1. Supposons que

S

est

{A, B, C}

et que

q

satisfait

q(A) = 15, q(B) = 4

q(C) = 1

Combien de bits faut-il pour représenter un mot de $S^q$ en utilisant un arbre optimal pour $(q, S)$ ?
Combien y a-t-il de mots dans $S^q$ ? On pourra exprimer ce nombre sous forme d'un produit de nombres premiers.
Montrez que 17 bits suffisent pour représenter chaque entier entre 0 et $|S^q| - 1$ (et donc n'importe quel mot de $S^q$ ). Remarque : $15 \cdot 17 = 2^8 - 1$ .

L'exemple de la question précédente montre que, dans certains cas, par exemple quand une lettre est bien plus fréquente que les autres, l'utilisation d'un code préfixe n'est pas l'approche optimale. Il faut alors se tourner vers d'autres mécanismes de compression.

On se restreint maintenant au cas où

S = [0, n - 1]

. Soit

N = \sum_(σ \in S)q(σ)

. La fonction

E_q : ℕ \times S \to ℕ

est définie de la façon suivante pour

q(σ) \neq 0

E_q(x, σ) = ⌊x/q(σ)⌋ \cdot N + (xmodq(σ)) + \sum_(0 \leq k < σ)q(k)

où

⌊a⌋

désigne la partie entière de

a

.
La fonction

E_q

peut être étendue en une fonction

C_q : ℕ \times S^* \to ℕ

qui travaille sur les mots de la façon suivante :

C_q(x, σ_0 σ_1\dotsσ_k) = E_q(\dotsE_q(E_q(x, σ_0), σ_1), \dotsσ_k)

Ainsi, après avoir choisi

x

arbitrairement, un mot

σ_0\dotsσ_(N - 1) \in S^q

peut être compressé en un entier

y = C_q(x, σ_0\dotsσ_(N - 1))

. Il est alors possible de retrouver le mot original à partir de

y

en calculant progressivement

σ_(N - 1), σ_(N - 2)

, etc, jusqu'à

σ_0

Considérons par exemple le mot

⟨0120000⟩(N = 7, q = [ [5, 1, 1] ])

. Si l'on part de

x = 0

, sa version compressée sera l'entier 151 :

0 \to ^0 0 \to ^1 5 \to ^2 41 \to ^0 57 \to ^0 79 \to ^0 109 \to ^0 151

où

x \to ^σ y

signifie

E_q(x, σ) = y

Question VII.2. Définissez une fonction OCaml decomp2 : int array -> int -> int -> int * int array qui reçoit en argument un tableau représentant

q

et deux entiers

y

k

, et renvoie un entier

x

et un tableau

[ [σ_0, σ_1, \dots, σ_(k - 1)] ]

tels que

E_q(x, σ_0 σ_1\dotsσ_(k - 1)) = y

Le nombre de bits de l'entier

C_q(x, σ_0\dotsσ_(N - 1))

est proche de l'optimum théorique

\sum_(σ \in S)q(σ)

log_2(N/q(σ))

mais un problème se pose en pratique. Sauf pour de tout petits mots sur de tout petits alphabets, le calcul de

C_q(x, σ_0\dotsσ_(N - 1))

va nécessiter de manipuler des entiers très grands. Pour éviter ce problème, une solution consiste, avant chaque appel à

E_q

, à se débarrasser d'un certain nombre

k_i

de bits de poids faible. Plus précisément, on construit les suites

(x_n)

(y_n)

suivantes:

{y_i, = ⌊x_i/2^(k_i)⌋; x_(i + 1), = E_q(y_i, σ_i)

Comme précédemment, la valeur de

x_0

est fixée arbitrairement. Le mot

σ_0\dotsσ_(N - 1)

peut alors être représenté par d'une part

x_N

et d'autre part la concaténation des séquences de bits suivantes, les bits de poids forts apparaissant en premier :

x_(N - 1)mod2^(k_(N - 1))_()_(k_(N - 1) bits); \dots; x_2 mod2^(k_2)_()_(k_2 bits); x_1 mod2^(k_1)_()_(k_1 bits).

Pour chaque

i

en ordre décroissant, le décompresseur déduit de

x_(i + 1)

les valeurs de

y_i

σ_i

(par exemple avec decomp2, question VII.2, avec

k = 1

), puis il lit

k_i

bits dans le mot compressé et les concatène à

y_i

pour obtenir

x_i

, et ainsi de suite jusqu'à avoir décompressé tout le mot.

Dans la suite, on supposera que

N

est une puissance de deux :

N = 2^K

. On supposera par ailleurs que le processeur n'est efficace que pour des entiers ne dépassant pas

2^B

pour un certain

B

bien plus grand que

K

. En particulier,

x_(i + 1) = E_q(y_i, σ_i)

ne doit jamais atteindre cette borne

2^B

lors de la compression.

Pour que le taux de compression se rapproche de l'optimum théorique, il faut que chaque

k_i

soit le plus petit possible (idéalement 0 ) et donc que chaque

y_i

soit le plus grand possible. Par ailleurs, les différents

k_i

ne font pas partie du mot compressé. Autrement dit, en ne connaissant que

y_i

, le décompresseur doit pouvoir deviner le nombre

k_i

de bits qui doivent être lus dans le mot compressé pour reconstruire

x_i

. Une solution correcte mais mauvaise serait, par exemple, de fixer tous les

k_i

à la constante

K

; le décompresseur pourrait alors deviner trivialement les

k_i

mais le mot résultant ne serait absolument pas compressé.

Question VII.3. Proposez une façon pour le compresseur de choisir

k_i

en fonction de

x_i

σ_i

. Expliquez comment le décompresseur choisit

k_i

en fonction de

y_i

et prouvez que ce choix correspond bien à celui du compresseur. Si cela a une importance, expliquez comment le compresseur doit choisir

x_0

Remarque : la contrainte imposant que

N

soit une puissance de deux ne pose aucune difficulté en pratique. En effet, en matière de compression entropique, la seule chose qui importe est que

q(σ)/N

soit proche de la proportion de la lettre

σ

dans le mot à compresser.

Fin du sujet.

Questions fréquentes

3 questions

Sur quels chapitres porte la composition d'informatique X-ENS MP-MPI 2023 ?

Elle porte sur les arbres binaires, les codes préfixes et l'algorithme de Huffman, la programmation dynamique, la complexité algorithmique et les codes arithmétiques de type rANS, dans le cadre de la compression de texte.

Quelles erreurs le jury a-t-il le plus relevées à l'X-ENS informatique MP-MPI 2023 ?

Une confusion entre listes et tableaux, une mauvaise évaluation de la complexité de la concaténation de listes, des récurrences non explicitées, et un sens de parcours inversé dans un tableau de programmation dynamique.

L'épreuve d'informatique X-ENS MP-MPI 2023 est-elle difficile ?

Oui, la moyenne des candidats MP s'établit à 9,68 sur 20 avec un écart-type de 3,60, et plusieurs questions de fin de sujet n'ont été réussies que par une très faible proportion de candidats.

Pas de description pour le moment

Commentaires• X ENS Option Informatique MP MPI 2023

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...