Huffman Coding แบบมีประสิทธิภาพสำหรับอินพุตที่เรียงแล้ว

Efficient Huffman Coding for Sorted Input เป็นการปรับปรุงอัลกอริทึม Huffman Coding เมื่อ ความถี่ (Frequency) เรียงลำดับจากน้อยไปมากแล้ว ลดความซับซ้อนจาก O(n log n) เป็น O(n)

แนวคิดหลัก

ใช้ 2 คิว (Queues): Q1 สำหรับโหนดใบ (Leaf nodes) เรียงตามความถี่, Q2 สำหรับโหนดภายใน (Internal nodes)
• ทุกขั้นตอน ดึง 2 โหนดที่มีความถี่น้อยที่สุดจากหัวของ Q1 และ Q2
• สร้างโหนดพาเรนต์ใหม่ ใส่เข้า Q2 (Q2 จะเรียงอัตโนมัติเพราะความถี่รวมเพิ่มขึ้น)
• ทำซ้ำจนเหลือ 1 โหนด (Root)

ตัวอย่างข้อมูล

Letters:  {L, K, X, C, E, B, A, F}
Frequency: {1, 1, 2, 2, 2, 2, 3, 4}  // เรียงแล้ว

Output Codes:
L: 0000   K: 0001   X: 001   C: 010
E: 011    F: 10     B: 110   A: 111

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

huffmanTree(data[], freq[], n)
  Q1 = queue of leaf nodes (sorted by freq)
  Q2 = empty queue

  for each character:
    Q1.enqueue(new Node(char, freq))

  while Q1 not empty OR Q2.size() != 1:
    c0 = dequeueMin(Q1, Q2)  // min from front of both queues
    c1 = dequeueMin(Q1, Q2)
    parent = new Node('#', c0.freq + c1.freq)
    parent.left = c0; parent.right = c1
    Q2.enqueue(parent)

  return Q2.dequeue()  // root

getCodes(node, code[], top)
  if node.left:
    code[top] = 0; getCodes(node.left, code, top+1)
  if node.right:
    code[top] = 1; getCodes(node.right, code, top+1)
  if leaf node:
    print node.char + ": " + code[0..top-1]

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

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

struct Node {
    char data;
    int freq;
    Node *left, *right;
};

Node* getNode(char d, int f) {
    Node* n = new Node;
    n->data = d; n->freq = f; n->left = n->right = NULL;
    return n;
}

Node* findMin(queue<Node*> &q1, queue<Node*> &q2) {
    if (q1.empty()) { Node* n = q2.front(); q2.pop(); return n; }
    if (q2.empty()) { Node* n = q1.front(); q1.pop(); return n; }
    if (q1.front()->freq < q2.front()->freq) {
        Node* n = q1.front(); q1.pop(); return n;
    } else {
        Node* n = q2.front(); q2.pop(); return n;
    }
}

Node* huffmanTree(char data[], int freq[], int n) {
    queue<Node*> q1, q2;
    for (int i = 0; i < n; i++)
        q1.push(getNode(data[i], freq[i]));

    while (!(q1.empty() && q2.size() == 1)) {
        Node *c0 = findMin(q1, q2);
        Node *c1 = findMin(q1, q2);
        Node *par = getNode('#', c0->freq + c1->freq);
        par->left = c0; par->right = c1;
        q2.push(par);
    }
    Node* root = q2.front(); q2.pop();
    return root;
}

void getCodes(Node* root, int code[], int top) {
    if (root->left) { code[top] = 0; getCodes(root->left, code, top+1); }
    if (root->right) { code[top] = 1; getCodes(root->right, code, top+1); }
    if (!root->left && !root->right) {
        cout << root->data << ": ";
        for (int i = 0; i < top; i++) cout << code[i];
        cout << endl;
    }
}

int main() {
    char data[] = {'L','K','X','C','E','B','A','F'};
    int freq[] = {1,1,2,2,2,2,3,4};
    int n = 8;
    Node* root = huffmanTree(data, freq, n);
    int code[50];
    getCodes(root, code, 0);
}

ข้อได้เปรียบ

• O(n) แทนที่จะเป็น O(n log n) - ไม่ต้องใช้ Priority Queue (Heap)
• ง่ายกว่า ใช้ Queue ธรรมดา 2 ตัว
• เหมาะสำหรับ Embedded Systems ที่ทรัพยากรจำกัด

เงื่อนไข

ต้องมี Frequency เรียงลำดับจากน้อยไปมากแล้ว มิฉะนั้นต้องเรียงก่อน (กลับเป็น O(n log n))