Hofmanov i Grejov kôd

· Hofmanov kôd

· Istorija Hofmanovog kôda

· Grejov kôd

· Istorija Grejovog kôda 

Hofmanovo kôdiranje

1. Optimalnim binarnim prefiksnim kôdom kôdirati rečenicu: NA VRH BRDA VRBA MRDA

Reči binarnog koda su nizovi bitova (ne obavezno fiksne dužine).

Reči prefiksnog koda imaju svojstvo da niti jedna reč nije prefiks druge. Ako je neki kompresioni kod prefiksni, ta osobina je značajna zbog postupka dekompresije.

Huffman kodiranje je algoritam entropijskog kodiranja koji se koristi za kompresiju podataka koji pronalazi optimalni sistem kodiranja objekata zasnovan na relativnoj frekvenciji pojave svakog objekta u kolekciji.

Algoritam je 1953. razvio (tada postdiplomac na MIT) David A. Huffman(1925-1999) i objavio u radu A Method for the Construction of Minimum-Redundancy Codes.

Povodom osobine optimalnosti, važno je istaćii da je pokazano da Hofmanovo kodiranje je najefikasniji kompresioni metod u svojoj klasi, a to je klasa preslikavanja karaktera eksterne azbuke neke tekstualne kolekcije u bitove za poznatu frekvenciju pojavu svakog karaktera eksterne azbuke. Ako verovatnoća pojave svakog simbola ima uniformnu distribuciju, a broj simbola je stepen dvojke Hofmanovo kodiranje kodiranje binarnim blokovima (ASCII,…).

Najgori slučaj za Hofmanovo kodiranje, tj. najduži Hofmanov kod dobija se u situaciji kada distribucija frekvenci simbola se odvija po poravilu generisanja Fibonačijevih brojeva.

Varijacije Hofmanovog kodiranja

Adaptivno Hofmanovo kodiranje

Ova varijanta izračunava frekvencije objekata dinamički tokom pregleda tekućeg dokumenta. Radi se o jednoprolaznom algoritmu korisnom za realtime aplikacije. Ova varijanta Hofmanovog kodiranja je kasnije upotrebljeno u familiji Lempel-Ziv algoritama.

n-arno Hofman kodiranje

n-arno Hofman algoritmi koristi {0, 1, ..., n − 1} alfabet za kodiranje objekata i izgradnju n-arnog stabla.

Hofmanovo kodiranje danas se često koristi kao "back-end" faza za druge kompresione metode kao na primer PKZIP algoritam DEFLATE. JPEG i MP3 algoritmi imaju front-end prolaz i kvantizaciju koju prati Hofmanovo kodiranje.

Skup karaktera S={N, A, , V, R, H, B, D, M}

Ako kôdiramo ravnomernim kôdom, onda je dužina binarne reči kôda svakog karaktera bar 4 bita (ako #S %2 != 0 => dužina binarne reči je >= [log₂ #S] +1 = [log₂ 9] +1)
Za rečenicu sa 21 karakterom je potrebno 4*21 = 84 bita
Upotrebom tradicionalnih 7-bitnih/8-bitnih kôdova, dužina je:

7*21 = 147 bitova

8*21 = 168 bitova

Ali, Hofmanovim kôdiranjem će se dobiti optimalna dužina: (pogledati poglavlje 5.5 o kompresiji podataka u knjizi M. Živković "Algoritmika")

Neka je f_i broj pojava karaktera i u rečenici. Tada je:

	A	blanko	R	B	V	D	N	M	H
fi	4	4	4	2	2	2	1	1	1

1. korak - ubacivanje karaktera u hip prema frekvencijama pojavljivanja

2. korak
f_H=1,
f_M=1
Sa hipa se skidaju M, H i zamenjuju u hipu sa MH, gde
f_MH = f_H + f_M = 2

Otuda, tablica glasi:

	A	blanko	R	B	V	D	N	MH
fi	4	4	4	2	2	2	1	2

3. korak = formiranje segemenata stabla
MH je otac čija dva sina su M, H (bez obzira koji sin je levi, a koji desni, jer su stabla međusobno izomorfna do na permutaciju)

4. korak
f_N=1,
f_MH=2
Sa hipa se skidaju MH, N i zamenjuju u hipu sa MHN, gde
f_MHN = f_MH + f_N = 3

Otuda, tablica glasi:

	A	blanko	R	B	V	D	MHN
fi	4	4	4	2	2	2	3

5. korak
MHN je otac čija dva sina su MH, N (bez obzira koji sin je levi, a koji desni, jer su stabla međusobno izomorfna do na permutaciju)

Daljim preuređivanjem hipa, dobijaju se redom tablice ( i segmenti drveta redom):

	A	blanko	R	B	VD	MHN
fi	4	4	4	2	4	3

	A	blanko	R	BMHN	VD
fi	4	4	4	5	4

	A	R	BMHN	VDblanko
fi	4	4	5	8

	AR	BMHN	VDblanko
fi	8	5	8

	AR	BMHNVDblanko
fi	8	13

	ARBMHNVDblanko
fi	21

Ako hip ostane samo sa jednim članom, taj član je koren kôdnog stabla Hofmanovog kôda.

Dakle, tablica kôdova glasi:

karakter	A	R	B	blanko	V	D	N	M	H
kôd	00	01	100	111	1100	1101	1011	10100	10101

Broj bitova za rečenicu je:
f₁*l₁ + . . . + f₉*l₉ = 2*4 + . . . + 5*1 = 64

Hofmanov algoritam i kompresija slika

Grejov kôd (Frank Grey)

Grejov  kôd dužine n>1 je niz k-torki bita (k>=1) b1, b2,...b_n takvih da se u nizu b svaka dva uzastopna člana, kao i prvi i poslednji član razlikuju na tačno jednoj poziciji. Na primer, Grejov  kôd dužine 4 je 00, 01, 11, 10.

Grejov  kôd se koristi i kao ciklički kôd sa za kodiranje dekadnih cifara binarnim rečima sa svojstvom da pri prelasku sa dekadne cifre i na cifru i+1 u kodnoj reči se menja samo binarna cifra na jednoj poziciji. Ovo svojstvo ga čini pogodnim za primene u kontroli pozicija rotirajućih elemenata, na primer kod nekih štampača, mehaničkih dekodera, ...

Na primer Grejov kod za k=3, n=8

0 000
1 001
2 011
3 010
4 110
5 111
6 101
7 100

Izgradnja Grej koda sa k bita na osnovu k-1 bitnog Grej koda – prefiksovanjem najpre sa k nula, a potom sa k jedinica

G1. Da li postoji Grejov  kôd neparne dužine?

O1. Ne postoji, jer za i>1 b₁, b_i se razlikuju na parnom (neparnom) broju pozicija ako i je neparno(parno). Ako bi dužina koda n bila neparna, onda bi se b₁, b_n razlikovali na parnom broju pozicija, što je kontradikcija sa svojstvom da se oni razlikuju na jednoj poziciji.

G2. Algoritmi konverzije

Algoritam u pseudokodu za konverziju binarne reprezentacije dekadnih cifri u Grejov kod (enkodiranje):

 Neka B[n:0] je niz bitova u uobičajenoj binarnoj reprezentaciji 
 Neka G[n:0] je niz bitova u Grejovom kodu
 G[n]=B[n];
 for (i=n-1; i>=0; i--) {
 G[i]=B[i+1] ^ B[i] ; /* ^ za XOR */
 
 Ekvivalent u programskom jeziku C:
 unsigned int grejEnkod(unsigned int g) {
 return(g^g>>1);
 }

Algoritam u pseudokodu za konverziju Gray koda u binarnu reprezentacije dekadnih cifri (dekodiranje):

 B[n]=G[n];
 for (i=n-1; i>=0; i--) {
 B[i]=B[i+1] ^ G[i];
 }

Ekvivalent u programskom jeziku C:

 unsigned int grejDekod(unsigned int b) {
 b^=b>>1;
 b^=b>>2;
 b^=b>>4;
 b^=b>>8;
 return(b^(b>>16));
 }

Istorija i primene

Gray kodovi (dok još nisu tako imenovani) najpre su se koristili u matematičkim mozgaliciama, a tek potom su postali sredstvo koje su koristili inžinjeri u svojim primenama. Francuski inžinjer Émile Baudot je 1878 upotrebio Grejove kodove u telegrafiji i za taj rad dobio francusku Legiju časti.

1953. je Frank Gray iz Belll Labs istraživačkog centra patentirao vakumsku cev koja koristi Gray enkodiranje i stoga su ovi kodovi nazvani po njemu.

Hemingovo rastojanje Grejovih kodova čini ih pogodnim za upotrebu u evolucionom izračunavanju i genetskim algoritmima, kao i u rešenju problema Hanojskih kula. Ta interesantna primena je detaljnije objašnjena u članku čiji URL je http://occawlonline.pearsoned.com/bookbind/pubbooks/miller2_awl/chapter4/essay1/deluxe-content.html#tower

Čekajući Godoa: Beckett-Gray kod

Interesantna primena Grejovog koda je Beckett-Gray kod nazvanog po engleskom piscu Semjuelu Beketu. Sam Beket je kao režiser ekstremno poštovao principe simetrije na sceni u smislu da mu je bilo važan broj glumaca na i van scene. Jedan od njegovih komada "Blok" se odigrava u 16 vremenskih perioda. Na kraju svakog perioda, Beket je želeo da jedan od četvoro glumaca ili uđe na ili iziđe sa scene i da komad započne i završi se sa praznom pozornicom. Insistirao je i da svaka grupa glumaca se pojavi u zajedničkoj sceni najviše jednom. Matematički formulisano, to znači da glumci na pozornici se mogu predstaviti 4-bit binarnim Grejovim kodom. Dodatno ograničenje Beketovog scenarija je bilo i da glumci izlaze na i odlaze sa pozornice tako da odlazi sa scene onaj glumac koji je najduže boravio na pozornici. Dakle, glumci bi mogli da se reprezentuje FIFO strukturom reda čekanja, tako da prvi izlazni glumac bude onaj koji je i prvi ušao u red čekanja. Inače, matematičimarima nije bilo jednostavno pokazati da li postoji ili ne Beckett-Gray kod za n = 4, već je iscrpnom pretragom prostora rešenja utvrđeno da takav kod ner postoji, tj. Beket nije mogao ostvariti pređašnju zamisao, ali sa drugim brojem glumaca, moguće je. Jer za n = {2, 5, 6} postoji SB kod, ali ne postoji za n = {3, 4}. Interesantno je da prostor za pretragu rešenja za n = 6 je veliki i još nije kompletno okončana diskusija svih postojećih rešenja, već<je poznatao nekoliko hiljada SB kodova za n = 6.

Jelena Grmuša

Primene računara

---