Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> Lập Trình

Mã hóa Huffman (Huffman Coding)


Mã hóa Huffman là thuật toán nén dữ liệu không mất mát. Gán mã độ dài biến cho ký tự đầu vào. Độ dài mã liên quan đến tần suất xuất hiện. Ký tự thường dùng có mã ngắn, hiếm dùng có mã dài.

Có hai phần chính: xây dựng cây Huffman, và duyệt cây để tìm mã.

Ví dụ: chuỗi "YYYZXXYYX", tần suất Y lớn hơn X, Z nhỏ nhất. Do đó mã Y ngắn hơn X, X ngắn hơn Z.

  • Độ phức tạp gán mã theo tần suất: O(n log n)

Đầu vào − Chuỗi các ký tự, ví dụ "ACCEBFFFFAAXXBLKE"
Đầu ra − Mã cho các ký tự:

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

Thuật toán

huffmanCoding(string)

Đầu vào − Chuỗi các ký tự.

Đầu ra − Mã cho từng ký tự.

Begin
    định nghĩa nút với ký tự, tần suất, con trái, con phải cho cây Huffman
    tạo danh sách 'freq' lưu tần suất mỗi ký tự, ban đầu 0
    for mỗi ký tự c trong chuỗi do
        tăng tần suất cho ký tự ch trong freq
    done
    for tất cả loại ký tự ch do
        nếu tần suất ch khác 0 thì thêm ch và tần suất làm nút của hàng đợi ưu tiên Q
    done
    while Q không rỗng do
        lấy mục từ Q gán cho con trái của nút
        lấy mục từ Q gán cho con phải của nút
        duyệt nút để tìm mã gán
    done
End

duyetNode(n: node, code)

Đầu vào − Nút n của cây Huffman, và mã từ lời gọi trước

Đầu ra − Mã gán cho từng ký tự

if con trái của nút n ≠ φ then
    duyetNode(conTrái(n), code+'0')
    duyetNode(conPhải(n), code+'1')
else
    hiển thị ký tự và dữ liệu của nút hiện tại.

Ví dụ (C++)

#include 
#include 
#include 
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;
    }
    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];
    for(int i = 0; i<256; i++) frequency[i] = 0;
    for(int i = 0; i 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);
}

Đầu ra

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