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

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.²
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.³

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

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. ↩︎

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.