Huffmani kodeerimine

Huffman'i 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 bitt'i 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. Tulemusena saame informatsiooni kirjeldatud esinemistihedust eelistaval ja minimaalset tähemärkide hulka kasutaval alusel. Informatiooni kirjeldav andmehulk ei pruugi väheneda, eriolukorras võib ta isegi kasvada, kuid tegemist on tihendusalgoritmiga, mis tavateksti kokkupakkimisel saavutab märgatava erinevuse (tihti üle 30%'i).

Algoritmi implementeerimisest

Huffmani kodeerimisalgoritm põhineb konkreetse informatsiooni tähemärkide sageduse põhjal binaarpuu ehitamisel ja sellest tähemärkide bitijada kirjeldava kodeerimistabeli loomisel.

Kodeerimistabeli näide

Antud juhul on kodeerimistabeli informatsiooniks sõne "this is an example of a huffman tree".

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

Binaarpuu rakendamiseks kasutatav struktuur

{{{1}}}

//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 samat tüüpi struktuurile
	struct tree *right; //2 viide samat tüüpi struktuurile
} tree;

{{{1}}}

import java.util.Collection;

/**
 * tüüpiline klass Java's, mida kasutada objektipõhise binaarpuu ehitamisel
 */
public class tree implements Comparable<tree> {
    private tree left;
    private tree right;
    private int ch;
    private int freq;

    /**
     * tüüpiline konstruktor lehtede loomiseks
     * 
     * @param ch
     *            tähemärk
     * @param freq
     *            esinemise tihedus
     */
    public tree(int ch, int freq) {
        this.ch = ch;
        this.freq = freq;
    }

    /**
     * /** tüüpiline konstruktor varte loomiseks
     * 
     * @param left
     *            viide esimesele harule
     * @param right
     *            viide teisele harule
     * @param forest
     *            viide struktuurile, milles antud klasse hoitakse
     */
    public tree(tree left, tree right, Collection<tree> forest) {
        this.left = left;
        this.right = right;
        this.freq = left.freq + right.freq;

        forest.add(this);
        forest.remove(left);
        forest.remove(right);
    }

    /**
     * meetod klassi informatsiooni kuvamiseks
     */
    public String toString() {
        return "ch:" + this.ch + "\tfreq:" + this.ch;
    }

    public tree getLeft() {
        return this.left;
    }

    public void setLeft(tree left) {
        this.left = left;
    }

    public tree getRight() {
        return this.right;
    }

    public void setRight(tree right) {
        this.right = right;
    }

    public int getCh() {
        return this.ch;
    }

    public void setCh(int ch) {
        this.ch = ch;
    }

    public int getFreq() {
        return this.freq;
    }

    public void setFreq(int freq) {
        this.freq = freq;
    }

    /*
     * Meetod, mis võimaldab tree tüüpi elementide kollektsiooni sortimise
     * 
     * @see java.lang.Comparable#compareTo(java.lang.Object)
     */
    @Override
    public int compareTo(tree o) {
        try {
            if (o == null) return -1;

            return o.getFreq() - this.getFreq();
        } catch (Exception e) {
            return 0;
        }

    }
}

Puu ehitamisel kasutatakse mõisteid

• leht - struktuur, mille tähemärgi numbriline kood on määratud positiivselt, harud jäävad ühendamata (tal pole neid)
• vars - struktuur, mille tähemärgi numbriline kood on vaid algväärtustatud, struktuuri viited on määratud, esinemistihedus on temast otseselt järgnevalt harude varte/lehtede esinemistiheduse summa
• juur - struktuur, mille harusid pidi võib jõuda kõigi lehtedeni,

Puu ehitamise algoritm

1. Saadakse lehtede massiiv, milles on tähemärgid ja nende esinemise sagedused
2. Massiiv sorditakse esinemise sageduse alusel
3. Luuakse uus vars, mille harud ühendatakse 2 pisiksema esinemise sagedust omava elemendiga massiivis.
4. Massiivi lisatakse vars ja eemaldatakse elemendid, mis asetsevad tema harudes
5. Lisatud vars saab oma esinemise sageduseks tema harudes olevate elementide summa
6. Kui massiivis on järgi vaid 1 element, on puu valmis, kui mitte korratakse punkte alates 2'est

Kodeerimistabeli loomise rekursiivne algoritm

1. Saadake viit puu juurele
2. Kui tegemist on lehega, lisatakse loodud kood ja koodi pikkus kodeerimstabelisse
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 1'eks, 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 bitt'iga mille kogu kombinatsioonide hulk on 256.

Kodeerimistabeli element koosneb vormist ja pikkusest, ning kõik elemendid saavad pärast seda algoritmi määratud unikaalsete bitt'ijadadega.

Vaata ka

• Andmete pakkimine