Huffman Coding Algorithm (อัลกอริทึมฮัฟแมน)

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

หลักการทำงาน

1. นับความถี่ (Frequency) ของแต่ละตัวอักษร
2. สร้าง Huffman Tree โดยใช้ Priority Queue (Min-Heap)
3. เดินทาง (Traverse) ต้นไม้: ซ้าย = 0, ขวา = 1
4. รหัสของแต่ละตัวอักษร = เส้นทางจากรูทถึงใบ

ตัวอย่าง

Input: "ACCEBFFFFAAXXBLKE"

Frequency:  A:3, B:2, C:2, E:2, F:4, K:1, L:1, X:2

Codes:
F: 01       (บ่อยที่สุด -> สั้นที่สุด)
A: 111
B: 100      C: 101      E: 001      X: 110
K: 0000     L: 0001     (น้อยที่สุด -> ยาวที่สุด)

ความซับซ้อน (Complexity)

• Time: O(n log n) - เนื่องจาก Priority Queue operations
• Space: O(n) - เก็บต้นไม้และรหัส

อัลกอริทึม (Pseudocode)

huffmanCoding(string)
  freq[256] = {0}
  for each char c in string:
    freq[c]++

  PriorityQueue Q (min-heap by freq)
  for each char with freq > 0:
    Q.push(Node(char, freq))

  while Q.size() > 1:
    left = Q.pop()
    right = Q.pop()
    parent = Node('\0', left.freq + right.freq)
    parent.left = left; parent.right = right
    Q.push(parent)

  root = Q.pop()
  traverse(root, "")

traverse(node, code)
  if node.left:
    traverse(node.left, code + "0")
    traverse(node.right, code + "1")
  else:
    print node.char + ": " + code

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

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

struct Node {
    char data;
    int freq;
    Node *left, *right;
    Node(char d, int f) : data(d), freq(f), left(nullptr), right(nullptr) {}
    Node(Node* l, Node* r) : data('\0'), freq(l->freq + r->freq), left(l), right(r) {}
    bool operator<(const Node& other) const { return freq > other.freq; } // min-heap
};

void traverse(Node* node, string code) {
    if (node->left) {
        traverse(node->left, code + "0");
        traverse(node->right, code + "1");
    } else {
        cout << "Data: " << node->data << ", Freq: " << node->freq << ", Code: " << code << endl;
    }
}

int main() {
    string str = "ACCEBFFFFAAXXBLKE";
    int freq[256] = {0};
    for (char c : str) freq[(int)c]++;

    priority_queue<Node*> pq;
    for (int i = 0; i < 256; i++)
        if (freq[i] > 0) pq.push(new Node((char)i, freq[i]));

    while (pq.size() > 1) {
        Node* left = pq.top(); pq.pop();
        Node* right = pq.top(); pq.pop();
        pq.push(new Node(left, right));
    }

    cout << "Huffman Codes:\n";
    traverse(pq.top(), "");
}

คุณสมบัติสำคัญ

• Prefix-free: ไม่มีรหัสตัวหนึ่งเป็นคำนำหน้าของอีกตัว (Decode ได้อย่างเดียว)
• Optimal: ให้ความยาวรหัสเฉลี่ยน้อยที่สุดสำหรับความถี่ที่กำหนด
• Lossless: ถอดรหัสกลับได้ข้อมูลต้นฉบับสมบูรณ์

การประยุกต์ใช้

• บีบอัดไฟล์: ZIP, GZIP, PNG, MP3, JPEG (ส่วนหนึ่ง)
• โปรโตคอลเครือข่าย, ฟอนต์, ฐานข้อมูล