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 (l'ordre d'extraction est totalement défini par la règle de départage ci-dessous), 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 et au moins 2 caractères distincts.
• Chaque nœud porte un rang de création : les feuilles reçoivent les rangs 0, 1, 2… dans l'ordre ASCII croissant de leur caractère, puis chaque nœud interne reçoit le rang suivant au moment où il est créé.
• La file de priorité extrait le nœud de plus faible fréquence ; à fréquence égale, le nœud de plus petit rang sort en premier. Cette règle couvre aussi les nœuds internes, dont la fréquence peut égaler celle d'une feuille restante — des fréquences de départ distinctes ne suffisent pas à rendre l'arbre unique.
• 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