Décompression
L’algorithme de décompression reconstruit l’arbre au fur et à mesure de la lecture du flux compressé (cf. figure 8). On remarque au passage qu’il n’est nul besoin d’attendre la fin du traitement pour obtenir une sortie : la décompression (comme la compression d’ailleurs) se fait sur le flux.
Figure 8 : Décompression
La réorganisation de l’arbre en fonction des probabilités d’apparition des caractères se fait au fur et à mesure. La lecture se fait bit à bit, en navigant dans l’arbre. Cependant, une astuce permet d’aller plus vite : en remarquant que dans l’arbre les fils 0 sont des feuilles et les fils 1 des nœuds - sauf le caractère phi, on peut sans problème lire d’un bloc toute suite de 1 de longueur maximale la hauteur de l’arbre, ce qui revient à lire le chemin jusqu’à la feuille. Si le chemin finit par un 1, nous avons un phi et les 8 bits suivants représentent un caractère, ou dans le cas inverse (le chemin se termine par un 0), on prend la valeur de la feuille rencontrée.