Fork me on GitHub

Construction du code de Huffman

Dans ce TD nous allons nous occuper de la partie du Codage de Huffman qui consiste à construire l’arbre de décodage. Le TD est divisé en deux parties : dans un premier temps nous allons nous occuper de la construction de l’arbre avec des fréquences prédéfinies dans le code source ; dans un deuxième temps, nous allons récupérer ces fréquences d’un fichier de texte.

Construction de l’arbre de Huffman

Créez un fichier Huffman.java contenant le code suivant.

import java.util.ArrayList;
import java.util.Collections;

/*
  Cette classe implante le noeud d'un arbre binaire contenant
  contenant les donnees necessaires a l'algorithme de Huffman (le
  symbole encode et sa frequence).
 */
class Node implements Comparable<Node> {
    char symbol;
    double freq;
    Node left, right;

    /* 
       Methode implantant l'interface Comparable. Renvoie -1 si la
       frequence de ce noeud est inferieur a celle de other, 1 sinon.
    */
    public int compareTo(Node other) {
        return 0;
    }
}

/*
  Cette classe implante l'algorithme de Huffman
*/
public class Huffman {
    // Quelques alphabets predefinis avec frequences
    /*
    static char[] symbols = {
        'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i',
        'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r',
        's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
    static double[] freqs = {
        0.03, 0.12, 0.01, 0.06, 0.04, 0.04, 0.04, 0.01,        0.04,
        0.06, 0.04, 0.03, 0.02, 0.02, 0.01, 0.10, 0.01, 0.06,
        0.01, 0.03, 0.01, 0.03, 0.02, 0.03, 0.06, 0.07 };
    */

    static char[] symbols = { 'a', 'b', 'c', 'd' };
    static double[] freqs = { 0.25, 0.45, 0.20, 0.10 };

    /*
      Cette methode construit un arbre binaire de Node correspondant a
      l'arbe de Huffman. En entree il attend un tableau de symboles et
      le tableau des frequences correspondantes. Elle renvoie la
      racine de l'arbre.
     */
    public static Node createTree(char[] symbols, double[] freqs) {
        return null;
    }

    /*
      Cette fonction construit la table d'encodage a partir de l'arbre
      de Huffman. La valeur de retour est un tableau de chaines,
      contenant l'encodage (en binaire) de chaque symbole de a jusqu'a
      z.
     */
    public static String[] createCode(Node root) {
        return null;
    }

    public static void main(String[] args) {
        String[] codes = createCode(createTree(symbols, freqs));
        for (int i = 0 ; i < codes.length ; i++) {
            System.out.println((char)(i + 'a') + ": " + codes[i]);
        }
    }
}

Un arbre binaire est un arbre dans lequel chaque nœud a soit deux soit aucun fils. La classe Node représente un nœud d’un arbre binaire : les champs left et right permettent de pointer vers les nœuds fils, et ils sont null lorsque le nœud est une feuille. En plus de ces informations, notre classe Node contient deux champs nécessaires à l’algorithme de Huffman : un champ symbol qui sert à stocker un symbole de l’alphabet à encoder, et un champ freq qui contient sa fréquence. Enfin, la classe Node implante l’interface Comparable, ce qui permet d’ordonner des listes de nœuds

  1. Complétez la classe Node en remplissant la méthode compareTo. La comparaison doit se faire par rapport au champ freq. Ajoutez aussi autant de constructeurs que vous le retiendrez nécessaire.

Maintenant on peut passer à l’algorithme de Huffman à proprement parler. Le main a déjà été complété avec du code qui permet de tester l’algorithme lorsque toutes les méthodes auront été implantées. N’hésitez pas à le modifier pour tester les méthodes en cours d’écriture.

La méthode createTree sert à créer l’arbre de Huffman. Ses entrées sont deux tableaux, qu’on suppose de la même longueur, contenant respectivement les symboles de l’alphabet et leurs fréquences. On rappelle brièvement le principe de l’algorithme de Huffman, et on en suggère une implantation possible.

  1. Complétez la méthode createTree avec l’algorithme décrit ci-dessus. Elle doit renvoyer la racine de l’arbre.

L’arbre de Huffman permet de décoder de façon très pratique, il n’est par contre pas très utile lorsqu’il s’agit de coder.

  1. Complétez la méthode createCode, qui prend en entrée la racine de l’arbre de Huffman, et qui renvoie un tableau de String, contenant dans l’ordre les codages (binaires) des symboles de ‘a’ à ‘z’. Pour cette méthode, un algorithme récursif est le plus adapté à parcourir l’arbre. Par exemple, vous pouvez ajouter une méthode

    private static void traversal(Node node, String code, String[] codes)
    

    qui parcourt tout le sous-arbre en dessous de node, en remplissant le tableau de sortie codes.

Lorsque vous aurez implanté correctement les méthodes createTree et createCode, la sortie du main doit être égale à l’un des deux codes suivants (selon si vous avez assigné 0 à gauche et 1 à droite, ou vice-versa):

a: 10
b: 0
c: 111
d: 110
e: null
...

ou

a: 01
b: 1
c: 000
d: 001
e: null
...

Pour être sûr que votre code est bon, testez avec d’autres jeux de symboles plus grands que ‘a’, ‘b’, ‘c’, ‘d’. Pour qu’un code soit valide il ne doit pas y avoir de dupliqués (deux symboles ne peuvent pas être encodés par les mêmes symboles) et, plus généralement, aucun code ne doit être le préfixe d’un autre.

Voici la solution de cette partie.

Lecture des fréquences d’un fichier texte

On voudrait maintenant que les fréquences des lettres nous soient données dans un ficher de texte, plutôt que codées en dur dans le code source. Pour cela nous allons utiliser les classes Java qui permettent la lecture des fichiers en mode texte.

La classe java.io.FileReader permet de lire un fichier caractère par caractère (plutôt qu’octet par octet), en tenant compte de l’encodage du fichier. Combinée avec java.io.BufferedReader, elle permet de lire directement un fichier ligne par ligne. Voici un exemple de code qui lit un fichier ligne par ligne et l’affiche sur la console.

BufferedReader in = new BufferedReader(new FileReader("fichier.txt"));

String line;
while ( (line = in.readLine()) != null)
    System.out.println(line);

La méthode readline() renvoie une ligne entière prise du flux, sous forme de String. Si le fichier ne contient plus de lignes, elle renvoie null.

Nous voulons encoder les fréquences dans un fichier obéissant au format suivant.

a: 0.0133
b: 0.123
c: 0.001
...

Un symbole par ligne, suivi de ‘: ’ et de sa fréquence.

  1. Modifiez Huffman.java en sorte que les symboles et les fréquences soient pris d’un fichier passé par la ligne de commande.

Pour découper une chaîne de caractères vous pouvez utiliser les méthodes de String :

Pour convertir une chaîne de caractères en double, vous pouvez utiliser Double.parseDouble().


  1. Modifiez votre code pour supporter d’autres symboles que ceux de ‘a’ à ‘z’ (potentiellement, tous les caractères Unicode !).