Algorithme de Huffman

Il s'agit de mettre en oeuvre l'algorithme de Huffman étudié en cours de SDA.
L'algorithme doit calculer le code optimal de Huffman correspondant à un texte donné. L'entrée du programme sera le nom du fichier contenant le texte et la sortie du programme sera la liste sur la sortie standard des caractères du texte avec le code correspondant.
Si le fichier contient le texte :
vingt fois sur le métier remettez votre ouvrage (Boileau),
la sortie pourrait être :

  (8 fois) : 011
( (1 fois) : 00100
) (1 fois) : 01010
B (1 fois) : 00101
a (2 fois) : 11011
e (8 fois) : 100
f (1 fois) : 111001
g (2 fois) : 01011
i (4 fois) : 1010
l (2 fois) : 11001
m (2 fois) : 11010
n (1 fois) : 111000
o (4 fois) : 1011
r (5 fois) : 000
s (2 fois) : 11000
t (5 fois) : 1111
u (3 fois) : 0100
v (3 fois) : 0011
z (1 fois) : 111011
é (1 fois) : 111010

Vous pourrez utiliser la classe ScanPlus d'un paquetage outil qui vous est fournie. Le constructeur de cette classe prend en paramètre un nom de fichier. La méthode d'instance nextChar() permet de parcourir le texte contenu dans le fichier caractère par caractère. À son premier appel, elle renvoie le premier caractère du fichier (de type char), au deuxième appel le deuxième caractère et ainsi de suite ; la méthode retourne 0 (qui est compatible avec le type char) lorsque que la fin du fichier est atteinte. Il vous suffit d'intégrer le fichier source de cette classe dans votre travail.

Vous pouvez choisir de travailler sans suivre le plan ci-dessous.

Si vous voulez suivre notre plan, vous développerez deux classes.

La classe NoeudHuffman représente un noeud de l'arbre de Huffman et un caractère avec son code qui sera calculé par l'algorithme.
Cette classe contient cinq attributs privés et les accesseurs nécessaires correspondants :
- caractere de type char pour le caractère concerné ;
- nbOcc de type int pour le nombre d'occurences du caractère dans un texte ;
- filsG et filsD de type NoeudHuffman qui serviront à construire l'arbre de Huffman ;
- code, de type String, qui contiendra la suite des 0 et des 1 du code du caractère ;
La classe implémentera l'interface Comparable<NoeudHuffman> (en mettant dans son en-tête implements Comparable<NoeudHuffman>) et définira donc la méthode d'en-tête :
    public int compareTo(NoeudHuffman autre)
Il pourra être pratique de pouvoir comparer des NoeudHuffman soit selon les caractères contenus soit selon les nombres d'occurrences ; en effet, vous devrez trier un ArrayList de NoeudHuffman selon les caractères contenus, mais vous devrez aussi déterminer dans un ArrayList de NoeudHuffman celui qui a le plus petit nombre d'occurrences. Pour cela, vous définirez deux constantes de classe par :
    public static int CARACTERE = 1, NB_OCC = 2; et un attribut de classe par :
    public static int optionTri; Vous pourrez alors définir la valeur de retour de la méthode compareTo en utilisant la valeur de la variable optionTri (selon qu'elle vaut CARACTERE ou NB_OCC).
Vous pouvez éventuellement définir une méthode qui incrémente de 1 l'attribut nbOcc.
La classe AlgoHuffman modélise l'algorithme de Huffman.
Cette classe contient un attribut nommé par exemple listeCaracteres qui est un ArrayList<NoeudHuffman>. Cet ArrayList contiendra exactement un NoeudHuffman par caractère contenu dans le texte, que ce caractère figure une ou plusieurs fois dans le texte.
Le constructeur de la classe recevra en paramètre le nom du fichier à partir duquel il faut calculer le code de Huffman. Ce constructeur appellera différentes méthodes pour calculer le code de Huffman puis écrire à l'écran le code optimal. La liste des différentes méthodes peut être la suivante.
- Une méthode construireListe(String nomFichier) utilise une instance de la classe ScanPlus pour lire un à un les caractères du texte en construisant la liste listeCaracteres.
- Une méthode ajouter(char c) ajoute une instance de NoeudHuffman correspondant au caractère c à la liste listeCaracteres ou bien incrémente de un le nombre d'occurrences si ce caractère avait déjà été rencontré.
- Une méthode huffman() construit l'arbre de Huffann ; on conseille de cloner la liste listeCaracteres pour appliquer l'algorithme à la liste clonée ; ce clonage peut être réalisé par l'instruction ;
  ArrayList<NoeudHuffman> copieListe = (ArrayList<NoeudHuffman>)listeCaracteres.clone();
  la liste clonée contient alors une copie de toutes les références contenues dans listeCaracteres. Les NoeudHuffman référencés sont les mêmes ; ils ne sont pas dupliqués. Modifier un NoeudHuffman dont la référence figure dans copieListe modifie aussi le noeud de même référence contenu par listeCaracteres.
  La méthode huffman() pourrait renvoyer la racine de l'arbre de Huffann, de type NoeudHuffman.
- Une méthode determinerCodes(NoeudHuffman racine, StringBuffer chaine), récursive, remplit les attributs code des éléments de listeCaracteres en utilisant l'arbre de racine racine calculé avec la méthode huffman ; le paramètre chaine de cette méthode peut servir à construire ces codes au fur et à mesure de la descente dans l'arbre ; des méthodes avec d'autres signatures peuvent avoir le même usage, cette signature dépend de l'algorithme retenu pour calculer les codes à partir de l'arbre de Huffman.
- Une méthode ecrire écrit à l'écran la liste des caractères figurant dans le texte avec leurs nombres d'occurrences et leurs codes, de la manière donnée plus haut en exemple ; cette liste sera classée par ordre alphabétique ; la méthode ecrire utilisera la méthode toString de la classe NoeudHufmann.
Corrigé :
© Irène Charon, Télécom ParisTech - Paris 2011

Algorithme de Huffman

Corrigé :