Algorisme de Huffman: diferència entre les revisions

== Descripció ==

L'algorisme consisteix en la creació d'un [[arbre binari]] que té tots els símbols repartits un 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 de Huffman associat.

# 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ó.

# Es prenen 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.

# Davallar per la branca etiquetada amb aquest símbol.

# 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.