26: Huffmanovo kodiranje

Avtor: Boštjan Jaklič (bostjan.jaklic@siol.net)
Visokošolski strokovni študij Praktična matematika
Študijsko leto 2004/05
 

Viri:

[1] fotokopije iz treh knjig - študijski material

[2] David A. Huffman, A method for the Construction of Minimum-Redundancy Codes, Proceedings of the I.R.E., September 1952; http://compression.graphicon.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes.pdf

[3] Debra A. Lelewer, Daniel S. Hirschberg, Data compression, internetna referenca http://www.ics.uci.edu/~dan/pubs/DataCompression.html

[4] Mark Nelson & Visicron Corp, Huffman Coding, internetni seznam povezav/referenc za Huffmanovo kodiranje http://datacompression.info/Huffman.shtml

[5] Kenneth D. Huffman, Huffman Coding, 1997-2005, http://www.huffmancoding.com/david/algorithm.html

[6] William A. McKee, Huffmanovo kodiranje v C++

 

Tekstovne datoteke lahko stisnemo tako, da zamenjamo pogosto ponavljajoče se besede s krajšimi simboli. Eden izmed načinov takega kodiranja je Huffmanovo kodiranje. Huffmanovo kodiranje je dobilo ime po Davidu Huffmanu, ki je leta 1952 objavil članek [2], v katerem je opisal metodo.

Koda se nahaja tukaj in je zapisana v eni sami datoteki.

Pri implementaciji algoritma sem zgradil naslednje pomožne razrede/strukture:

Razred Znak sem uporabil za opis znaka:

• simbol vsebuje znak/simbol v Unicode abecedi
• teza poda frekvenco znaka v danem besedilu deljeno s številom vseh znakov 
• koda sem pa shranimo dvojisko kodo znaka (pravzaprav niz, sestaljen iz 0 in 1)

Vozlisce je s povezavama na sinova razsirjen Znak in predstavlja vozlisce v drevesu:

• simbol vsebuje znak/simbol v Unicode abecedi
• teza poda frekvenco znaka v danem besedilu deljeno s številom vseh znakov 
• koda sem pa shranimo dvojisko kodo znaka (pravzaprav niz, sestaljen iz 0 in 1)
• levi kazalec na levega sina
• desni kazalec na desnega sina 

Drevo je povezan seznam Vozlisc in tvori dvojiško drevo:

• vozlHuff koren dvojiškega drevesa
• nasl rekurzivni kazalec na dvojiško (pod)drevo

Za gradnjo Huffmanovega drevesa sem uporabil vrsto s prednostjo VrstaPrednost:

• seznam je kazalec na seznam vozlišč v vrsti

Uporabljene metode:

• public void vstavi(Vozlice vzl) v vrsto vstavi novo vozlišče
• public void sestaviSeznam(Znak[] znaki, int n) iz n znakov podanih v tabeli znaki sestavi seznam
• public Vozlisce najmanjseVozlisce() v vrsti poišče vozlišče z najmanjšo težo

Razred Abeceda iz prebranih podatkov zgradi tabelo vseh nastopajočih znakov

• dolzinaTabele je trenutna dolžina tabele, ki jo gradimo
• znaki je tabela znakov
• vhod vhod s katerega beremo podatke
• datoteka je niz, v katerega beremo znake z vhoda - potem "obdelujemo" ta niz
• imeDat je ime (morebitne) vhodne datoteke
• stZnakov je število prebranih znakov
• strazar = 'Ö' je stražar za konec datoteke (pri dekodiranju) - ne sme se pojaviti v naših abecedi...

Metode v razredu Abeceda:

• public char preberiZnak() vrne naslednji prebrani znak iz vhoda
• public String izpisiZnak(Character znak) vrne niz, ki predstavlja znak; pri posebnih/kontrolnih znakih v nizu vrne šestnajstiško kodo znaka
• public int kjeJe(char ch) poisce, kje se nahaja iskani znak; če ga ne najde vrne -1
• public void zgradiAbc() prebere znak po znak (do ctrlZ (Win) ali ctrlD (Unix) oz. do stražarja) in zgradi abecedo
• public void izpisiAbc() izpiše vsebino abecede

Glavni razred je Huffman. Glavno vlogo igra konstruktor:

public Huffman(String imeDat) {
    abc = new Abeceda(imeDat); // preberemo in
    abc.zgradiAbc(); // zgradimo abecedo
    vp = new VrstaPrednost();
    vp.sestaviSeznam(abc.znaki, abc.dolzinaTabele); // sestavimo vrsto s prednostjo

    // zgradimo Huffmanovo drevo
    Vozlisce drevo = null;
    for (int i = 0; i < abc.dolzinaTabele-1; i++) { // za vse znake iz abecede
        drevo = new Vozlisce();
        drevo.levi = vp.najmanjseVozlisce(); // prvo najmanjse vozlisce
        drevo.desni = vp.najmanjseVozlisce(); // naslednje najmanjse vozlisce
        drevo.teza = drevo.levi.teza + drevo.desni.teza; // teza oceta je vsota tez sinov
        drevo.simbol = strazar; // v vozlisce, ki ni list za vsak slucaj postavimo strazarja
                                // seveda tega znaka ne smemo uporabiti v podatkih!
        drevo.koda = "";
        vp.vstavi(drevo); // v vrsto s prednostjo vstavimo drevesce
    } // drevo je zgrajeno
    // zdaj lahko v drevo zapisemo dvojiske kode
    dodajKodo(drevo, abc.znaki, abc.dolzinaTabele, "");
 

Metode:

• public void dodajKodo(Vozlisce drevo, Znak znaki[], int n, String geslo) s pomočjo rekurzije v liste v drevesu vpiše dvojiško kodo.
• public String stisni(String podatki) stisne podatke, ki jih imamo shranjene v nizu podatki
• public String povrni(String podatki) povrne podatke v prvotno obliko

Primer uporabe algoritma je sestavni del kode, ki se nahaja tukaj.

Program predstavi stiskanje podatkov tako, da dano besedilo "stisne" v dvojiški zapis. V tem zapisu so ničle in enke "standardni" znaki. Če bi želeli v resnici stisniti podatke, bi morali "dvojiški" zapis pretvoriti v bite.

 

Program lahko pokličemo z argumentom, ki je ime datoteke, ki jo želimo stisniti. V primeru, da datoteke ne moremo odpreti/prebrati, program vrne napako.

Če program pokličemo brez argumenta, začnemo brati iz standardnega vhoda. Vnos zaključimo s Ctrl Z (Windows) oziroma Ctrl D (Unix), pred tem pa moramo pritisniti Return, da program lahko prebere tudi zadnjo vrstico besedila (sicer je ne more prebrati).

Primeri uporabe:

C:\Seminar2\java Huffman testna.txt

in

C:\Seminar2\java Huffman

in nato vnesemo npr.:

abcdefgaaaaaaaaggggg     aaaa bbbbbbbbbbbb

ctrl Z

Zatem se izpišejo rezultati.