Hofmanov i Grejov kôd
· Hofmanov
kôd
· Istorija
Hofmanovog kôda
· Grejov kôd
· Istorija
Grejovog kôda
Hofmanovo kôdiranje
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.
Danas taj kod ima veliku
primenu. U pitanju je optimalni binarni prefiksni kôd.
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.
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.
Kod Hafmanovog algoritma
kreiraju se simboli promenljive dužine koji zamenjuju ulazne simbole.
Što je verovatnoća pojavljivanja simbola veća,
utoliko je manji broj bita kojim se on reprezentuje. Za jedinstveno
identifikovanje simbola promenljive dužine se koriste jedinstveni
prefiksni atributi (biti).
Kodiranje/dekodiranje
simbola se u Huffman-ovoj tehnici vrši na osnovu Huffman-ovog
stabla. Simboli u stablu se nalaze organizovani prema verovatnoći
pojavljivanja. Simboli sa većom verovatnoćom se
nalaze bliže korenu stabla, dok se simboli sa najmanjom
verovatnoćom dalje.
Huffman-ovo stablo je
binarno stablo i gradi se od dna ka vrhu. Kreće se od
listova stabla i progresivno se gradi sve do korena. Algoritam za
generisnje stabla je jednostavan i elegantan. Prvo se formira niz
simbola u obliku listova koji će se povezati u binarno stablo.
Za svaki od simbola se vezuje težina koja opisuje njegovu verovatnoću
pojavljivanja (što je težina veća, to je veća i
verovatnoća).
Stablo se gradi kroz
sledeće korake:
1. Pronalaze se dva slobodna čvora
u nizu sa najmanjom vrednošću težina.
2. Kreira se nadređeni čvor za
pronađene čvorove. Dodaje mu se težina jednaka zbiru težina
njegovih podređenih čvorova.
3. Nadređeni čvor se dodaje u
niz slobodnih čvorova a podređeni čvorovi se izvlače
iz niza.
4. Putanji od nadređenog do jednog
od podređenih čvorova se dodeljuje vrednost 0, dok se
putanji do drugog čvora dodeljuje vrednost 1.
5. Prethodni koraci se ponavljaju sve
dok u nizu slobodnih čvorova ne preostane samo jedan. Poslednji
čvor je koren Huffman-ovog binarnog stabla.
Povodom osobine
optimalnosti,važno je istaći i 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 pojave svakog karaktera
eksterne azbuke. Ako verovatnoća pojave svakog simbola ima
uniformnu distribuciju, a broj simbola je stepen dvojke, Hofmanovo
kodiranje je kodiranje binarnim blokovima(ASCII,…).
Najgori slučaj
za Hofmanovo kodiranje, tj. najduži Hofmanov kôd dobija se u
situaciji kada distribucija frekvenci simbola se odvija po pravilu
generisanja Fibonačijevih brojeva.
Varijacije Hofmanovog
kodiranja
Adaptivno
Hofmanovo kodiranje
Ova varijanta
izračunava frekvencije objekata dinamički tokom
pregleda tekućeg dokumenta. Radise o jednoprolaznom algoritmu
korisnom za realtime aplikacije. Ova varijanta Hofmanovog kodiranja
je kasnije upotrebljena 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.
Zadatak
1. Optimalnim binarnim prefiksnim kôdom kôdirati
rečenicu: NA VRH BRDA VRBA MRDA
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 >= [log2 #S] +1 = [log29] +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 fi 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
fH=1,
fM=1
Sa hipa se skidaju M, H i zamenjuju
u hipu sa MH, gde
fMH = fH
+ fM = 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
kojidesni, jer su stabla međusobno izomorfna do na permutaciju)
4.
korak
fN=1,
fMH=2
Sa hipa se skidaju MH, N i zamenjuju u hipu sa MHN, gde
fMHN
= fMH + fN = 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 kojidesni, 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
|
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:
f1*l1 + . . . +
f9*l9= 2*4 + . . . + 5*1 = 64
ZADACI ZA VEZBU:
Zadatak 1.
Optimalnim binarnim prefiksnim kôdom kôdirati rečenicu:
RIBA RIBI GRIZE REP
Zadatak
2. Optimalnim binarnim prefiksnim kôdom kôdirati
rečenicu: PO JUTRU SE DAN POZNAJE
Zadatak
3. Optimalnim binarnim prefiksnim kôdom kôdirati
rečenicu: BEZ MUKE NEMA NAUKE
Zadatak
4. Optimalnim binarnim prefiksnim kôdom kôdirati
rečenicu: BEZ ALATA NEMA ZANATA
Zadatak
5: Ako je data tabela simbola sa frekvencijama
simbol
|
A
|
B
|
R
|
C
|
fi
|
8
|
6
|
4
|
3
|
konstruisite Hafmanovo stablo,
odredite Hafmanov kôd,
kodirajte nisku BARCAR, dekodirajte nisku 10011110
Zadatak
6: Dokazite ili opovrgnite tvrđenje: U bilo kom binarnom stablu,
kôdovi
putanje za listove u stablu su prefiksni
kôdovi.
Grejov kôd(Frank
Grey)
Grejov
kôd dužine n>1 je niz
k-torki bita (k>=1) b1, b2,...bn takvih
da se unizu 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 nacifru 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 b1,bi se razlikuju na
parnom (neparnom) broju pozicija ako i je neparno(parno). Ako
bi dužina koda n bila neparna, onda bi se b1,bn
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] ;
Ekvivalent u programskom jeziku C:
unsigned int grejEnkod(unsigned int g) {
return(g^g>>1);
}
Algoritam
u pseudokodu za konverziju Gray
koda u binarnu reprezentacijedekadnih 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
zataj rad dobio francusku Legiju časti.
1953. je Frank Gray iz Belll Labs
istraživačkog centra patentirao vakumsku cev koja
koristi Gray enkodiranjei 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 primenaje 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 jeBeckett-Gray kod nazvanog po
engleskom piscu Semjuelu Beketu. Sam Beket je kao režiser
ekstremno poštovao principesimetrije 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 dakomad 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 moglida 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
neBeckett-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.
ZADACI
ZA VEZBU:
Zadatak
1: Konstruisite 5-bitni Grejov kôd.
Zadatak
2. Neka
su A i B kvadratne matrice reda n cije
su vrste otvoreni Grejovi kodovi (elementi
su im iz skupa {0, 1}, a svake dve
uzastopne vrste razlikuju se na tacno jednom mestu).
Konstruisati algoritam slozenosti O(n2)
za mnozenje ovakvih matrica.