Codage de Huffman

On souhaite implémenter l'algorithme de Huffmann pour la compression de données.
Les opérations sont, dans l'ordre :

• Ouvrir un fichier input.txt.
• Lire les caractères un par un. Stocker le nombre d'occurences d'un caractère dans une table de hachage.
• Pour chaque caractère, créer une arbre réduit à une feuille, ayant un poids égal au nombre d'occurences. Trier toutes ces feuilles par poids croissant dans une liste chaînée (par exemple avec un tri par insertion).
• Engendrer l'arbre de Huffman proprement dit, en prenant les deux arbres de poids le plus faible dans la liste, et en les fusionnant en un nouvel arbre dont le poids est la somme des deux poids. On réinsère ensuite ce nouvel arbre dans la liste et on recommence. Quand la liste est réduite à un seul élément, l'algorithme est fini.
• Enregistrer l'arbre par parcours préfixe dans un fichier output.txt.
• Relire le fichier output.txt et reconstruire l'arbre associé. Afficher le parcours préfixe sur la sortie standard.
• S'il reste du temps, obtenir le taux de compression du fichier. Comparer avec un outil usuel, comme gzip ou bzip2. Trouver un codage pour chaque caractère, que l'on pourra enregistrer dans la table de hachage déjà construite, en modifiant la structure initiale.

Une table de hachage est un tableau de listes chaînées. La taille du tableau est fixée. On a besoin d'une fonction de hachage pour savoir dans quelle case mettre un caractère (l'opération modulo est suffisante dans ce cas). Une fois qu'on est dans la bonne case, on parcourt la chaîne pour trouver le caractère.