Huffmani kodeerimine

Allikas: Vikipeedia
Jump to navigation Jump to search
Huffmani puu, mis on genereeritud järgnevast tekstist jutumärkides: "this is an example of a huffman tree". Lehtede puhul on kuvatud esinemissagedus ja tähemärk, varte puhul vaid esinemistihedus. Kodeeritud teksti kogumaht oleks 135 bitti ehk vähem kui 17 tähemärki, arvestamata puu kirjeldamiseks vajaliku ruumi. Algne teksti pikkus 36 tähemärki

Huffmani kodeerimine on prefikskoodide üks liik. Huffmani kodeerimise idee on asendada olemasolev sümboleid kirjeldav bitijada ümber nõnda, et informatsiooni hulgas tihemini esinevad tähemärgid saaksid kirjeldatud lühema bitijadaga. Tulemuseks on informatsiooni kirjeldus esinemistihedust eelistaval ja minimaalset tähemärkide hulka kasutaval alusel. Informatsiooni kirjeldav andmehulk ei pruugi väheneda ja võib eriolukorras isegi kasvada, kuid tegemist on tihendusalgoritmiga, mis tavateksti kokkupakkimisel saavutab märgatava erinevuse (tihti üle 30%).

Algoritmi rakendamisest[muuda | muuda lähteteksti]

Huffmani kodeerimisalgoritm põhineb konkreetse informatsiooni tähemärkide sageduse põhjal binaarpuu ehitamisel ja sellest tähemärkide bitijada kirjeldava kodeerimistabeli loomisel. Faili tihendamise puhul kirjutatakse väljundfaili puu kirjeldus ja algse sisendfaili sisu, kus tähemärgid on asendatud uue kodeeringuga.

Otsese informatsiooni sisaldava faili tihendamisel on mõned lahendamist vajavad kitsaskohad. Näiteks tuleb teostada väljundfaili lõpu tuvastus, sest tõenäolisel ei lõpe fail baidi pealt, vaid selles on mõnebitine ülejääk.

Binaarpuu rakendamiseks kasutatav struktuur[muuda | muuda lähteteksti]

//tüüpiline struktuur programmeerimskeeles C, mida kasutada binaarpuu ehitamisel
typedef struct tree {
	int ch; //tähemärgi numbriline kood
	int freq; //informatsioonis esinemise tihedus
	struct tree *left; //viide sama tüüpi struktuurile
	struct tree *right; //2 viide sama tüüpi struktuurile
} tree;

Puu ehitamisel kasutatavad mõisteid[muuda | muuda lähteteksti]

  • leht – element, mille tähemärgi numbriline kood on määratud positiivselt, harud jäävad ühendamata (tal pole neid);
  • vars – element, mille tähemärgi numbriline kood on vaid algväärtustatud, harud on väärtustatud, esinemistihedus on varre harudes olevate elementide esinemistiheduse summa;
  • juur – element, mille harusid pidi võib jõuda kõigi lehtedeni;
  • haru – elemendi viide sama tüüpi elemendile.

Puu ehitamise algoritm[muuda | muuda lähteteksti]

  1. Luuakse lehtede massiiv, milles on tähemärgid ja nende esinemissagedused;
  2. Massiiv sorditakse esinemise sageduse alusel;
  3. Luuakse uus vars, mille harud ühendatakse kahe väiksema esinemise sagedusega elemendiga massiivis;
  4. Massiivi lisatakse vars ja eemaldatakse selle harudes asetsevad elemendid;
  5. Lisatud varre esinemissageduseks määratakse selle harudes olevate elementide summa;
  6. Kui massiivis on järgi vaid üks element, on puu valmis, kui mitte, korratakse algoritmi alates punktist 2.

Kodeerimistabeli loomise rekursiivne algoritm[muuda | muuda lähteteksti]

  1. Saadakse viit puu juurele;
  2. Kui tegemist on lehega, lisatakse kodeerimstabelisse loodud kood ja koodi pikkus;
  3. Kui varrel on vasakpoolne (esimene) haru olemas, suurendatakse koodi pikkust ja pöördutakse punkti 1;
  4. Kui varrel on parempoolne (teine) haru olemas, määratakse koodi viimane bitt 1ks, suurendatakse koodi pikkust ja pöördutakse punkti 1.

Tõenäoliselt pole raske iteratiivset algoritmi luua, kuid selle vajadus on olematu, sest tähed on üldjuhul kirjeldatud 8 bitiga, mille kõigi kombinatsioonide hulk on 256.

Kodeerimistabeli näide[muuda | muuda lähteteksti]

Kodeerimistabeli element koosneb vormist ja pikkusest, ning kõik elemendid saavad pärast seda algoritmi määratud unikaalsete bitijadadega. Järgneval on toodud infokuvang eelneva ja uue kodeeringu erinevustest, kodeerimistabeli informatsiooniks on sõne "this is an example of a huffman tree", mille kohta eelneval oli juba samaväärne puu näide toodud.

Kodeerimistabel:
 Tähemärk ' ' nr(32)	| binaarkood:00100000 | uus binaarkood:111
 Tähemärk 'a' nr(97)	| binaarkood:01100001 | uus binaarkood:001
 Tähemärk 'e' nr(101)	| binaarkood:01100101 | uus binaarkood:000
 Tähemärk 'f' nr(102)	| binaarkood:01100110 | uus binaarkood:1101
 Tähemärk 'h' nr(104)	| binaarkood:01101000 | uus binaarkood:1100
 Tähemärk 'i' nr(105)	| binaarkood:01101001 | uus binaarkood:1001
 Tähemärk 'l' nr(108)	| binaarkood:01101100 | uus binaarkood:01101
 Tähemärk 'm' nr(109)	| binaarkood:01101101 | uus binaarkood:1000
 Tähemärk 'n' nr(110)	| binaarkood:01101110 | uus binaarkood:1011
 Tähemärk 'o' nr(111)	| binaarkood:01101111 | uus binaarkood:01100
 Tähemärk 'p' nr(112)	| binaarkood:01110000 | uus binaarkood:01111
 Tähemärk 'r' nr(114)	| binaarkood:01110010 | uus binaarkood:01110
 Tähemärk 's' nr(115)	| binaarkood:01110011 | uus binaarkood:1010
 Tähemärk 't' nr(116)	| binaarkood:01110100 | uus binaarkood:0101
 Tähemärk 'u' nr(117)	| binaarkood:01110101 | uus binaarkood:01001
 Tähemärk 'x' nr(120)	| binaarkood:01111000 | uus binaarkood:01000

Vaata ka[muuda | muuda lähteteksti]

Välislingid[muuda | muuda lähteteksti]