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
EndduyetNode(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