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 >= [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:

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:

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
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:

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):

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

Dakle,tablica kôdova glasi:

Broj bitova za rečenicu je:
f₁*l₁ + . . . + f₉*l₉= 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

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.

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

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);

 }

 B[n]=G[n];

 for (i=n-1; i>=0; i--) {

 B[i]=B[i+1] ^ G[i];

 }

unsigned int grejDekod(unsigned int b) {

 b^=b>>1;

 b^=b>>2;

 b^=b>>4;

 b^=b>>8;

 return(b^(b>>16));

 }