Java platforma i jezik su započeti kao interni istraživački projekt tvrtke Sun Microsystems u prosincu 1990., iako je srž ideje nastala nekoliko godina ranije.

Projekt NeWS

Sve je započeo James Gosling koji pokrenuo projekt nazvan NeWS (Network/extensible Window System). Ideja projekta NeWS je bila napraviti softver koji omogućava kreiranje prozora (engl. windows) u grafičkom korisničkom sustavu, na bilo kojem računalu, bez obzira o kojem proizvođaču se radi, Sun, Hewlett-Packard, IBM i sl. To je u to vrijeme bio veliki problem jer su grafička sučelja uzimala sve više trakcije, i svaki proizvođač računala je imao svoj softver za crtanje prozora, što je značilo da je svaki komercijalni softver morao biti posebno rađen za svakog proizvođača jer je morao implementirati njegov set standarda za crtanje prozora. Sun je planirao izdavati licence za NeWS proizvođačima računala dok tehnologija ne postaje industrijski standard. Takvo što bi učvrstilo poziciju Suna kao tehnološkog predvodnika što bi kompaniju učinilo privlačnijom potrošačima. Kompanija je službeno lansirala NeWS na Comdex sajmu u Atlanti na proljeće 1987., te krenula u potragu za partnerima. Prethodni proizvod tvrtke Sun, NFS (Network File System), je bio iznimno uspješan te je postavio industrijski standard koje su ostale kompanije morale slijediti. Ta činjenica je rezultirala velikim otporom NeWS-u, te kompanija nije uspjela ostvariti željena partnerstva kako bi ga probila na željeni dio tržišta, zbog čega je u konačnici projekt propao. Na sreću NeWS nije bio totalni gubitak za Sun. Srž NeWS-a, izvršavanje neovisno o hardveru, ponovno će se roditi u Javi nekoliko godina kasnije.¹

Tajni projekt Green

Krajem 1990. na scenu stupa Patrick Naughton, tada dvadesetpetogodišnji ambiciozni programer, Patrick je bio nezadovoljan smjerom kojim je kompanija krenula. Napuštanjem projekta NeWS, programeri koji su radili na njemu su premješteni na druga istraživačka mjesta, ali kompanija je djelovala uspavano, nije bilo drugih značajnih projekata. To je Patricka natjeralo da potraži novi posao, te je dobio priliku pridružiti se kompaniji Next koju je osnovao Steve Jobs. Iako je prošao sve intervjue i bio primljen u kompaniju, ipak nije mogao samo tako otići bez da to kaže Scottu McNealyu, CEO-u Sun Microsystemsa. Nakon razgovora, Scott mu je rekao da se pretvara da je Bog i pošalje mu e-mail s popisom stvari koje ne valjaju u kompaniji, s prijedlozima kako ih popraviti. To je bio vrlo dobar potez jer je Patrick napisao poduži e-mail u kojem je iznio sve svoje frustracije, još iz vremena NeWS projekta. Ono što je Patrick zamislio je malu usko povezanu grupu ljudi koja će raditi brzo bez birokracije i opozicije. Scott je proslijedio e-mail ključnim ljudima u kompaniji koji je u konačnici pronašao put do Jamesa Goslinga. James je instantno prepoznao iskru te krenuo u akciju. Upoznao ga je sa Mike Sheridanom te je oformljen tim ljudi koji su danas poznati kao začetnici Jave, James Gosling, Patrick Naughton i Mike Sheridan. Projekt je ubrzo dobio ime Green, a poslovni plan je nazvan “Iza zelenih vrata”, po najpopularnijem pornografsku filmu u tom vremenu. Kako bi osigurali nesmetan rad i otklonili birokratske probleme, projekt je rađen u tajnosti, te su za njega znali samo najviši rukovodioci kompanije.²

Tim je originalno razmišljao o nadogradnji postojećeg C++ jezika, međutim odustali su od te ideje zbog više razloga. Zbog toga što su razvijali jezik za embedded sustave koji imaju ograničene resurse, zaključili su da C++ zahtjeva previše memorije. Jezik također nije imao sakupljač smeća (engl. Garbage collector), što je značilo da programeri moraju ručno upravljati sistemskom memorijom, što je izazovan zadatak koji često dovodi do problema.

Gosling je probao modificirati i proširiti C++ (nazivajući ga C++ ++ –), međutim ubrzo napušta tu ideju i stvara novi programski jezik, kojeg naziva Oak (hrv. hrast), po drvetu kojeg je imao ispred ureda.

Zeleni projekt u jednom trenutku postaje Firstperson. Tim koji je radio na Firstpersonu je htio napraviti interaktivni uređaj za upravljanje televizijom, međutim televizijska industrija nije bila previše zainteresirana jer su korisnicima dali previše slobode. Ubrzo cijeli projekt Firstperson propada.

1993. godine, naglo započinje razvoj World Wide Weba i ljudi iz Suna uuočavaju veliki potencijal Jave u tome području. Naughton izrađuje mali web preglednik pod nazivom WebRunner, kasnije preimenovan u HotJava 1995. Java je omogućavala dodavanje dinamičkih interaktivnih sadržaja i animacija na internetske stranice.

U listopadu 1994. Sun mijenja naziv jezika u Java, zbog toga što je već postojala tvrtka Oak Technologies. Iako je bilo moguće preuzimanje Java 1.0a verzije 1994. godine, prva službena verzija Jave pod imenom Java 1.0a2 je objavljenja 23. svibnja 1995. na SunWorld konferenciji.

2009. godine Oracle preuzima Sun Microsystems.

18.03.2014. Sun Microsystems objavljuje inačicu Java 8.

Reference

1. Southwick, Karen (1999). High Noon: the inside story of Scott McNealy and the rise of Sun Microsystems. New York [u.a.]: Wiley. pp. 72–74. ISBN 0471297135. ↩︎
2. Southwick, Karen (1999). High Noon: the inside story of Scott McNealy and the rise of Sun Microsystems. New York [u.a.]: Wiley. pp. 123–124. ISBN 0471297135. ↩︎

U računalstvu i teoriji informacije, duljina kodne riječi označava broj znamenaka (bitova) u jednoj kodnoj riječi. Često se označava malim slovom $$l$$. Ona je vrlo bitno svojstvo kodne riječi. Generalno, preferiraju se kraće kodne riječi kako bi efikasnost koda bila što veća. [1]

Prosječna duljina kodne riječi

Prosječna duljina kodne riječi koristi se kod entropijskog neravnomjernog kodiranja. Često se označava velikim slovom $$L$$. Ona označava prosječan broj znamenaka (bitova) kodne riječi u danoj tablici kodnih riječi uzimajući u obzir vjerojatnost pojavljivanja kodnih riječi. Kod ravnomjernog kodiranja nema smisla govoriti o prosječnoj duljini koda zbog toga što je duljina svake kodne riječi jednaka. U takvom slučaju je prosječna duljina kodne riječi identična duljini jedne kodne riječi. Ona je bitan faktor koji utječe na efikasnost koda.

Prosječna duljina kodne riječi računa se kao ponderirana aritmetička sredina pojedinih kodnih riječi, tj. može se izračunati kao suma svih umnožaka duljina pojedinih kodnih riječi i njihovih pripadajućih vjerojatnosti. [2]
Prikazano sljedećom jednadžbom:

<latex>L\left( X \right)=\sum_{i=1}^{n}P\left( x_{i} \right)\cdot l_{i}</latex>

Pri čemu je:

• $$L\left( X \right)$$ – prosječna duljina kodne riječi
• $$n$$ – ukupan broj kodnih riječi
• $$P\left( x_i \right)$$ – vjerojatnost pojave $$i$$-tog simbola
• $$l_i$$ – duljina $$i$$-te kodne riječi

Primjer računanja prosječne duljine kodne riječi

Zamislimo slikovnicu u kojoj se pojavljuju samo prva četiri slova engleske abecede. Iz slikovnice izračunamo vjerojatnost pojave pojedinih slova te zapišemo u tablicu. Zamislimo da je netko već uspješno iskodirao slova. Izračunajmo prosječnu duljinu kodne riječi.

Simbol ($$x_i$$)	Vjerojatnost pojave ($$P\left( x_i \right)$$)	Kodna riječ	Duljina kodne riječi ($$l_i$$)
A	1/2	0	1
B	1/6	10	2
C	1/6	110	3
D	1/6	111	3

<latex>L\left( X \right)=\sum_{i=1}^{n}P\left( x_{i} \right)\cdot l_{i}</latex>

<latex>L=\frac{1}{2}\cdot 1 + \frac{1}{6}\cdot 2 + \frac{1}{6}\cdot 3 + \frac{1}{6}\cdot 3 = 1,8\dot{3}\:bita</latex>

Prosječna duljina kodne riječi u ovome slučaju iznosi 1.83 bita.

Donja granica prosječne duljine kodne riječi

Ako govorimo o kodiranju bez gubitka informacija, onda je jasno da prosječna duljina kodne riječi ne može biti manja od entropije. Kada bi ona bila manja, kôd bi nosio manje informacija od samog izvora, što znači da se jedan dio informacija izgubio u procesu kodiranja. Iz toga slijedi da prosječna duljina kodne riječi mora biti veća ili jednaka entropiji. [3]

<latex>L\left( X \right)\geqslant H\left( X \right)</latex>

Kompaktnost koda

Informacije je moguće kodirati na više različitih načina pa tako različiti kodovi imaju i različite duljine kodnih riječi.

Za neki kod možemo reći da je kompaktan, za jedan izvor, ako mu je prosječna duljina kodne riječi manja ili jednaka prosječnoj duljini svih ostalih kodova koji se mogu dekodirati na jedinstven način za taj isti izvor. [4]

Reference

1. Luenberger, David G. (2006). Information Science, str. 22. Princeton, New Jersey: Princeton University Press. ISBN 978-0-637-12418-3.
2. Togneri R., deSilva Christopher J.S. (2003). Fundamentals of Information Theory and Coding Design, str. 121. Boca Raton, Florida: CRC Press. ISBN 978-0-203-99810.
3. Togneri R., deSilva Christopher J.S. (2003). Fundamentals of Information Theory and Coding Design, str. 123. Boca Raton, Florida: CRC Press. ISBN 978-0-203-99810.
4. Togneri R., deSilva Christopher J.S. (2003). Fundamentals of Information Theory and Coding Design, str. 121. Boca Raton, Florida: CRC Press. ISBN 978-0-203-99810.

Isječak Java kôda prikazuje primjer metode za množenje dva cijela broja, bez upotrebe operatora množenja.
Množenje je izvedeno upotrebom while petlje.

public static int mnozenje(int prviBroj, int drugiBroj) {
	int umnozak = 0;
	if (drugiBroj > 0) 
		drugiBroj = 0 - drugiBroj
		prviBroj = 0 - prviBroj;
	}
	while (drugiBroj > 0) {
		umnozak = umnozak + prviBroj;
		drugiBroj = drugiBroj - 1;
	}
	return umnozak;
}

Paritetni bit je dodatni bit koji se dodaje na kraj kodne riječi da bi se osigurao određen broj jedinica u njoj. Paritetni bit se određuje tako da, u kombinaciji s ostalim bitovima, kodna riječ sadrži isključivo paran broj jedinica kod parnog pariteta (engl. even parity), odnosno, neparan broj jedinica kod neparnog pariteta (engl. odd parity). [1] S time omogućuje jednostavnu detekciju pogreške u prijenosu, ali ju ne može ispraviti.

Parni i neparni paritet

Pri korištenju parnog pariteta, paritetni bit se dodaje tako da u kombinaciji s bitovima kodne riječi uvijek postoji isključivo paran broj jedinica. Ako dana kodna riječ sadrži paran broj jedinica, paritetni bit koji dodajemo ima vrijednost nula, a ako dana kodna riječ sadrži neparan broj jedinica, paritetni bit koji dodajemo ima vrijednost jedan. Ukupan broj jedinica, uključujući paritetni bit, mora biti paran.

Pri korištenju neparnog pariteta, paritetni bit se dodaje tako da u kombinaciji s bitovima kodne riječi uvijek postoji isključivo neparan broj jedinica. Ako dana kodna riječ sadrži paran broj jedinica, paritetni bit koji dodajemo ima vrijednost jedan, a ako dana kodna riječ sadrži neparan broj jedinica, paritetni bit koji dodajemo ima vrijednost nula. Ukupan broj jedinica, uključujući paritetni bit, mora biti neparan.

Za za istu kodnu riječ, paritetni bit kod parnog i neparnog pariteta imaju inverznu vrijednost.

Primjer korištenja parnog i neparnog paritetnog bita

Zadanim kodnim riječima je potrebno dodati paritetni bit koristeći parni i neparni paritet.

Kodna riječ (7 znamenaka)	Kodna riječ s parnim paritetom (8 znamenaka)	Kodna riječ s neparnim paritetom (8 znamenaka)
0000000	00000000	00000001
1000000	10000001	10000000
0110011	01100110	01100111
1010101	10101010	10101011
1111111	11111111	11111110

Označen i razmaknut paritet

Ponekad je paritetni bit prisutan ali se ne koristi te nema nikakvu funkciju. Takav paritet se često naziva označen paritet (engl. mark parity) ili razmaknut paritet (engl. space parity), ovisno o prijednosti paritetnog bita. Kod označenog pariteta, paritetni bit uvijek ima vrijednost 1. Kod razmaknutog pariteta, paritetni bit uvijek ima vrijednost nula. [2]

Detekcija pogrešaka

Paritetni bit se koristi za jednostavnu detekciju pogrešaka prilikom prijenosa kodnih riječi. Ako se neparan broj bitova prenese pogrešno (uključujući paritetni bit), paritet će biti netočan te će ukazati na pogrešku u prijenosu. Paritetni bit može samo otkriti pogrešku, međutim ne može ju ispraviti jer ne može otkriti koji bit ili bitovi su pogrešno preneseni. Stoga, u slučaju otkrivanja pogreške u primljenom podatku, podatak se mora potpuno odbaciti, te se slanje mora ponoviti. Njegova mana je da slanje podatka preko linije s izraženim šumom može potrajati duže vremena uslijed stalnih ponavljanja. Njegove prednosti su to što koristi samo jedan dodatni bit za zaštitu te zahtjeva samo jedan XOR sklop za generiranje paritetnog bita. [3]

Primjena

Paritetni bit se najčešće primjenjuje u hardveru kod kojeg se slanje kodne riječi može jednostavno ponoviti u slučaju pogreške u prijenosu. Na primjer, PCI sabirnice koriste paritet za detektiranje pogrešaka u prijenosu. [4]

Reference

1. Paunović, Stanko (1999). Digitalna Elektronika, 1. svezak, 2. izdanje, str. 33. Zagreb: Školska Knjiga. ISBN 978-953-0-21147-6.
2. Venkateswarlu, N. B. (2014). Computer Science and Information Technology for GATE, str. 1.89. New Delhi: McGraw Hill Education (India) Private Limited. ISBN 978-1-25-902720-8.
3. Rajput, Uday Singh (2012). Advanced Discrete Mathematics, str. 55. New Delhi: PHI Learning Private Limited. ISBN 978-81-203-4589-8.
4. PCI Special Interest Group (1998). PCI Local Bus Specification Revision 2.2., str. 93. (PDF)

U računalstvu i teoriji informacije, Huffmanov kod je poseban prefiksni kod koji se najčešće koristi za sažimanje podataka bez gubitaka. Proces pronalaženja ili korištenja toga koda naziva se Huffmanovo kodiranje. Algoritam pomoću kojega se pronalazi kod, konstruirao je David Albert Huffman za vrijeme doktorskog studija na MIT-u. Svoje otkriće objavio je u radu “A Method for the Construction of Minimum-Redundancy Codes” 1952. [1]

Huffmanov kod je neravnomjeran kod. Algoritmom se dobiva tablica kodova koja se bazira na vjerojatnosti pojave svakog simbola pojedinačno, što znači da će simboli koji imaju veću vjerojatnost pojavljivanja biti kodirani s kraćim kodnim riječima, a simboli koji imaju manju vjerojatnost pojavljivanja biti kodirani s duljim kodnim riječima. Takvim načinom kodiranja povećava se efikasnost koda.

Huffmanovo kodiranje

Huffmanov algoritam

Huffmanov algoritam je algoritam pomoću kojeg se na jednostavan način može kodirati neka informacija. On nam govori sljedeće… [2]

1. Posložimo vjerojatnosti od najveće prema najmanjoj, tako da se najveća vjerojatnost nalazi na krajnoj lijevoj strani, a najmanja na krajnjoj desnoj strani.
2. Zbrojimo dvije krajnje desne vjerojatnosti.
3. Zbrojimo dvije najmanje vjerojatnosti. U slučaju postojanja više jednakih najmanjih vjerojatnosti, zbrojimo bilo koje dvije, obično se zbrajaju dvije s krajnje desne.
4. Ponavljamo korak 3 dok ne ostane samo jedna vjerojatnost. Ako je stablo ispravno, ona će uvijek biti jednaka 1.
5. Počevši od vrha prema dnu, na svakoj točki na kojoj se stablo grana, dodijelimo po jednu binarnu vrijednost (0 ili 1) svakoj grani. Obično se lijevoj grani pridodaje 0 a desnoj 1. Ako se napravi obrnuto, kod će izgledati malo drugačije, ali će imati identična svojstva.
6. Počevši od vrha, gibamo se najkraćim putem do prve vjerojatnosti, te pritom ispisujemo bitove na koje nailazimo, redom, s lijeva na desno. Ponavljamo za svaku vjerojatnost pojedinačno.

Primjer Huffmanovog algoritma

Zamislimo sljedeći slučaj. Meteorološka postaja nalazi se na otoku koji je 10 km udaljen od najbližeg grada na kopnu. U meteorološkoj postaji nalazi se osoba koja svaki dan, točno u podne, zabilježi vrijeme na pučini. Nakon toga u svome čamcu otplovi do grada te mještanima preda informaciju o vremenu na pučini. To je vrlo naporan posao, no na svu sreću, tehnološkom revolucijom, izumljen je uređaj koji ima mogućnost slanja električnih signala u grad, kroz žicu koju su postavili. Dogovoreno je slanje električnog signala koji predstavlja određeno vrijeme na pučini. Dogovorena su 4 različita vremena: sunčano, oblačno, maglovito te kišno. Kako bi poslali informaciju o vremenu s pomoću električnog signala, potrebno je svako vrijeme pojedinačno predstaviti nekim kodom koji se potom šalje električnim signalom. Uzmimo u obzir da su to bili sami početci tehnike pa je stoga svaki poslani signal (bit) bio jako skup. Iz toga razloga je bilo potrebno smanjiti broj signala koji se šalju. Bilo je potrebno pronaći najefikasniji kod. Iz dosadašnjih mjerenja izračunali su vjerojatnost pojave pojedinog vremena. Vjerojatnost sunčanog vremena je iznosila 1/2. Vjerojatnost oblačnog vremena je iznosila 1/6. Vjerojatnost maglovitog vremena je iznosila 1/6. Vjerojatnost kišnog vremena je iznosila 1/6. Vidimo da je vjerojatnost sunčanog vremena najveća, što znači da je veći dio godine sunčano vrijeme, te da će se ta informacija najčešće slati. Kako bi trošak bio najmanji, bilo bi logično signal koji se šalje najčešće predstaviti najkraćim mogućim kodom. Pitanje je, kako doći do najefikasnijeg koda?
Ovaj zadatak riješit ćemo pomoću Huffmanovog algoritma crtajući Huffmanovo stablo.

1. Posložimo vjerojatnosti od najveće prema najmanjoj, tako da se najveća vjerojatnost nalazi na krajnoj lijevoj strani, a najmanja na krajnjoj desnoj strani.

2. Zbrojimo dvije krajnje desne vjerojatnosti.

3. Zbrojimo dvije najmanje vjerojatnosti. U slučaju postojanja više jednakih najmanjih vjerojatnosti, zbrojimo bilo koje dvije, obično se zbrajaju dvije s krajnje desne.

4. Ponavljamo korak 3 dok ne ostane samo jedna vjerojatnost. Ako je stablo ispravno, ona će uvijek biti jednaka 1.

5. Počevši od vrha prema dnu, na svakoj točki na kojoj se stablo grana, dodijelimo po jednu binarnu vrijednost (0 ili 1) svakoj grani. Obično se lijevoj grani pridodaje 0 a desnoj 1. Ako se napravi obrnuto, kod će izgledati malo drugačije, ali će imati identična svojstva.

6. Počevši od vrha, gibamo se najkraćim putem do prve vjerojatnosti, te pritom ispisujemo bitove na koje nailazimo, redom, s lijeva na desno. Ponavljamo za svaku vjerojatnost pojedinačno.

Ovime smo dobili najefikasniji kod za navedene vjerojatnosti.

Možemo izračunati efikasnost koda. Za efikasnost koda nam je potrebna entropija i prosječna duljina kodne riječi.

Entropiju izračunamo kao sumu svih pojedinačnih entropija.

<latex>H\left( X \right) = \sum_{i=1}^{n}P\left( x_i \right) \cdot log_2\left( \frac{1}{P\left( x_i \right)} \right)</latex>

<latex>H=\frac{1}{2}log_2\left( \frac{1}{\frac{1}{2}} \right)+\frac{1}{6}log_2\left( \frac{1}{\frac{1}{6}} \right)+\frac{1}{6}log_2\left( \frac{1}{\frac{1}{6}} \right)+\frac{1}{6}log_2\left( \frac{1}{\frac{1}{6}} \right) = 1,792481\text{ }bita</latex>

Prosječnu duljinu kodne riječi možemo izračunati kao sumu umnoška vjerojatnosti i duljine kodne riječi.

<latex>L\left( X \right) = \sum_{i=1}^{n}P\left( x_i \right)\cdot l_i</latex>

<latex>L=\frac{1}{2}\cdot 1+\frac{1}{6}\cdot 2+\frac{1}{6}\cdot 3+\frac{1}{6}\cdot 3 = 1,8\dot{3}\text{ }bita</latex>

Efikasnost koda možemo izračunati kao omjer entropije i prosječne duljine kodne riječi.

<latex>\eta\left( X \right)=\frac{H\left( X \right)}{L\left( X \right)}</latex>

<latex>\eta=\frac{1,792481}{1,8\dot3}=0,979498\text{ }\frac{bit}{simbol}</latex>

U ovome slučaju efikasnost koda iznosi približno 98%. Vidimo da je izračunata prosječna duljina kodne riječi samo malo veća od izračunate entropije. Tako da ne samo da je ovaj kod efikasan, on je ujedno i veoma blizu teoretskog limita kojeg je postavio Shannon.

Fleksibilnost Huffmanovog algoritma

Kako u prethodnom primjeru postoji više jednakih vjerojatnosti, zadatak smo mogli riješiti i na drugi način. Na primjer da smo prvo zbrojili vjerojatnosti za oblačno i maglovito vrijeme, a potom tu vrijednost s vjerojatnosti za kišno vrijeme. Kodne riječi bi bile u različitom poretku. Prosječna duljina kodne riječi bi ostala ista, a samim time i efikasnost.

U nekim slučajevima se može promijeniti i duljina kodne riječi. Promotrimo sljedeću tablicu.

Vjerojatnost ($$p_i$$)	Kod 1	Kod 2
0,4	1	00
0,2	01	10
0,2	000	11
0,1	0010	010
0,1	0011	011

Oba koda su dobivena pomoću Huffmanova algoritma, međutim na prvi pogled izgledaju potpuno različito. Duljine kodnih riječi su različite. Uzmimo vjerojatnost 0,4, u prvom kodu duljina kodne riječi iznosi 1 bit, a u drugom kodu duljine kodne riječi iznosi 2 bita. Međutim ako bi izračunali prosječnu duljinu kodne riječi, ona bi u oba slučaja iznosila 2,2 bita što znači da bi efikasnost bila jednaka u oba slučaja. Huffmanov algoritam uvijek daje najefikasniji kod s najmanjom mogućom prosječnom duljinom kodne riječi za određeni skup vjerojatnosti, iako je moguće dobiti više naizgled različitih kodova. To upravo demonstrira fleksibilnost Huffmanovog algoritma. [3]

Huffmanovo dekodiranje

Huffmanov kod je kod s prefiksom što znači da postoji samo jedan način na koji se kodna riječ može dekodirati. Taj uvjet je osiguran zbog toga što ni jedna kodna riječ ne predstavlja prvi dio (prefiks) neke druge kodne riječi. Ako taj uvjet ne bi bio osiguran, onda bi jedno kodnu riječ mogli dekodirati na više različitih načina. Ispunjenje ovog uvjeta se jasno vidi na samom Huffmanovom stablu.
Proces dekodiranja je vrlo jednostavan. Prilikom dekodiranja se koristi prethodno izgrađeno Huffmanovo stablo, tako što čitamo kodne riječi bit po bit, pri čemu se počevši od vrha (korijena) spuštamo duž grana na kojima se nalaze pojedini bitovi, sve dok ne dođemo do simbola. Na ovaj način možemo potpuno rekonstruirati početni simbol pa stoga Huffmanov kod spada u grupu reverzibilnih kodova.

Sažimanje podataka

Statičko Huffmanovo kodiranje

Osnovna ideja Huffmanovog kodiranja je pridodijeliti kodne riječi najmanje duljine simbolima koji se najčešće pojavljuju. Iz tog razloga je za primjenu Huffmanovog kodiranja potrebno znati vjerojatnost pojave određenog simbola. Na temelju tih vjerojatnosti, u statičkom Huffmanovom kodiranju, Huffmanovo stablo se kreira na samom početku kodiranja te se više ne mijenja tijekom procesa. Međutim, ovo je ograničavajući faktor u mnogim primjenama. U slučajevima gdje nije moguće točno odrediti vjerojatnost pojave određenog simbola ili u slučajevima gdje se ona mijenja dinamički, primjena Huffmanovog koda neće dati najveće moguće sažimanje.

Uzmimo na primjer Hrvatski jezik. Znamo približno vjerojatnosti pojava određenih slova u hrvatskom jeziku. Pomoću tih vjerojatnosti možemo konstruirati Huffmanovo stablo te izvesti kodne riječi za pojedino slovo. Huffmanovim algoritmom dobijemo najkraće kodne riječi za slova koja se pojavljuju najčešće, tj. najdulje kodne riječi za slova koja se pojavljuju najrjeđe. Međutim, problem se javlja ako tu tablicu iskoristimo na dvije knjige različitih tematika. Recimo da se radi o znanstveno-fantastičnom romanu i znanstvenom radu iz područja elektrotehnike. Ako primijenimo naše stablo na znanstveno-fantastični roman, nećemo postići jednak stupanj sažimanja kao na znanstvenom radu. Razlog tomu je različita vjerojatnost pojave pojedinih slova. U znanstvenom radu će se možda češće pojavljivati slova U (napon), I (struja), R (otpor) nego u romanu.

Možemo reći da Huffmanov kod nije univerzalan kod što znači da neće dati najveću moguću kompresiju u svim primjenama, upravo zbog toga što je ovisan o poznavanju vjerojatnosti. Kako bi se nosili s time, razvijena je nova metoda Huffmanovog kodiranja, nazvana dinamičko ili adaptivno Huffmanovo kodiranje.

Dinamičko (adaptivno) Huffmanovo kodiranje

Kod dinamičkog (adaptivnog) Huffmanovog kodiranja, prilikom svakog novog kodiranja, vjerojatnosti pojave simbola računaju se dinamički, tijekom samog procesa kodiranja. To ipak nije najefikasnija metoda jer se kod takvog postupka Huffmanovo stablo stalno iznova mijenja pa takvo kodiranje ima veće vrijeme izvršavanja. Stoga se za npr., kodiranje teksta, koriste kodovi s manjim vremenom izvršavanja, poput Lempel-Ziv koda.

Primjena

Huffmanovo kodiranje se često koristi pri sažimanju podataka, npr. u DEFLATE algoritmu za sažimanje kojeg koriste mnogi programi sa sažimanje datoteka različitih vrsta poput .ZIP datoteka. [4] Huffmanovo kodiranje se također koristi u sažimanju .JPEG i .MP3 datoteka. [5] [6]

Reference

1. Huffman, David A. (1952). A Method for the Construction of Minimum-Redundancy Codes. Proceedings of the IRE, 40. svezak, 9. izdanje, str. 1098–1101. (PDF)
2. Togneri R., deSilva Christopher J.S. (2003). Fundamentals of Information Theory and Coding Design, str. 137. Boca Raton, Florida: CRC Press. ISBN 978-0-203-99810.
3. Luenberger, David G. (2008). Information Science. New Jersey: Princeton University Press. ISBN 978-0-691-12418-3.
4. PKWARE (2012). .ZIP File Format Specification, sekcija 5.5, Deflating – Method 8. (TXT)
5. CCITT (1993). INFORMATION TECHNOLOGY – DIGITAL COMPRESSION AND CODING OF CONTINUOUS-TONE STILL IMAGES – REQUIREMENTS AND GUIDELINES, str. 50. (PDF)
6. ISO/IEC 11172-3 (1993). Coding of moving pictures and associated audio for digital storage media at up to about 1,5 Mbit/s – Part 3.

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Quisque rutrum ut magna eu euismod. Vivamus iaculis velit posuere est finibus, rutrum pretium libero elementum. Fusce ut metus quis nibh ultrices scelerisque et eu lacus. In tempus nisi vitae volutpat posuere. Cras non malesuada odio, a interdum nisi. Suspendisse iaculis neque ac erat hendrerit, quis tristique lorem vehicula. Donec ac hendrerit arcu, at iaculis enim. Pellentesque nibh quam, tristique eget tellus ac, molestie pellentesque leo. Sed egestas felis eu orci porta, et consectetur nulla molestie. Phasellus id odio a dolor dictum cursus ut id turpis. Ut cursus malesuada turpis. In ut pellentesque ipsum, id blandit nisi. Integer sed quam a enim condimentum condimentum. Nunc velit nibh, porta sit amet dapibus vitae, cursus at nunc.

Vivamus magna tellus, volutpat at tincidunt in, tristique id ligula. Quisque non ligula imperdiet, iaculis justo non, mattis eros. Nullam feugiat velit non consequat mollis. In posuere est lacus, ut tempus tellus egestas eu. Suspendisse potenti. Suspendisse sodales fringilla lorem, vitae commodo ligula lobortis quis. Sed mi sapien, ornare id sodales non, dignissim eu justo. Nam consectetur, est eu iaculis consectetur, nibh tortor pulvinar quam, et gravida orci elit vitae ante. Vestibulum ante ipsum primis in faucibus orci luctus et ultrices posuere cubilia curae; Cras ac turpis iaculis, venenatis ante aliquet, tempus elit. Cras sodales bibendum nulla a aliquet. Sed eget volutpat tellus. Nulla eget dictum enim, in mollis eros. Ut sagittis ut massa at ultricies. Integer dapibus in odio et fermentum.

Maecenas ipsum nisi, blandit id euismod at, ultrices in purus. Sed libero orci, viverra in eros scelerisque, aliquet lobortis nulla. Integer hendrerit ante at lorem tincidunt posuere. Suspendisse sed iaculis diam. Praesent sit amet quam nec nisl sollicitudin sollicitudin non vitae elit. Etiam hendrerit fringilla neque, eget vulputate odio. Sed in orci neque. Pellentesque dignissim magna a leo rutrum maximus. Fusce vel diam molestie ex lobortis sagittis. Sed mi massa, pharetra sed risus sed, porta varius diam. Quisque ac tincidunt lorem, id fermentum lorem. Cras fermentum auctor odio in varius. Nunc congue, arcu congue elementum varius, arcu eros pellentesque mi, ut lacinia ipsum urna ut mauris. Ut convallis vulputate eros porttitor rutrum. Nunc faucibus ac orci in cursus. Mauris nunc tellus, cursus eu luctus vel, fermentum non tortor.

Mauris viverra in sapien vitae convallis. Aliquam aliquam faucibus neque, a egestas elit consequat non. Pellentesque et leo vel sapien fermentum dapibus ut at risus. Phasellus feugiat ac ipsum sit amet faucibus. Morbi eu ultrices turpis, ac volutpat tortor. Donec vel facilisis turpis. Pellentesque vel metus a dolor mollis rhoncus. Nunc mollis nunc vitae ligula bibendum, eget scelerisque ligula hendrerit. Etiam congue a velit at pretium. Donec feugiat lectus scelerisque, congue massa a, posuere nisl. Quisque lectus elit, consequat non nunc at, interdum ullamcorper velit.

Mauris vitae facilisis leo. Nam dui lorem, sodales vitae magna ac, consectetur ullamcorper diam. Mauris tristique mauris ac ex ornare aliquet. Quisque ac pulvinar tortor. Nullam pellentesque venenatis nisi, quis mollis odio elementum in. Sed condimentum vulputate odio, sed dapibus arcu sagittis vel. Nulla dolor nisi, auctor ac lacinia vel, hendrerit vitae neque. Nullam sed rutrum erat, eget lobortis turpis. Quisque nec lobortis dolor. Proin id mollis mauris. Sed ornare enim ac mi sodales dictum. Nullam et ante varius, laoreet nisl eget, tristique nibh.