J-0
00m
00j
00h
00min
00s

Version interactive avec LaTeX compilé

Télécharger PDF

X ENS Option Informatique MP MPI 2023

Compression entropique

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Logo x-ens
🔗 Explorer
Banque
X-ENS
Année
2023
Filière
MP/MPI
Matière
Info
X-ENS MP/MPIX-ENS 2023MP/MPI InfoInfo 2023
2025_08_29_f62c51ed50ed100ca251g

ECOLE POLYTECHNIQUE ECOLES NORMALES SUPERIEURES

CONCOURS D'ADMISSION 2023

MARDI 18 AVRIL 2023
14h00-18h00
FILIERE MP-MPI - Epreuve
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 de cardinal . Plus précisément, on se donne une fonction de dans et on s'intéresse aux mots de tels que chaque lettre a exactement occurrences dans ces mots. On note l'ensemble de ces mots. Remarque : les mots de ont pour longueur .
Une lettre de peut être représentée avec bits, où désigne la partie entière supérieure de , c'est-à-dire l'entier tel que . Si l'on concatène les bits représentant chacune des lettres d'un mot de , on peut donc représenter ce mot de façon non ambiguë à l'aide d'une séquence de bits de taille
Il s'agit d'une représentation non compressée.
La théorie de l'information affirme qu'il faut au moins bits pour représenter tous les mots de 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 , 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 . La partie III utilise ces arbres pour (dé)compresser des mots de . La partie IV s'intéresse aux arbres qui donnent les meilleurs taux de compression pour les mots de . 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 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 . Dans la suite, à chaque fois qu'il s'agira de définir une fonction en OCaml, les lettres de seront représentées par des entiers et un mot de 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 de chaque lettre dans un mot.
Question I.1. Supposons . 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 de chaque lettre sous forme d'un tableau ; .
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 par mais par un tableau de paires avec et
Question I.2. Définissez une fonction OCaml nonzero_occurrences : int array -> (int * int) array qui passe de la représentation de de la question I. 1 (tableau ; à la représentation sous forme d'un tableau de paires. Cette fonction devra avoir une complexité temporelle en .

Partie II. Arbres binaires

Soit l'ensemble des arbres binaires dont les feuilles sont en bijection avec un ensemble fini . Autrement dit, un arbre de a exactement feuilles; chacune de ses feuilles est étiquetée par un élément de ; toutes les feuilles sont étiquetées par des éléments différents de . Ces arbres peuvent être construits comme suit:
  • Une feuille étiquetée par est notée . C'est un arbre de .
  • Si et sont des arbres appartenant respectivement à et , alors l'arbre dont le sous-arbre gauche est et le sous-arbre droit est , noté , est un arbre de à condition que .
    Remarque : un tel arbre binaire possède exactement 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 .
Question II.1. Montrez que l'ensemble contient 120 arbres.
Le type OCaml utilisé pour représenter les arbres est le suivant :
type tree of int of tree tree
Étant donnés un arbre de et un élément de , on note la profondeur de la feuille étiquetée par , c'est-à-dire le nombre d'arêtes entre la racine de et cette feuille. Par exemple, avec l'arbre de la figure 1 , on a .
Comme précédemment, soit une fonction de dans . Pour tout arbre avec , on note la somme pondérée suivante :
Question II.2. Supposons . Définissez une fonction array int qui reçoit deux arguments, un arbre et un tableau représentant , et qui renvoie la valeur de . On cherchera à écrire une fonction efficace. Donnez et justifiez sa complexité temporelle.
Étant donné un arbre de , on représente une lettre par la séquence des bits obtenus en parcourant de la racine vers la feuille . Par exemple, dans l'arbre de de la figure 1, D est représenté par 0 tandis que 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 et un arbre et qui renvoie la liste de 0 et 1 représentant dans . 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 bits valant 1 , suivis d'un bit à 0 , suivis de bits arbitraires, ce que l'on notera . Les dix premières séquences par ordre lexicographique sont donc , 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 .
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 pour lesquelles n'excède pas une certaine borne , afin d'obtenir un arbre de profondeur bornée .
Question II.4. Définissez une fonction OCaml integers : int -> tree qui prend un entier en argument et renvoie l'arbre dont les branches sont les séquences de la forme avec , ainsi que la séquence . Les feuilles seront étiquetées de gauche à droite par les entiers , etc.

Partie III. Codes préfixes

Étant donnés un alphabet et un arbre de , un mot de peut être représenté par la concaténation des séquences de bits représentant chacune de ses lettres dans , de la gauche vers la droite. Supposons que l'arbre est l'exemple de la figure 1. Le mot « ADBDCD » est alors représenté par la séquence de bits . 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 un arbre de . Étant donnée une séquence de bits, montrez qu'il existe au plus un mot de qui est représenté par cette séquence.
Question III.2. Supposons . 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 et qui renvoie la liste des éléments de représentée par cette liste de bits. On sera attentif au cas où la liste en argument ne représente aucun mot de . Donnez et justifiez la complexité temporelle de cette fonction.
Cette fonction est dite de décompression. Supposons que est et que la fonction donne le nombre d'occurrences de chaque lettre dans le mot « ADBDCD », par exemple . Dans ce cas, 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, est la longueur de n'importe quelle séquence représentant un mot de compressé avec l'arbre . Il s'avère qu'il n'existe aucun arbre tel que est donc optimal.
Étant donnée une fonction , l'objectif de la partie suivante sera de construire un des arbres de offrant la meilleure compression des mots de , c'est-à-dire un arbre qui minimise .

Partie IV. Arbres optimaux

Soit une fonction dont le domaine inclut . Un arbre de est dit optimal pour ( ) s'il minimise parmi tous les arbres de . Autrement dit, un arbre optimal vérifie . De tels arbres optimaux existent et, dès lors que , ils ne sont pas uniques.
Question IV.1. Soit un arbre optimal pour ( ). Soit l'ensemble des lettres qui étiquettent les feuilles du sous-arbre . Montrez que est un arbre de optimal pour .
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 entre les feuilles du sous-arbre gauche et celles du sous-arbre droit.
Question IV.2. Supposons qu'il existe une lettre telle que . Montrez que, pour tout arbre de optimal pour ( ), la feuille est à profondeur 1 , c'est-à-dire directement attachée à la racine.
Question IV.3. Soient et deux éléments différents de tels que, pour tout , on a et . Soit avec un tout nouvel élément. On définit de telle sorte que et .
  1. Montrez qu'il existe un arbre de optimal pour ( ) ayant un noud .
  2. Soit un arbre de optimal pour ( ). Montrez que l'arbre obtenu en remplaçant dans la feuille par est optimal pour ( ).
On définit la fonction en étendant la fonction aux arbres de la façon suivante. Pour une feuille, vaut . Pour un nœud interne, vaut récursivement . Remarque : en général, .
La question précédente montre qu'il est possible de construire un arbre optimal pour ( ) à l'aide de l'algorithme suivant. On initialise un ensemble d'arbres avec toutes les feuilles avec . À chaque étape, on retire de deux arbres et qui minimisent ; puis on ajoute à l'arbre . On répète cette procédure jusqu'à ce qu'il ne reste qu'un seul arbre dans . Il s'agit alors d'un arbre optimal pour ( ).
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 ; elle contient toutes les paires ( ) pour ; ces paires sont triées par valeur croissante de .
  3. Donnez et justifiez la complexité temporelle de la fonction optimal.
Les deux questions suivantes montrent que, quand la liste initiale des ( ) est triée par valeur croissante de , de simples listes et/ou tableaux suffisent pour écrire une fonction optimal dont la complexité temporelle est en .
Question IV.5. Montrez que, lors de l'exécution de l'algorithme décrit ci-dessus, les arbres sont ajoutés à l'ensemble par valeur croissante de .
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 de la séquence de bits représentant un mot de . 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 . Pour , il s'agira de l'ordre usuel sur . Soit un arbre de . On définit la relation entre éléments de de la façon suivante : pour toute paire ,
L'arbre est dit canonique si, en parcourant les feuilles de la gauche vers la droite, leurs étiquettes respectent la relation . 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 est plus profonde que celle étiquetée par 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 le nombre de lettres telles que . Le deuxième tableau contient les éléments de obtenus en parcourant les feuilles de l'arbre de gauche à droite. Ainsi, l'arbre de de la figure 3 est représenté par les deux tableaux et .
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 est alphabétique si, en parcourant ses feuilles de gauche à droite, les étiquettes apparaissent dans l'ordre alphabétique. On note l'ensemble de ces arbres. On dit d'un arbre qu'il est alphabétique-optimal pour ( ) s'il minimise parmi tous les arbres de . Remarque : un arbre alphabétique-optimal pour ( ) n'est pas nécessairement optimal pour ( ).
Soit et . On se donne une fonction . Étant donnés deux entiers et tels que , on note la valeur de pour n'importe quel arbre de alphabétique-optimal pour ( ). En particulier, si est un arbre de alphabétique-optimal pour ( ), il vérifie .
Question VI.1. Exprimez la valeur de en fonction des valeurs de avec . Déduisez en une fonction OCaml alpha_optimal : int array -> tree qui calcule un arbre de alphabétique-optimal pour ( ). La fonction est donnée par le tableau de taille passé en argument. La complexité temporelle de la fonction devra être en .
Un arbre alphabétique de peut être représenté par la séquence de 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 avec la taille du tableau.

Partie VII. Codes arithmétiques

Soient un alphabet et une fonction . Comme précédemment, est le sousensemble des mots de qui contiennent exactement occurrences de pour chaque .
Question VII.1. Supposons que est et que satisfait , .
  1. Combien de bits faut-il pour représenter un mot de en utilisant un arbre optimal pour ?
  2. Combien y a-t-il de mots dans ? 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 (et donc n'importe quel mot de ). Remarque : .
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ù . Soit . La fonction est définie de la façon suivante pour :
où désigne la partie entière de .
La fonction peut être étendue en une fonction qui travaille sur les mots de la façon suivante :
Ainsi, après avoir choisi arbitrairement, un mot peut être compressé en un entier . Il est alors possible de retrouver le mot original à partir de en calculant progressivement , etc, jusqu'à .
Considérons par exemple le mot . Si l'on part de , sa version compressée sera l'entier 151 :
où signifie .
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 et deux entiers et , et renvoie un entier et un tableau tels que .
Le nombre de bits de l'entier est proche de l'optimum théorique . mais un problème se pose en pratique. Sauf pour de tout petits mots sur de tout petits alphabets, le calcul de va nécessiter de manipuler des entiers très grands. Pour éviter ce problème, une solution consiste, avant chaque appel à , à se débarrasser d'un certain nombre de bits de poids faible. Plus précisément, on construit les suites et suivantes:
Comme précédemment, la valeur de est fixée arbitrairement. Le mot peut alors être représenté par d'une part et d'autre part la concaténation des séquences de bits suivantes, les bits de poids forts apparaissant en premier :
Pour chaque en ordre décroissant, le décompresseur déduit de les valeurs de et (par exemple avec decomp2, question VII.2, avec ), puis il lit bits dans le mot compressé et les concatène à pour obtenir , et ainsi de suite jusqu'à avoir décompressé tout le mot.
Dans la suite, on supposera que est une puissance de deux : . On supposera par ailleurs que le processeur n'est efficace que pour des entiers ne dépassant pas pour un certain bien plus grand que . En particulier, ne doit jamais atteindre cette borne lors de la compression.
Pour que le taux de compression se rapproche de l'optimum théorique, il faut que chaque soit le plus petit possible (idéalement 0 ) et donc que chaque soit le plus grand possible. Par ailleurs, les différents ne font pas partie du mot compressé. Autrement dit, en ne connaissant que , le décompresseur doit pouvoir deviner le nombre de bits qui doivent être lus dans le mot compressé pour reconstruire . Une solution correcte mais mauvaise serait, par exemple, de fixer tous les à la constante ; le décompresseur pourrait alors deviner trivialement les mais le mot résultant ne serait absolument pas compressé.
Question VII.3. Proposez une façon pour le compresseur de choisir en fonction de et . Expliquez comment le décompresseur choisit en fonction de et prouvez que ce choix correspond bien à celui du compresseur. Si cela a une importance, expliquez comment le compresseur doit choisir .
Remarque : la contrainte imposant que 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 soit proche de la proportion de la lettre dans le mot à compresser.
Fin du sujet.
X ENS Option Informatique MP MPI 2023 - Version Web LaTeX | WikiPrépa | WikiPrépa