Contrôle Final 1 – Année 2021/2022
- Durée du contrôle : 2h
- Tous les documents papier sont autorisés
Dans l'exercice 1, vous allez mettre en œuvre une nouvelle structure de données appelée la file de priorité (priority queue en anglais). Dans l'exercice 2, vous allez utiliser cette structure de données pour mettre en œuvre le codage de Huffman. Ce codage est utilisé pour compresser des données.
Réaliser l'exercice 1 n'est pas nécessaire pour réaliser l'exercice 2. En revanche, il est nécessaire de lire l'introduction de l'exercice 1 afin de comprendre ce qu'est une file de priorité et donc de pouvoir l'utiliser correctement dans l'exercice 2. La classe que vous allez mettre en œuvre à l'exercice 1.b sera aussi réutilisée dans l'exercice 2. Lire l'énoncé de cette question est donc aussi recommandé avant de passer à l'exercice 2.
File de priorité (8,5 points)
Le but de cet exercice est de mettre en œuvre une file de prioriété (class PriorityQueue). Une file de prioriété est une structure de données permettant de stocker des éléments. Ces éléments peuvent être comparés, ce qui définit un ordre total. En supposant que E est le type d'un élément stocké dans la file de priorité, PriorityQueue fournie trois méthodes :
- E poll() : retire l'élément le plus petit et le renvoie si la file n'est pas vide, et renvoie null sinon,
- void add(E element) : ajoute un élément à la file,
- int size() : renvoie le nombre d'élément dans la file.
Pour stocker des éléments, nous nous servirons d'un tableau dynamique (classe java.util.ArrayList fournie par la bibliothèque Java). Lors d'un ajout (méthode add de PriorityQueue), l'élément sera ajouté à la fin du tableau dynamique sans trier la liste. Lors d'un retrait (méthode poll de PriorityQueue), l'élément le plus petit sera retiré du tableau dynamique. Cette mise en œuvre n'est pas très efficace, mais sera suffisante pour les besoins du contrôle.
Afin d'illustrer, considérons une file contenant 55, 12 et 17. Avec cette file, un appel à poll retourne 12 et la file contient donc 55 et 17. Ensuite, après un appel à add(3), la file contient 55, 17 et 3.
Dans la suite, vous aurez besoin de vous servir des méthodes suivantes fournies par la classe ArrayList<E> :
- Un constructeur vide permettant d'initialiser le tableau dynamique,
- Une méthode int size() renvoyant le nombre d'éléments dans le tableau dynamique,
- Une méthode void add(E e) ajoutant l'élément e à la fin du tableau dynamique,
- Une méthode E get(int i) renvoyant l'élément à la position i du tableau (i est supposé plus petit que size()),
- Une méthode void set(int i, E e) permettant de remplacer l'élément à la position i par e (i est supposé plus petit que size()),
- Une méthode void remove(int i) supprimant l'élément la position i (i est supposé plus petit que size()).
L'interface Comparable (0,5 points)
De façon à comparer deux éléments de type E, on commence par définir une interface générique nommée Comparable. Cette interface doit fournir une unique méthode compareTo prenant un argument nommé e de type E, et renvoyant un entier. Cet entier indique le résultat de la comparaison de this et e et est interprété de la façon suivante :
- inférieur à 0 si this est strictement plus petit que e,
- 0 si this est égal à e,
- supérieur à 0 sinon.
Donnez le code de l'interface Comparable. Pensez que le type E n'est pas connu à la conception.
La classe Weight (2 point)
Dans l'exercice 2, nous aurons besoin de comparer des éléments suivant un poids (weight en anglais). Pour cela, donnez le code de la classe Weight. Cette classe doit :
- mettre en œuvre Comparable de façon à pouvoir comparer deux éléments de type Weight,
- posséder un champ weight de type entier représentant le poids et un constructeur prenant en argument un poids initial,
- posséder une méthode void incWeight() permettant d'incrémenter de 1 weight,
- mettre en œuvre compareTo et renvoyer un nombre négatif si this a un poids plus petit que l'argument, 0 si ils sont égaux, et un nombre positif sinon.
Définition de la file de prioriété (1 point)
Une file de priorité (class PriorityQueue) doit stocker des éléments de type E. Ces éléments sont inconnus à la conception, mais ils doivent mettre en œuvre l'interface Comparable de façon à pouvoir les comparer. Donnez la définition de la class PriorityQueue en laissant le corps de la classe vide.
Le constructeur de la file de priorité (0,5 points)
Pour stocker des éléments, PriorityQueue doit posséder un champ nommé list de type java.util.ArrayList (tableau dynamique). À cette question, on vous demande d'indiquer :
- La directive import que vous devez ajouter au début de votre fichier,
- La définition du champ list de la classe PriorityQueue,
- Le code du constructeur permettant d'initialiser ce champ.
Dans la suite de l'exercice, on considère que chaque méthode que vous écrivez se trouve dans la classe PriorityQueue et on ne vous demande donc plus de rappeler la définition de cette classe.
Ajout et taille (0,5 points)
Écrivez le code des méthodes size et add de PriorityQueue. On vous rappelle que add ajoute simplement l'élément à la fin du tableau dynamique list.
Retrait (4 points)
Donnez le code de la méthode poll de PriorityQueue. Cette méthode doit d'abord identifier la position min à laquelle se trouve l'élément le plus petit dans list, stocker cet élément dans une variable res, déplacer le dernier élément de list à la position min puis supprimer le dernier élément avant de renvoyer res. Pensez aussi que poll doit renvoyer null lorsque la liste est vide.
Le codage de Huffman (11,5 points)
Le codage du Huffman est un codage permettant de compresser des données sans perte d'information. On considère que les données sont fournies sous la forme d'un tableau d'octets (type byte Java). La fonction de codage commence par calculer, pour chaque valeur possible d'un octet, la fréquence d'apparition de cette valeur dans le tableau d'entrée. Par exemple, si le tableau d'entrée contient "A_DEAD_DAD_CEDED_A_BAD_BABE_A_BEADED_ABACA_BED", les fréquences sont : A: 11, B: 6, C: 2, D: 10, E: 7, _: 10.
Ensuite, au lieu de coder les valeurs avec un nombre fixe de bits (8 bits puisqu'on considère des byte), la fonction va utiliser un codage à longueur variable : une valeur fréquente va être codée avec un faible nombre de bits, alors qu'une valeur rare va être codée avec un plus de bits. Dans notre cas, par exemple, comme A est fréquent, on pourrait imaginer le coder sur 2 bits, alors que comme C est rare, on pourrait imaginer le coder sur 4 bits.
Pour calculer le codage on va construire un arbre binaire dans lequel les feuilles sont les valeurs du tableau d'octets initial. Dans cet arbre, le chemin à partir de la racine est court si un élément est fréquent, alors qu'il est long si l'élément est rare.
Pour cela, il faut considérer que chaque nœud de l'arbre (qu'il soit une feuille ou non) a un poids. Initialement, on ne considère que les feuilles (c'est-à-dire les valeurs du tableau d'octets initial) et on considère que leur poids est égal à leur fréquence. Ensuite, on trie les nœuds par ordre croissant de poids, ce qui nécessite l'utilisation d'une file de priorité (voir exercice 1). Après, tant que la file contient strictement plus d'un élément :
- on retire les deux éléments avec le plus faible poids (par exemple C et B à la première étape sur notre exemple),
- on construit un nouveau nœud interne ayant pour poids la somme des poids des éléments retirés, et pour enfants les nœuds retirés,
- et on ajoute ce nouveau nœud à la file de priorité.
Sur notre exemple, on obtient donc le déroulement suivant :
Enfin, on peut construire les codes associés aux éléments en parcourant les chemins allant de la racine jusqu'à chaque feuille et en considérant que si on passe par un fils gauche, on note 0 et si on passe par un fils droit, on note 1. Par exemple, E est encodé avec 110 puisqu'à partir de la racine, on doit parcourir le fils droit (1), puis le fils droit (1) et enfin le fils gauche (0). Au final, avec l'arbre obtenu, les codes sont donc : D: 00, _: 01, A: 10, E: 110, C: 1110 et B: 1111.
Les nœuds (1.5 points)
Notre algorithme doit manipuler des nœuds (class Node) triés par poids. Pour cette raison Node hérite de Weight (voir question 1.b) et y ajoute trois champ :
- parent : référence le nœud parent, ce champ sera utilisé à la fin de l'exercice pour remonter dans l'arbre à partir des feuilles,
- left et right : référencent respectivement les fils gauche et droit.
La classe Node doit posséder deux constructeurs :
- Un constructeur sans argument utilisé pour construire les feuilles. Ce constructeur initialise le poids à 0 et les champs de Node à null.
- Un constructeur utilisé pour construire les nœuds intermédiaires prenant en argument un fils gauche et un fils droit. Ce constructeur commence par initialiser le poids à la somme des poids des fils gauche et droit. Ensuite, il initialise son champ parent à null, et ses champs left et right de façon adéquate. Enfin, le constructeur modifie de façon adéquate le champ parent des fils gauche et droit afin que l'on puisse remonter dans l'arbre dans la suite de l'exercice.
Donnez le code de la classe Node avec ces deux constructeurs.
L'encodage (2 points, plus difficile)
Pour simplifier l'exercice, on va représenter les formes encodées des nœuds avec des chaînes de caractères. Donnez le code de la méthode String encode() de la classe Node permettant de construire le codage d'un nœud. Cette méthode doit remonter dans l'arbre jusqu'à la racine en construisant une chaîne de caractères représentant le codage du nœud. Par exemple, appeler encode() sur la feuille représentant le caractère E dans notre exemple devrait renvoyer la chaîne de caractères "110".
Calcul des fréquences (2 points)
On suppose qu'on dispose du squelette de code suivant :
Écrivez une méthode void Huffman.computeFrequency() calculant la fréquence de chaque octet du tableau input. Dans cette méthode, vous devez allouer des instances Node au fur et mesure que vous rencontrez de nouvelles valeurs dans le tableau input. Pensez à réutiliser la méthode incWeight que vous avez conçue à la question 1.b.
Construction de l'arbre (4 points)
Écrivez une méthode void Huffman.computeTree() qui construit l'arbre d'encodage. À l'entrée de cette méthode, nodes[i] contient :
- null si la valeur i n'existe pas dans input,
- une référence vers une instance de Node, et dans ce cas, weight indique la fréquence d'apparition de i dans input.
Encodage (2 points)
Écrivez une méthode String Huffman.encode() qui renvoie une représentation compressée de input. Techniquement, cette méthode doit renvoyer la version compressée de input sous la forme d'une chaîne de caractères ne contenant que les caractères '0' et '1'.
