Lankide:TxapasXIV/Huffman kodifikazio
Huffman kodifikazioa konputazio zientzia eta informazioaren teorian erabiltzen den datuen konpresiorako algoritmo bat da. Luzera aldakorreko kodeetan oinarritzen den metodo bat da, agertzen diren sinbolo edo karaktereen maiztasunaren arabera, hauei kode konkretu 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 aldatu
1951. urtean David Huffman eta bere klasekideek Informazioaren Teoria irakasgaian azterketa final bat egin edo lan bat aurkezteko aukera izan zuten. Irakasleak lanaren nondik norakoak zehaztu zituen: kodifikazio bitar efizienteena bilatzearen inguruko lan bat. Huffmanek, kodifikazio hoberena bilatzearen zailtasuna zela eta, azterketarako ikasten hasi zen. Ikasten ari zela ideia bat bururatu zitzaion Huffmani: sinboloen probabilitatean oinarritutako zuhaitz bitarrak erabiltzea kodifikatzeko. Ideia hau landuz, metodorik efizienteena 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.[1]
Kodifikazioa aldatu
Kodifikazioaren oinarria, jatorriko informazio batetik hasita honi aldaketak aplikatu eta helburuko informazio bat lortzea da, informazio bera lortuz era ezberdinetan adierazita. Kodifikazioak helburu asko izan ditzake: erroreak saihestea, informazioa babestea, seinale analogikotik digitalera pasatzea, etab. Ordea, artikulu honetan, beste helburu bat duen kodifikazioa aztertuko da: datu gutxiago erabiliz informazio berdina transmititzea.
Konpresioa termino garrantzitsu bat da. Helburua datuen tamaina murriztea da, ahalik eta jatorriko informazio gutxien galduz. Hau informazioaren teorian asko aztertu den arlo bat da, izan ere, informazioa gordetzerako edo transmititzerako orduan baliabideak finituak dira, eta datuen tratamendu ona ezinbestekoa da. Adibide bat jartzearren, 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. Ikusitako adibide sinple hau kodifikatzeko metodo bat izango litzateke, hemen printzipioz ausaz ezarri dira egoera bakoitzerako kodeak, ordea, badaude kodeketa bat gauzatzeko beste metodo batzuk.
Orain jo dezagun ikerketa zentroa oso gune eguzkitsuan dagoela, egoera honetan, sentsoreak ia beti "00" kodea bidaliko du, eta oso gutxi gainontzeko kodeak. Hau ikusita, eguraldia adierazten duten datu guztiei pisu berdina ematea ez dirudi ideia ona. Gehien agertzen den kodeari (eguzkitsua) pisu gutxiago emanez gero, hau da, bi bit izan beharrean bit bakarra, honen transmisio pisua erdira jaitsiko litzateke, "00" transmititu beharrean '0' soilik adibidez. Hau eginda, kodifikatzean konpresioa gauzatu da. Orain, eguraldi eguzkitsua adierazteko bit gutxiago erabiliko dira, baliabide gutxiago beharko dira ondorioz. 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 konkretu bateko sinbolo guztien kodifikazioen luzeren bataz bestekoa adierazten du. Hau gero eta txikiagoa izan, kodifikazioa efizienteagoa izango da konpresioaren ikuspuntutik.
Huffman kodifikazioa aldatu
Huffman kodeketaren oinarria beraz, sinboloak agertzen diren probabilitatearen arabera kodifikazio bitar motz bat esleitzea da; sinboloa zenbat eta gehiago agertuz, orduan eta kode motzago bat emanez. Algoritmoaren errendimentu optimoa lortuko da karaktere bakoitzari esleitutako bit kopurua, bere probabilitatearen logaritmoaren proportzionala denean.
Huffmanen metodoa aldatu
Metodoa ondorengo irudian ikusten den bezalako zuhaitz bitar baten sorreran oinarritzen da, non zuhaitzaren tamaina sinbolo kopuruaren araberako izango den.
Pausoak:[2]
0 pausoa: Sinboloak identifikatzen dira eta bakoitzaren agerpen probabilitateak zehaztu. Sinboloak probabilitate txikienetik handienera antolatzen dira.
1 pausoa: Sinboloak ordenatuta izanda, 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 bestez 0→ 1→ 2 pausoak errepikatzen dira 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 emaitzak 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:
Kodeketa eginez:
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.
Huffman moldagarria edo dinamikoa aldatu
Huffmanen metodo originala semi-moldagarria zen. Izan ere, honek bi prozesatze gauzatzen zituen; lehenengoa sinboloen estatistikak lortzeko eta bigarrengoa konpresioa egiteko estatistika horien arabera, bi pauso hauen artean zuhaitz bitarra sortuz. Bi aldiz prozesatu beharrak metodoa motela izatea ekartzen du, eta honek denbora errealeko aplikazioetarako erabilgarria ez izatea dakar. 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. Ordea, errealitatean ez da Huffman kodifikazioa bere horretan erabiltzen. Beste kodifikatzeko metodo batzuk erabiltzen dute Huffman, hau beraien algoritmoentzat oinarritzat hartuz.[2]
Errendimendu maximoa aldatu
Huffman algoritmoa, aipatu den moduan, fitxategi bateko sinboloen agertzeko probabilitatean oinarritzen da konpresioa gauzatzeko. Hau oso baliagarria da, izan ere, beti daude beste batzuk baino gehiago erabiltzen diren hitzak, ingelesez adibidez A, T eta E letrak dira gehien erabiltzen direnak, eta errusieran berriz O, E eta A.
Letra guztiek agertzeko probabilitate berdina duten kasuan Huffman algoritmoak ez du inolako eraginik izango, ez baitu konprimitzeko erabiltzen duen parametro berezirik izango. Honela, aurkako kasua aztertuz honako ondoriora iritsi ahal gara: Sinbolo guztiak agertzeko probabilitatearen gero eta zati handiago bat sinbolo gutxitan banatzean konpresioa gero eta handiagoa izango da.
Honek Huffman algoritmoa ezagututa zentzu handia dauka, izan ere, sinbolo asko izanda ere, gutxi batzuen artean banatzen bada agerpen probabilitate totala, sinbolo hauei oso kode motzak esleitu ahal izango zaie. Honek beste sinboloei luzera handiko kode bat esleitzea ekarriko du, baina hauek oso gutxi erabiltzen badira, erredendimendu aldetik askoz errentagarriagoa izango da gutxi batzuk kode luzeak izatea beste askok kode laburrak badituzte.
Aplikazioak aldatu
Huffman algoritmoaren konprimatzeko gaitasuna argi ikusi da. Baina, gaur egungo konpresio metodoak oso espezializatuak dira, hau da, nahiz eta oinarrizko konpresio metodo bat izan erreferentziatzat, bakoitzak bere aldaketak egiten ditu erabiliko den kasurako egokitu dadin.
Hau dela eta, Huffman algoritmoa konpresio formatu ezberdinetan erabiltzen da inglesez esaten den “back-end” moduan. Horien artean PKZIP eta multimedia kodek ezberdinetan: JPEG eta MP3 bezalakoetan adibidez.
Konpresio metodorik hoberena aukeratzea ez da erraza. Metodo bat oso azkarra izan daiteke, denbora errealerako ezin hobea izanda. Beste batek berriz, oso konpresio ona lor dezake, baina motela izan aldi berean. Honela, hiru ezaugarri definitzen dira konpresio metodo bat aztertzeko: konpresio abiadura, konpresio tasa eta memoriaren erabilera.
Huffmanen metodoa gaur egun konpresio metodo askok erabiltzen dute beraien oinarri moduan, ordea, gaur egun, kodetze aritmetikoa pisu handia hartzen hasi da. Huffmanek egin dezakeen guztia, aritmetikoak hobeto egiten duela esaten baita.[3]
Erreferentziak aldatu
- ↑ (Gaztelaniaz) Codificación Huffman. 2020-09-09 (Noiz kontsultatua: 2020-12-01).
- ↑ a b https://www.tamps.cinvestav.mx/~mmorales/documents/Compre.pdf
- ↑ (Ingelesez) Bookstein, A.; Klein, S. T.. (1993-12-01). «Is Huffman coding dead?» Computing 50 (4): 279–296. doi:. ISSN 1436-5057. (Noiz kontsultatua: 2020-12-01).