Huffman Coding (ฮัฟแมนโค้ดดิ้ง): อัลกอริทึมบีบอัดข้อมูลไร้การสูญเสีย

Huffman Coding เป็นอัลกอริทึมบีบอัดข้อมูลแบบ Lossless กำหนด Variable-length Code ให้ตัวอักษร ความยาว Code เกี่ยวกับความถี่ (Frequency) ตัวอักษรที่พบบ่อยมี Code สั้น ตัวอักษรที่พบน้อยมี Code ยาว

มี 2 ส่วนหลัก: 1) สร้าง Huffman Tree 2) ท่อง Tree เพื่อหา Code

ตัวอย่าง: สตริง "YYYZXXYYX" Y พบมากที่สุด → Code สุดสั้น Z พบน้อยสุด → Code สุดยาว

• Complexity การกำหนด Code ตามความถี่: O(n log n)

Input: สตริง "ACCEBFFFFAAXXBLKE"
Output: Code สำหรับแต่ละตัวอักษร:

Data: K, Frequency: 1, Code: 0000
Data: L, Frequency: 1, Code: 0001
Data: E, Frequency: 2, Code: 001
Data: F, Frequency: 4, Code: 01
Data: B, Frequency: 2, Code: 100
Data: C, Frequency: 2, Code: 101
Data: X, Frequency: 2, Code: 110
Data: A, Frequency: 3, Code: 111

Algorithm

huffmanCoding(string)

Input: สตริงที่มีตัวอักษรต่างๆ
Output: Code สำหรับแต่ละตัวอักษร

Begin
    define node with char, frequency, left/right child for Huffman tree
    create list 'freq' store frequency of each char, initially 0
    for each char c in string do
        increase frequency for ch in freq list
    done
    for all char types ch do
        if frequency non-zero add ch and freq as node to priority queue Q
    done
    while Q not empty do
        remove item from Q assign to left child
        remove item from Q assign to right child
        traverse node to find assigned code
    done
End

traverseNode(n: node, code)

Input: โหนด n ของ Huffman Tree, Code จากการเรียกก่อนหน้า
Output: Code ที่กำหนดกับแต่ละตัวอักษร

if left child of n ≠ ∅ then
    traverseNode(leftChild(n), code+'0')
    traverseNode(rightChild(n), code+'1')
else
    display character and data of current node

ตัวอย่างโค้ด (C++)

#include <iostream>
#include <queue>
#include <string>
using namespace std;

struct node {
    int freq;
    char data;
    const node *child0, *child1;
    node(char d, int f = -1) {
        data = d; freq = f; child0 = NULL; child1 = NULL;
    }
    node(const node *c0, const node *c1) {
        data = 0; freq = c0->freq + c1->freq; child0=c0; child1=c1;
    }
    bool operator<(const node &a) const {
        return freq > a.freq; // min-heap by frequency
    }
    void traverse(string code = "") const {
        if(child0!=NULL) {
            child0->traverse(code+'0');
            child1->traverse(code+'1');
        } else {
            cout << "Data: " << data << ", Frequency: " << freq << ", Code: " << code << endl;
        }
    }
};

void huffmanCoding(string str) {
    priority_queue qu;
    int frequency[256] = {0};
    for(int i = 0; i < str.size(); i++)
        frequency[int(str[i])]++;
    for(int i = 0; i < 256; i++)
        if(frequency[i])
            qu.push(node(i, frequency[i]));
    while(qu.size() > 1) {
        node *c0 = new node(qu.top()); qu.pop();
        node *c1 = new node(qu.top()); qu.pop();
        qu.push(node(c0, c1));
    }
    cout << "The Huffman Code: " << endl;
    qu.top().traverse();
}

main() {
    string str = "ACCEBFFFFAAXXBLKE";
    huffmanCoding(str);
}

Output

The Huffman Code:
Data: K, Frequency: 1, Code: 0000
Data: L, Frequency: 1, Code: 0001
Data: E, Frequency: 2, Code: 001
Data: F, Frequency: 4, Code: 01
Data: B, Frequency: 2, Code: 100
Data: C, Frequency: 2, Code: 101
Data: X, Frequency: 2, Code: 110
Data: A, Frequency: 3, Code: 111