Compresser et décompresser un texte par codes de longueur variable

Énoncé

Le programme lit une ligne de commande E ou D, puis traite l'entrée. Pour E (encodage), il lit un texte sur une seule ligne, calcule les fréquences de chaque caractère, construit l'arbre de Huffman (en cas d'égalité de fréquences, le caractère d'ordre ASCII inférieur est traité en premier), affiche la table de codes (un caractère et son code binaire par ligne, triés par ordre ASCII), puis affiche le texte encodé sous forme de suite de bits 0/1. Pour D (décodage), il lit d'abord le nombre de codes, puis chaque paire caractère code, puis la suite de bits, et affiche le texte original.

Contraintes

• Le texte pour E contient entre 1 et 500 caractères ASCII imprimables, au moins 2 caractères distincts, et toutes les fréquences des caractères sont distinctes (pas d'égalité — aucune ambiguïté dans la construction de l'arbre).
• La file de priorité est un min-heap sur les fréquences ; le nœud de plus faible fréquence est toujours extrait en premier.
• L'arbre de Huffman est construit en plaçant le nœud extrait en premier comme enfant gauche.
• La suite de bits ne contient que 0 et 1.
• Solution réalisable dans tout langage généraliste avec sa seule bibliothèque standard.

Exemple

CopierEntrée :
E
aaaabbc

Sortie :
a 1
b 01
c 00
1111010100

Fréquences : a=4, b=2, c=1. File : c(1), b(2), a(4). Étape 1 : fusion c(1)+b(2)=nœud(3) ; c→gauche=00, b→droite=01. Étape 2 : fusion nœud(3)+a(4)=racine ; nœud→gauche, a→droite=1. Encodage de aaaabbc : 1·1·1·1·01·01·00 = 1111010100.

CopierEntrée :
D
3
a 1
b 01
c 00
1111010100

Sortie :
aaaabbc