L’algorisme de Huffman s’utilitza per comprimir o codificar dades. Normalment, cada caràcter d’un fitxer de text s’emmagatzema com a vuit bits (dígits, 0 o 1) que s’assignen a aquest caràcter mitjançant una codificació anomenada ASCII. Un fitxer codificat per Huffman descompon l'estructura rígida de 8 bits de manera que els caràcters més utilitzats s'emmagatzemen en pocs bits ('a' podria ser "10" o "1000" en lloc de l'ASCII, que és "01100001"). Els caràcters menys comuns, doncs, sovint ocuparan molt més de 8 bits ('z' podria ser "00100011010"), però com que es produeixen tan rarament, la codificació Huffman, en general, crea un fitxer molt més petit que l'original.
Passos
Part 1 de 2: Codificació
Pas 1. Compteu la freqüència de cada caràcter del fitxer a codificar
Incloeu un personatge fictici per marcar el final del fitxer; això serà important més endavant. De moment, anomeneu-lo EOF (final del fitxer) i marqueu-lo com a amb una freqüència d'1.
Per exemple, si voleu codificar un fitxer de text que digui "ab ab cab", tindríeu 'a' amb freqüència 3, 'b' amb freqüència 3, '' (espai) amb freqüència 2, 'c' amb freqüència 1, i EOF amb freqüència 1
Pas 2. Emmagatzemeu els caràcters com a nodes d'arbre i poseu-los en una cua de prioritat
Construireu un gran arbre binari amb cada caràcter com una fulla, de manera que heu d’emmagatzemar els caràcters en un format que els converteixi en nodes de l’arbre. Col·loqueu aquests nodes en una cua de prioritat amb la freqüència de cada caràcter com a prioritat del seu node.
- Un arbre binari és un format de dades en què cada dada és un node que pot tenir fins a un pare i dos fills. Sovint es dibuixa com un arbre ramificat, d’aquí el seu nom.
- Una cua és una recopilació de dades amb el nom adequat on el primer que cal entrar a la cua també és el primer que surt (com esperar a la cua). En una cua de prioritat, les dades s’emmagatzemen per ordre de prioritat, de manera que el primer que surt és el més urgent, el que té la prioritat més petita i no el primer que es fa a la cua.
- A l'exemple "ab ab cab", la vostra cua de prioritat seria la següent: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Pas 3. Comenceu a construir el vostre arbre
Elimineu (o deixeu la cua) les dues coses més urgents de la cua de prioritat. Creeu un nou node d'arbre per ser el pare d'aquests dos nodes, emmagatzemant el primer node com a fill esquerre i el segon com a fill dret. La prioritat del nou node hauria de ser la suma de les prioritats del seu fill. A continuació, poseu aquest nou node a la cua de prioritat.
La cua de prioritat ara té aquest aspecte: {'': 2, nou node: 2, 'a': 3, 'b': 3}
Pas 4. Acabeu de construir l'arbre:
repetiu el pas anterior fins que només hi hagi un node a la cua. Tingueu en compte que, a més dels nodes que heu creat per als caràcters i les seves freqüències, també anireu fent cua, convertint-vos en arbres i tornant a posar en cola els nodes pares, nodes que ja són ells mateixos arbres.
- Quan hàgiu acabat, l'últim node de la cua serà l'arrel de l'arbre de codificació, amb la resta de nodes que se'n derivaran.
- Els caràcters més freqüentment utilitzats seran les fulles més properes a la part superior de l’arbre, mentre que els caràcters poc utilitzats es situaran a la part inferior de l’arbre, més lluny de l’arrel.
Pas 5. Creeu un mapa de codificació. Passegeu per l’arbre per arribar a cada personatge. Cada vegada que visiteu el fill esquerre d'un node, és un '0'. Cada vegada que visiteu el fill adequat d'un node, és un '1'. Quan arribeu a un personatge, deseu-lo amb la seqüència de 0s i 1s que va trigar a arribar-hi. Aquesta seqüència és el que es codificarà el caràcter al fitxer comprimit. Emmagatzemeu els personatges i les seves seqüències en un mapa.
- Per exemple, comenceu per l'arrel. Visiteu el fill esquerre de l'arrel i visiteu el fill esquerre d'aquest node. Com que el node on es troba ara no té fills, heu arribat a un caràcter. Això és ' '. Com que heu caminat dues vegades a l'esquerra per arribar fins aquí, la codificació de '' és "00".
- Per a aquest arbre, el mapa tindrà aquest aspecte: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Pas 6. Al fitxer de sortida, incloeu el mapa de codificació com a capçalera
Això permetrà descodificar el fitxer.
Pas 7. Codifiqueu el fitxer
Per a cada caràcter del fitxer que cal codificar, escriviu la seqüència binària que heu emmagatzemat al mapa. Un cop hàgiu acabat de codificar el fitxer, assegureu-vos d'afegir l'EOF al final.
- Per al fitxer "ab ab cab", el fitxer codificat serà així: "1011001011000101011011".
- Els fitxers s’emmagatzemen com a bytes (8 bits o 8 dígits binaris). Com que l'algorisme de codificació Huffman no utilitza el format de 8 bits, els fitxers codificats sovint no tenen longituds múltiples de 8. La resta de dígits s'ompliran amb 0. En aquest cas, s’afegirien dos 0 al final del fitxer, que sembla un altre espai. Podria ser un problema: com sabria el descodificador quan deixar de llegir? Tanmateix, com que hem inclòs un caràcter de final de fitxer, el descodificador hi arribarà i, a continuació, s'aturarà, ignorant qualsevol altra cosa que s'hagi afegit després.
Part 2 de 2: Descodificació
Pas 1. Llegiu un fitxer codificat per Huffman
En primer lloc, llegiu la capçalera, que hauria de ser el mapa de codificació. Utilitzeu això per construir un arbre de descodificació de la mateixa manera que vau crear l'arbre que vau utilitzar per codificar el fitxer. Els dos arbres haurien de ser idèntics.
Pas 2. Llegiu el binari d'un dígit a la vegada
Travesseu l'arbre mentre llegiu: si llegiu amb un '0', aneu cap a l'esquerra secundària del node en què us trobeu i, si llegiu en un '1', aneu cap al fill correcte. Quan arribeu a una fulla (un node sense fills), heu arribat a un personatge. Escriviu el caràcter al fitxer descodificat.
A causa de la manera com s’emmagatzemen els caràcters a l’arbre, els codis de cada caràcter tenen una propietat de prefix, de manera que mai es pot produir cap codificació binària de caràcters a l’inici de la codificació d’un altre caràcter. La codificació de cada personatge és totalment única. Això facilita molt la descodificació
Pas 3. Repetiu fins que arribeu a l'EOF
Enhorabona! Heu descodificat el fitxer.
