Huffman Coding hiệu quả cho đầu vào đã sắp xếp

Trong bài Huffman coding trước, tần suất chưa sắp xếp. Nếu danh sách tần suất đã cho theo thứ tự tăng dần, việc gán mã hiệu quả hơn.

Sử dụng hai hàng đợi rỗng. Tạo node lá cho mỗi ký tự duy nhất và chèn vào hàng đợi theo thứ tự tần suất tăng dần.

Độ phức tạp: O(n)

Input và Output

Input: Ký tự và tần suất đã sắp xếp
Letters: {L, K, X, C, E, B, A, F}
Frequency: {1, 1, 2, 2, 2, 2, 3, 4}
Output: Mã cho các ký tự
L: 0000  K: 0001  X: 001  C: 010  E: 011  F: 10  B: 110  A: 111

Thuật toán

huffmanCodes(dataList, freqList, n)

Begin
  root := huffmanTree(dataList, freqList, n)
  tạo mảng lưu mã, con trỏ top
  gọi getCodes(root, mảng, top) để tìm mã cho từng ký tự
End

getCodes(root, array, top)

Begin
  if leftChild(root) ≠ ∅ then
    array[top] := 0
    getCodes(leftChild(root), array, top+1)
  if rightChild(root) ≠ ∅ then
    array[top] = 1
    getCodes(rightChild(root), array, top+1)
  if leftChild(root) = ∅ AND rightChild(root) = ∅ then
    hiển thị ký tự ch của root
    for tất cả entry của array do hiển thị array[i] done
End

huffmanTree(dataList, freqList, n)

Begin
  for tất cả ký tự ch do
    thêm node với ch và tần suất vào queue q1
  done
  while q1 không rỗng OR size(q2) ≠ 1 do
    tìm 2 node nhỏ nhất từ q1, q2 làm con trái/phải của node mới
    thêm node mới vào q2
  done
  xóa node từ q2 và trả về node đó
End

Ví dụ (C++)

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

struct node { char data; int freq; node *child0, *child1; };

node *getNode(char d, int f) {
    node *n = new node; n->data = d; n->freq = f; n->child0 = n->child1 = NULL; return n;
}

node *findMinNode(queue<node*> &q1, queue<node*> &q2) {
    if(q1.empty()) { node *m = q2.front(); q2.pop(); return m; }
    if(q2.empty()) { node *m = q1.front(); q1.pop(); return m; }
    if(q1.front()->freq < q2.front()->freq) { node *m = q1.front(); q1.pop(); return m; }
    else { node *m = q2.front(); q2.pop(); return m; }
}

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 = findMinNode(q1, q2);
        node *c1 = findMinNode(q1, q2);
        node *par = getNode('#', c0->freq + c1->freq);
        par->child0 = c0; par->child1 = c1;
        q2.push(par);
    }
    node *ret = q2.front(); q2.pop(); return ret;
}

void getCodes(node *root, int arr[], int n) {
    if(root->child0) { arr[n] = 0; getCodes(root->child0, arr, n+1); }
    if(root->child1) { arr[n] = 1; getCodes(root->child1, arr, n+1); }
    if(!root->child0 && !root->child1) {
        cout << root->data << ": ";
        for(int i = 0; i < n; i++) cout << arr[i];
        cout << endl;
    }
}

void huffmanCodes(char data[], int freq[], int n) {
    node *root = huffmanTree(data, freq, n);
    int arr[50]; getCodes(root, arr, 0);
}

int main() {
    char data[] = {'L','K','X','C','E','B','A','F'};
    int freq[] = {1,1,2,2,2,2,3,4};
    int n = sizeof(data)/sizeof(data[0]);
    huffmanCodes(data, freq, n);
}

Kết quả

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

Lợi ích: Khi tần suất đã sắp xếp, không cần priority queue (heap) - chỉ dùng 2 queue đơn giản, giảm độ phức tạp từ O(n log n) xuống O(n).