X/ENS Informatique A MP 2023

ECOLE POLYTECHNIQUE
ECOLES NORMALES SUPERIEURES
CONCOURS D'ADMISSION 2023

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

-

Epreuve n° 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|  2. Plus précisément, on se donne une fonction q de S dans N et on s'intéresse
aux mots de S  tels que chaque lettre   S a exactement q() occurrences dans ces
Pmots. On
q
q
note S l'ensemble de ces mots. Remarque : les mots de S ont pour longueur N = S q().
Une lettre de S peut être représentée avec log2 |S| bits, où x désigne la partie entière
supérieure de x, c'est-à-dire l'entier tel que x - 1 < x  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 X q() · log2 |S| = log2 |S| · N. S Il s'agit d'une représentation non compressée. P La théorie de l'information affirme qu'il faut au moins S q() · log2 (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 l renvoie un tableau initialisé avec les valeurs de la liste l, 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. 1 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   S sous forme d'un tableau [[q(0); q(1); . . . ;
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); . . . ; q(|S| - 1)]]
mais par un tableau de paires [[(1 , q(1 )); (2 , q(2 )); . . .]] avec {1 , 2 , . . .} = {  S | q() =
0} et 1 < 2 < . . . 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); . . . ;
q(|S| - 1)]]) à la représentation sous forme d'un tableau de paires. Cette fonction devra avoir
une complexité temporelle en O(|S|).

2

Partie II. Arbres binaires
Soit TS l'ensemble des arbres binaires dont les feuilles sont en bijection avec un ensemble
fini S. Autrement dit, un arbre de TS 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 à TS1 et TS2 , 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 TS1 S2
à condition que S1  S2 = .
Remarque : un tel arbre binaire possède exactement |S| - 1 noeuds 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).
0

1

D
1
B

0
0
A

1
C

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 de TS et un élément  de 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 N. Pour tout arbre t  TS  avec

S  S, on note cq (t) la somme pondérée suivante :
X
cq (t) =
q()t ().
S 

Question II.2. Supposons S = [0, n - 1]. Définissez une fonction OCaml cq : tree -> int
array -> int qui reçoit deux arguments, un arbre t  TS et un tableau [[q(0); q(1); . . . ; q(n-1)]]
représentant q, et qui renvoie la valeur de cq (t). On cherchera à écrire une fonction efficace.
Donnez et justifiez sa complexité temporelle.
Étant donné un arbre t de TS , on représente une lettre   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.

3

Question II.3. Définissez une fonction OCaml get_path : int -> tree -> int list qui
reçoit en argument un entier   S et un arbre t  TS 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  0
bits valant 1, suivis d'un bit à 0, suivis de k bits arbitraires, ce que l'on notera 1k 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.
0

1

0
0
0

1
0

1

1

2

1

3. . .6

7. . .

Figure 2 ­ Arbre des séquences 1k 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 1k 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
  0 en argument et renvoie l'arbre dont les branches sont les séquences de la forme 1k 0(0 | 1)k
avec k  , ainsi que la séquence 1+1 . Les feuilles seront étiquetées de gauche à droite par les
entiers 0, 1, 2, etc.

4

Partie III. Codes préfixes

Étant donnés un alphabet S et un arbre t de TS , 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 TS . É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  N. 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 TS 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, cq (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, cq (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  TS tel que cq (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 TS offrant la meilleure compression des mots de S q , c'est-à-dire un arbre qui minimise cq . 5 Partie IV. Arbres optimaux Soit q une fonction dont le domaine inclut S. Un arbre de TS est dit optimal pour (q, S) s'il minimise cq parmi tous les arbres de TS . Autrement dit, un arbre optimal t  TS vérifie cq (t) = mint TS cq (t ). De tels arbres optimaux existent et, dès lors que |S|  2, ils ne sont pas uniques. Question IV.1. Soit t = N (g, d)  TS un arbre optimal pour (q, S). Soit Sg l'ensemble des lettres qui étiquettent les feuilles du sous-arbre g. Montrez que g est un arbre de TSg optimal pour (q, Sg ). 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. P Question IV.2. Supposons qu'il existe une lettre 0  S telle que q(0 ) > S\{0 } q().
Montrez que, pour tout arbre de TS optimal pour (q, S), la feuille F (0 ) est à profondeur 1,
c'est-à-dire directement attachée à la racine.

Question IV.3. Soient 1 et 2 deux éléments différents de S tels que, pour tout   S \
{1 , 2 }, on a q()  q(1 ) et q()  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 ) et   S \{1 , 2 }, q  () = q().
1. Montrez qu'il existe un arbre t de TS optimal pour (q, S) ayant un noeud N (F (1 ), F (2 )).
2. Soit un arbre t de TS  optimal pour (q  , S  ). Montrez que l'arbre t  TS 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 noeud interne, q(N (g, d)) vaut récursivement q(g) + q(d).
Remarque : en général, cq (t) = 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   S. À chaque étape, on retire de E deux arbres t1 et t2 qui minimisent q ; puis
on ajoute à E l'arbre N (t1 , t2 ). 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).

6

Question IV.4. Implantez l'algorithme décrit ci-dessus en définissant les deux fonctions
OCaml suivantes : insert et optimal.
1. 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.
2. 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   S ;
ces paires sont triées par valeur croissante de q().
3. 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 (t1 , t2 ) 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 cq 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.

7

Partie V. Arbres canoniques

On suppose maintenant qu'il existe un ordre alphabétique noté < sur les éléments de S. Pour S  N, il s'agira de l'ordre usuel sur N. Soit t un arbre de TS . On définit la relation t entre éléments de S de la façon suivante : pour toute paire (1 , 2 )  S 2 , 1 t 2 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 : 1 3 4 0 2 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   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]] et [[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.

8

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 :

D
C
A

B

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 TS est alphabétique si, en parcourant ses feuilles de gauche
à droite, les étiquettes apparaissent dans l'ordre alphabétique. On note AS l'ensemble de ces
arbres. On dit d'un arbre qu'il est alphabétique-optimal pour (q, S) s'il minimise cq parmi tous les
arbres de AS . Remarque : un arbre alphabétique-optimal pour (q, S) n'est pas nécessairement
optimal pour (q, S).
Soit n  N et S = [0, n - 1]. On se donne une fonction q : S  N. Étant donnés deux
entiers i et j tels que 0  i  j < n, on note mi,j la valeur de cq (t) pour n'importe quel arbre t de A[i,j] alphabétique-optimal pour (q, [i, j]). En particulier, si t est un arbre de AS alphabétique-optimal pour (q, S), il vérifie cq (t) = m0,n-1 . Question VI.1. Exprimez la valeur de mi,j en fonction des valeurs de mi ,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(n3 ).
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 noeud, les chiffres 0 et 1 indiquent respectivement s'il s'agit d'un noeud 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.

9

Partie VII. Codes arithmétiques

Soient un alphabet S et une fonction q : S  N. Comme précédemment, S q est le sousensemble des mots de S  qui contiennent exactement q() occurrences de  pour chaque   S.
Question VII.1. Supposons que S est {A, B, C} et que q satisfait q(A) = 15, q(B) = 4,
q(C) = 1.
1. Combien de bits faut-il pour représenter un mot de S q en utilisant un arbre optimal
pour (q, S) ?
2. Combien y a-t-il de mots dans S q ? On pourra exprimer ce nombre sous forme d'un
produit de nombres premiers.
3. 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 · 17 = 28 - 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.
P
On se restreint maintenant au cas où S = [0, n - 1]. Soit N =
S q(). La fonction
Eq : N × S  N est définie de la façon suivante pour q() = 0 :
X
Eq (x, ) = x/q() · N + (x mod q()) +
q(k),
0k< où a désigne la partie entière de a. La fonction Eq peut être étendue en une fonction Cq : N × S   N qui travaille sur les mots de la façon suivante : Cq (x, 0 1 . . . k ) = Eq (. . . Eq (Eq (x, 0 ), 1 ), . . . k ). Ainsi, après avoir choisi x arbitrairement, un mot 0 . . . N -1  S q peut être compressé en un entier y = Cq (x, 0 . . . 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 1 2 0 0 0 0 0 - 0 - 5 - 41 - 57 - 79 - 109 - 151 où x - y signifie Eq (x, ) = y. 10 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 et k, et
renvoie un entier x et un tableau [[0 , 1 , . . . , k-1 ]] tels que Eq (x, 0 1 . . . k-1 ) = y.
P
Le nombre de bits de l'entier Cq (x, 0 . . . N -1 ) est proche de l'optimum théorique S q()·
log2 (N/q()) mais un problème se pose en pratique. Sauf pour de tout petits mots sur de tout
petits alphabets, le calcul de Cq (x, 0 . . . N -1 ) va nécessiter de manipuler des entiers très
grands. Pour éviter ce problème, une solution consiste, avant chaque appel à Eq , à se débarrasser d'un certain nombre ki de bits de poids faible. Plus précisément, on construit les suites
(xn ) et (yn ) suivantes :

yi = xi /2ki 
xi+1 = Eq (yi , i )
Comme précédemment, la valeur de x0 est fixée arbitrairement. Le mot 0 . . . N -1 peut
alors être représenté par d'une part xN et d'autre part la concaténation des séquences de bits
suivantes, les bits de poids forts apparaissant en premier :
x
mod 2kN -1 ;
| N -1 {z
}
kN -1 bits

...;

x2 mod 2k2 ;
|
{z
}
k2 bits

x1 mod 2k1 .
|
{z
}
k1 bits

Pour chaque i en ordre décroissant, le décompresseur déduit de xi+1 les valeurs de yi et
i (par exemple avec decomp2, question VII.2, avec k = 1), puis il lit ki bits dans le mot
compressé et les concatène à yi pour obtenir xi , et ainsi de suite jusqu'à avoir décompressé tout
le mot.
Dans la suite, on supposera que N est une puissance de deux : N = 2K . On supposera
par ailleurs que le processeur n'est efficace que pour des entiers ne dépassant pas 2B pour un
certain B bien plus grand que K. En particulier, xi+1 = Eq (yi , i ) ne doit jamais atteindre
cette borne 2B lors de la compression.
Pour que le taux de compression se rapproche de l'optimum théorique, il faut que chaque ki
soit le plus petit possible (idéalement 0) et donc que chaque yi soit le plus grand possible. Par
ailleurs, les différents ki ne font pas partie du mot compressé. Autrement dit, en ne connaissant
que yi , le décompresseur doit pouvoir deviner le nombre ki de bits qui doivent être lus dans le
mot compressé pour reconstruire xi . Une solution correcte mais mauvaise serait, par exemple,
de fixer tous les ki à la constante K ; le décompresseur pourrait alors deviner trivialement les
ki mais le mot résultant ne serait absolument pas compressé.
Question VII.3. Proposez une façon pour le compresseur de choisir ki en fonction de xi
et i . Expliquez comment le décompresseur choisit ki en fonction de yi et prouvez que ce
choix correspond bien à celui du compresseur. Si cela a une importance, expliquez comment le
compresseur doit choisir x0 .
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.

11