Huffman kodifikazio

thumb|362x362px|Huffman kodifikazioan oinarritzen den zuhaitz bitarraren adibide bat.
**Huffman kodifikazioa** algoritmo bat da, konputazio-zientzia eta informazioaren teorian erabiltzen dena datuen konpresiorako. Luzera aldakorreko kodeetan oinarritzen den metodo bat da, agertzen diren sinbolo edo karaktereen maiztasunaren arabera, hauei kode zehatz bat esleitzeko erabiltzen dena.

David A. Huffmanek garatutako metodo bat da, MITen doktoretza gauzatzen zuen bitartean garatutakoa. Hau *A Method for the Construction of Minimum-Redundancy Codes* delako artikuluan argitaratu zen.

## Historia 
1951. urtean David Huffman eta bere klasekideek aukera izan zuten Informazioaren Teoria irakasgaian amaierako azterketa egin edo lan bat aurkezteko. Irakasleak lanaren nondik norakoak zehaztu zituen: kodifikazio bitar eraginkorrena bilatzearen inguruko lan bat. Huffman, kodifikazio eraginkorrena bilatzearen zailtasuna zela-eta, azterketarako ikasten hasi zen; baina ikasten ari zela ideia bat bururatu zitzaion: sinboloen probabilitatean oinarritutako zuhaitz bitarrak erabiltzea kodifikatzeko. Ideia hau landuz, metodorik eraginkorrena zela frogatu zuen.

Lan honekin Huffmanek bere irakaslea gainditu zuen, irakaslea Claude Shanonekin jardun baitzen antzeko kodifikazio bat sortu nahian. Huffmanek Shanon-Fano kodifikazioaren errore gehienak konpondu zituen bere metodoaren bidez.

## Kodifikazioa 
Kodifikazioaren oinarria da jatorriko informazio batetik hasita honi aldaketak aplikatu eta helburuko informazio bat lortzea, honela informazio bera lortzen da era ezberdinetan adierazita. Kodifikazioak helburu asko izan ditzake: erroreak saihestea, informazioa babestea, seinale analogikotik digitalera pasatzea, etab. Bada beste helburu bat duen kodifikazioa ere: datu gutxiago erabiliz informazio berdina transmititzea, alegia.

Konpresioa termino garrantzitsua da. Honen helburua datuen tamaina murriztea da, baina ahalik eta jatorriko informazio gutxien galduta. Hau informazioaren teorian asko aztertu den arlo bat da; izan ere, informazioa gordetzeko edo transmititzeko orduan baliabideak finituak dira eta, honenbestez, datuen tratamendu ona ezinbestekoa da.

Adibidez, kodifikazioa gauzatzen den kasu bat ondorengoa izango litzateke: Demagun eguraldiaren informazioa adierazten duen sentsore bat dagoela, eta honek datuak aztertzeko ikerketa zentro batera informazioa bidaltzen duela. Eguraldia adieratzeko honako hau egin daiteke sistema bitarra erabiliz:

00 → Eguzkitsua

01 → Lainotsua

10 → Euritsua

11 → Ekaitza

Metodo honetan 2 bit erabili dira egoera bakoitza adierazteko. Honela, egoera bakoitzean, sentsoreak eguraldia aztertuko du, eta egunaren arabera aurretik zehaztutako kodifikazio bidez, eguraldiaren datuak bidaliko ditu ikerketa zentrora. Kodifikatzeko metodo bat izango litzateke goiko adibidea, non printzipioz ausaz ezarri diren egoera bakoitzerako kodeak; halabaina, badaude kodeketa gauzatzeko beste metodo batzuk ere.

Orain demagun ikerketa zentroa oso gune eguzkitsuan dagoela, egoera honetan, sentsoreak ia beti "00" kodea bidaliko du, eta oso gutxi gainontzeko kodeak. Hau ikusita, bidea ez litzateke eguraldia adierazten duten datu guztiei pisu berdina ematea. Izan ere, gehien agertzen den kodeari (eguzkitsua) pisu gutxiago emanez gero (hau da, bi bit izan beharrean bit bakarra izatea) honen transmisio pisua erdira jaitsiko litzateke, "00" transmititu beharrean '0' soilik transmitituz, adibidez. Hau eginda, kodifikatzean konpresioa gauzatu da. Eguraldi eguzkitsua adierazteko bit gutxiago erabiliz gero, baliabide gutxiago beharko dira. Hau luzera aldakorreko kodeen oinarria da, eta printzipio honetan oinarritzen da Huffman kodifikazioa.

Kodifikatzeko sistema hau metodo estatisko batean oinarritzen da. Sinboloen probabilitateak aztertzen dira, bai letrak, zenbakiak zein eguraldia izan, hauen agerpenaren arabera bit gehiago edo gutxiago esleitzeko gehien erabiliko diren sinboloei. Hau dela eta, kodifikazio estatistiko deitzen zaie Huffman bezalako kodifikazioei.

Kodifikazioen efizientzia aztertzerako orduan, garrantzitsua den aldagai bat ezagutu behar da: sinboloen bataz besteko luzera (l). Bere izenak dioen moduan, aldagai honek egoera zehatz bateko sinbolo guztien kodifikazioen luzeren bataz bestekoa adierazten du. Hau zenbat eta txikiagoa izan, kodifikazioa efizienteagoa izango da konpresioaren ikuspuntutik.

\textstyle l=\sum_{k=1}^N P_k\times l_k \displaystyle

## Huffman kodifikazioa 
Huffman kodeketaren oinarria, beraz, sinboloak agertzen diren probabilitatearen arabera kodifikazio bitar motz bat esleitzea da; sinboloa zenbat eta gehiago agertu, orduan eta kode motzago bat ematen zaio. Algoritmoaren errendimentu optimoa lortuko da karaktere bakoitzari esleitutako bit kopurua, bere probabilitatearen logaritmoaren proportzionala denean.

### Huffmanen metodoa 
thumb|Huffman zuhaitz bitarra.
Metodoa ondorengo irudian ikusten den bezalako zuhaitz bitar baten sorreran oinarritzen da, non zuhaitzaren tamaina sinbolo kopuruaren araberako izango den.

Pausoak:

0 pausoa: Sinboloak identifikatzen dira eta bakoitzaren agerpen probabilitateak zehaztu. Sinboloak probabilitate txikienetik handienera antolatzen dira.

1 pausoa: Sinboloak ordenatuta izanik, probabilitate txikieneko bi sinboloak nodo batengatik ordezkatuko dira. Nodo berriak bi adarkadura izango ditu, hauek nodoa eraiki duten bi sinboloak izango dira. Nodoaren probabilitatea batu diren bi sinboloen probabilitateen batura izango da.

2 pausoa: Nodo berriarekin berriro 2 pausora itzuliz, prozesua errepikatuko da.

3 pausoa: Behar bezain beste aldiz errepikatuko dira 0→ 1→ 2 pausoak, nodo bakarra gelditu arte.

Behin zuhaitza eraikita, nodoetatik irteten diren adar bakoitza 0 edo 1 kodeaz izendatuko dira. Honela, adar bakoitza izendatuta izanda, zuhaitzaren errotik kodetu nahi den sinbolorako bidea gauzatuko da, eta bidean zeharkatutako adarretako kodeak hartuz sinboloaren kodea lortuko da.

Irudian ikusten den moduan, D sinboloak, probabilitate handiena duen sinboloak hain zuzen, kode laburrena dauka, eta A eta B sinboloek kode luzeena izango dute, agertzeko probabilitate gutxien daukatenak baitira.

Honako emaitzak lortu dira algoritmoa erabiliz:

D → 1

C → 01

A → 000

B → 001

Kodeketa erabiliz lortutako emaitza kodeketa egiten ez den kasuarekin konparatzen bada:

Kodeketa egin gabe: A, B, C eta D sinboloak izanda, 4 sinbolo adierazteko 2 bit beharko dira: 00, 01, 10 eta 11. Kodearen bataz besteko luzera kalkulatzen bada:

\textstyle \sum_{k=1}^N P_A\times l_A+P_B\times l_B+P_C\times l_C+P_D\times l_D\displaystyle

\textstyle \sum_{k=1}^N 0,1\times 2 bit+0,2\times 2 bit+0,3\times 2 bit+0,4\times 2 bit=2 bit\displaystyle

Kodeketa eginez:

\textstyle \sum_{k=1}^N 0,1\times 3 bit+0,2\times 3 bit+0,3\times 2 bit+0,4\times1 bit=1,9 bit\displaystyle

Emaitzetan ikusten da kodeketa eginez sinboloko bataz besteko luzera txikiagoa dela. Diferentzia ez da oso handia, baina kontuan hartu behar da hau adibide oso sinple bat dela eta emaitza hauek funtzionamendua aztertzeko soilik balio dutela.

erdian|thumb|480x480px|Zuhaitz bitarraren sorreraren adibidea.

### Huffman moldagarria edo dinamikoa 
Huffmanen metodo originala semi-moldagarria zen. Izan ere, honek bi prozesatze gauzatzen zituen: lehenengoa, sinboloen estatistikak lortzeko; eta, bigarrena, konpresioa egiteko estatistika horien arabera. Bi pauso hauen artean zuhaitz bitarra sortzen zuen. Bi aldiz prozesatu beharrak metodoa motela izatea dakar eta, honek, denbora errealeko aplikazioetarako erabilgarria ez izatea. Hori dela eta, praktikan Huffman kodeketa moldagarria edo dinamikoa erabiltzen da.

Hemen, konpresore eta deskonpresoreak zuhaitz bitar huts batekin hasten dira, eta bata konprimitzen eta bestea deskonprimitzen doan neurrian zuhaitza osatzen joango dira.

Metodo honek Huffman kodifikazioa denbora errealean aplikatzea ahalbideratzen du. Halabaina, errealitatean ez da Huffman kodifikazioa bere horretan erabiltzen. Beste kodifikatzeko metodo batzuek erabiltzen dute Huffman, beraien algoritmoen oinarritzat hartzen dutena.

## Erreferentziak 
## Ikus, gainera 
* Entropia (Informazio teoria)
* Informazio kantitate
* Datu-konpresio

## Kanpo estekak 
* Huffman kodifikazioaren kalkulagailua
* Huffman kodifikazioko zuhaitz bitarra