হাফম্যান কোডিং একটি লসলেস ডেটা কম্প্রেশন অ্যালগরিদম। এতে ভেরিয়েবল-লেথ কোড অ্যাসাইন করা হয় ক্যারেক্টারগুলোকে। কোডের দৈর্ঘ্য ক্যারেক্টারের ফ্রিকোয়েন্সির ওপর নির্ভর করে। বেশি ফ্রিকোয়েন্সি = ছোট কোড, কম ফ্রিকোয়েন্সি = বড় কোড।
দুটি প্রধান অংশ: ১) হাফম্যান ট্রি তৈরি, ২) ট্রি ট্রাভার্সাল করে কোড বের করা।
ইনপুট এবং আউটপুট
Input: "ACCEBFFFFAAXXBLKE"
Output:
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
অ্যালগরিদম
huffmanCoding(string)
Begin
নোড ডিফাইন করুন (char, freq, left, right)
freq লিস্ট তৈরি করুন (২৫৬ সাইজ, সব ০)
স্ট্রিংয়ের প্রতিটি ক্যারেক্টারের ফ্রিকোয়েন্সি বাড়ান
নন-জিরো ফ্রিকোয়েন্সি 가진 ক্যারেক্টারগুলো প্রায়োরিটি কিউ (Q) এ डालুন
while Q not empty:
Q থেকে রিমুভ করে লेफট চাইল্ড, আবার রিমুভ করে রাইট চাইল্ড
নোড ট্রাভার্স করে কোড বের করুন
done
End
traverseNode(node, code)
if left child exists: traverseNode(left, code+'0')
if right child exists: traverseNode(right, code+'1')
else: print character, frequency, code
C++ উদাহরণ
#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) : 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; } // min-heap
void traverse(string code="") const {
if(child0) { child0->traverse(code+'0'); child1->traverse(code+'1'); }
else { cout << "Data: " << data << ", Frequency: " << freq << ", Code: " << code << endl; }
}
};
int main() {
string str = "ACCEBFFFFAAXXBLKE";
int freq[256] = {0};
for(char c : str) freq[(int)c]++;
priority_queue<node> qu;
for(int i=0; i<256; i++) if(freq[i]) qu.push(node(i, freq[i]));
while(qu.size() > 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();
}
আউটপুট
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
