Huffman Kodlaması

Açgözlü Algoritmalar O(n log n) O(n)

Optimal önek kodu kurar: en düşük frekanslı iki ağacı tekrar tekrar birleştirir, sonra kodları kök-yaprak yollarından okur.

Metin

1/20

Her karakter için birer yapraklı 5 ağaçla başlanıyor.

DeğişmezEn hafif iki ağacı birleştirmek en nadir sembolleri en derine koyar, böylece uzun kodları en az maliyetli olur.

seçilen (iki en küçük)birleştirildikod üretildi

huffman-coding.c

typedef struct Node {
    char ch;
    int freq;
    struct Node *left, *right;
} Node;
 
Node *buildHuffman(Node *forest[], int n) {
    while (n > 1) {
        int a = minIndex(forest, n, -1);
        int b = minIndex(forest, n, a);
        Node *m = newNode(forest[a]->freq
                        + forest[b]->freq);
        m->left  = forest[a];
        m->right = forest[b];
        forest[a] = m;               /* replace one    */
        forest[b] = forest[--n];     /* drop the other */
    }
    return forest[0];
}
 
void printCodes(Node *t, char buf[], int d) {
    if (!t->left && !t->right) {
        buf[d] = '\0';
        printf("%c: %s\n", t->ch, buf);
        return;
    }
    buf[d] = '0'; printCodes(t->left,  buf, d + 1);
    buf[d] = '1'; printCodes(t->right, buf, d + 1);
}

Huffman Kodlaması nasıl çalışır?

En nadir iki simgeyi tek düğüm altında birleştir, çifti tek simge say ve tekrarla. Nadir simgeler derine (uzun kod), sık olanlar yüzeye (kısa kod) düşer; ağaç yolları önek-siz kodlar verir.

Ne zaman kullanılır?

Sıkıştırmada entropi kodlama: DEFLATE/zip, JPEG, MP3 hep Huffman aşaması içerir.