L'algorithme de Huffman

Il s'agit d'écrire en langage C un programme qui effectue l'algorithme de huffman.
Le programme prendra en argument sur la ligne de commande le nom d'un fichier d'entrée contenant un texte et le nom d'un fichier dans lequel les résultats seront sauvegardés.
Le programme calculera d'abord les nombres d'occurrences de chacune des lettres du texte du fichier d'entrée. Il calculera alors le codage des caractères permettant d'avoir un texte codé, avec un codage préfixe, le plus court possible ; cela sera fait en utilisant l'algorithme de Huffman. On ne calculera un mot de code que pour les lettres figurant au moins une fois dans le texte.
Les mots de code attribués à chaque lettre du texte seront d'une part affichés à l'écran et d'autre part sauvegardés, dans l'ordre du code ASCII, dans le fichier de sauvegarde.
Le programme indiquera aussi la longueur du texte non codé et la longueur du texte codé (néanmoins, on ne construira pas le texte codé). Pour le texte non codé, il faut compter un octet par caractè!re. Le texte codé est une suite de 0 et de 1 ; il faut compter un bit pour chaque 0 ou 1, et donc un octet pour huit 0 ou 1 (on divisera donc par huit la somme des longueurs des mots de code concaténés dans le texte codé).

Un texte

Un corrigé

ou bien Un corrigé sans trier

Irene Charon

Last modified: Tue Nov 18 19:21:57 CET 2008