Algorisme d'Huffman

L'algorisme d'Huffman és un algorisme per la construcció de codis d'Huffman, desenvolupat per David A. Huffman el 1952 i descrit a A Method for the Construction of Minimum-Redundancy Codes.

Aquest algorisme pren un alfabet de n símbols, juntament amb les seves freqüències d'aparició associades, i produeix un codi d'Huffman per aquest alfabet i aquestes freqüències.

Descripció

L'algorisme consisteix en la creació d'un arbre binari que té tots els símbols a cada fulla, i està construït de forma que seguint-lo des de l'arrel a cada una de les fulles s'obtingui el codi d'Huffman associat.

1. Es creen diferents arbres, un per cada símbol de l'alfabet, consistint cada arbre en un node sense fills. Cada arbre s'etiqueta amb el seu símbol associat i la seva freqüència d'aparició.
2. S'agafen els dos arbres de menor freqüència i s'uneixen creant un nou arbre. L'etiqueta de l'arrel serà la suma de les freqüències de les arrels dels dos arbres que s'uneixen, i aquests dos arbres seran fills del nou arbre. També s'etiqueten les dues branques del nou arbre: amb un 0 la de l'esquerra, i amb un 1 la de la dreta.
3. Es repeteix el pas 2 fins que només queda un arbre.

Amb aquest arbre es pot conèixer el codi associat a un símbol i també es pot obtenir el símbol associat a un determinat codi.

Per obtenir el codi associat a un símbol s'ha de procedir de la següent manera:

1. Començar amb un codi buit.
2. Iniciar el recorregut de l'arbre a la fulla associada al símbol.
3. Començar un recorregut de l'arbre cap amunt.
4. Cada vegada que es pugi un nivell, afegir al codi l'etiqueta de la branca que s'ha recorregut.
5. Després d'arribar a l'arrel, invertir el codi.
6. El resultat és el codi d'Huffman desitjat.

Per obtenir un símbol a partir d'un codi s'ha de fer així:

1. Començar el recorregut de l'arbre a l'arrel d'aquest.
2. Extreure el primer símbol del codi a descodificar.
3. Descendir per la branca etiquetada amb aquest símbol.
4. Tornar al pas 2 fins que s'arribi a una fulla, que serà el símbol associat al codi.

A la pràctica, gairebé sempre s'utilitza l'arbre per obtenir tots els codis a la vegada; després es guarden en taules i es deixa l'arbre.