Mã hóa Huffman là thuật toán nén dữ liệu không mất dữ liệu. Trong thuật toán này, một mã có độ dài thay đổi được gán để nhập các ký tự khác nhau. Độ dài mã có liên quan đến tần suất các ký tự được sử dụng. Các ký tự thường gặp nhất có mã nhỏ nhất và mã dài hơn cho các ký tự ít thường xuyên nhất.
Chủ yếu có hai phần. Một cái đầu tiên để tạo cây Huffman và một cái khác để đi qua cây để tìm mã.
Ví dụ:hãy xem xét một số chuỗi “YYYZXXYYX”, tần số của ký tự Y lớn hơn X và ký tự Z có tần suất ít nhất. Vì vậy, độ dài của mã cho Y nhỏ hơn X và mã cho X sẽ nhỏ hơn Z.
-
Độ phức tạp để gán mã cho từng ký tự theo tần số của chúng là O (n log n)
Đầu vào - Một chuỗi có các ký tự khác nhau, nói “ACCEBFFFFAAXXBLKE”
Đầu ra - Mã cho các ký tự khác nhau:
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 (chuỗi)
Đầu vào - Một chuỗi có các ký tự khác nhau.
Đầu ra - Các mã cho từng ký tự riêng lẻ.
Begin define a node with character, frequency, left and right child of the node for Huffman tree. create a list ‘freq’ to store frequency of each character, initially all are 0 for each character c in the string do increase the frequency for character ch in freq list. done for all type of character ch do if the frequency of ch is non zero then add ch and its frequency as a node of priority queue Q. done while Q is not empty do remove item from Q and assign it to left child of node remove item from Q and assign to the right child of node traverse the node to find the assigned code done End
traverseNode (n:nút, mã)
Đầu vào - Nút n của cây Huffman và mã được gán từ lần gọi trước
Đầu ra - Mã được gán với từng ký tự
if left child of node n ≠ φ then traverseNode(leftChild(n), code+’0’) //traverse through the left child traverseNode(rightChild(n), code+’1’) //traverse through the right child else display the character and data of current node.
Ví dụ
#include<iostream>
#include<queue>
#include<string>
using namespace std;
struct node{
int freq;
char data;
const node *child0, *child1;
node(char d, int f = -1){ //assign values in the node
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 { //< operator performs to find priority in queue
return freq >a.freq;
}
void traverse(string code = "")const{
if(child0!=NULL){
child0->traverse(code+'0'); //add 0 with the code as left child
child1->traverse(code+'1'); //add 1 with the code as right child
}else{
cout << "Data: " << data<< ", Frequency: "<<freq << ", Code: " << code<<endl;
}
}
};
void huffmanCoding(string str){
priority_queue<node> qu;
int frequency[256];
for(int i = 0; i<256; i++)
frequency[i] = 0; //clear all frequency
for(int i = 0; i<str.size(); i++){
frequency[int(str[i])]++; //increase frequency
}
for(int i = 0; i<256; i++){
if(frequency[i]){
qu.push(node(i, frequency[i]));
}
}
while(qu.size() >1){
node *c0 = new node(qu.top()); //get left child and remove from queue
qu.pop();
node *c1 = new node(qu.top()); //get right child and remove from queue
qu.pop();
qu.push(node(c0, c1)); //add freq of two child and add again in the queue
}
cout << "The Huffman Code: "<<endl;
qu.top().traverse(); //traverse the tree to get code
}
main(){
string str = "ACCEBFFFFAAXXBLKE"; //arbitray string to get frequency
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