হাফম্যান কোডিং

হাফম্যান কোডিং হলো একটি লসলেস ডেটা কমপ্রেশন অ্যালগরিদম। এই অ্যালগরিদমে ইনপুটের বিভিন্ন ক্যারেক্টারের জন্য ভেরিয়েবল-লেঞ্জ কোড অ্যাসাইন করা হয়। কোডের দৈর্ঘ্য ক্যারেক্টার কত কমন 사용하는 সাথে সম্পর্কিত। সবচেয়ে কমন ক্যারেক্টারগুলো সবচেয়ে ছোট কোড পায়, এবং কম কমন ক্যারেক্টারগুলো লম্বা কোড পায়।

এখানে মূলত দুটি পার্ট আছে। প্রথমটি হাফম্যান ট্রি তৈরি করা, এবং দ্বিতীয়টি ট্রি ট্রাভার্স করে কোড বের করা।

উদাহরণস্বরূপ, কিছু স্ট্রিং ধরুন "YYYZXXYYX", এখানে Y ক্যারেক্টারের ফ্রিকোয়েন্সি X-র চেয়ে বেশি এবং Z-র সবচেয়ে কম। তাই Y-এর কোডের দৈর্ঘ্য X-র চেয়ে ছোট, এবং X-এর কোড Z-র চেয়ে ছোট হবে।

• প্রতিটি ক্যারেক্টারের ফ্রিকোয়েন্সি অনুযায়ী কোড অ্যাসাইন করার কমপ্লেক্সিটি O(n log n)

ইনপুট − বিভিন্ন ক্যারেক্টারের স্ট্রিং, মনে করুন "ACCEBFFFFAAXXBLKE"
আউটপুট − বিভিন্ন ক্যারেক্টারের জন্য কোড:

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
    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: node, code)

ইনপুট − হাফম্যান ট্রির নোড n, এবং পূর্বের কল থেকে অ্যাসাইন করা কোড।

আউটপুট − প্রতিটি ক্যারেক্টারের সাথে অ্যাসাইন করা কোড।

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.

উদাহরণ (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 < str.size(); i++){
        frequency[int(str[i])]++;
    }
    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());
        qu.pop();
        node *c1 = new node(qu.top());
        qu.pop();
        qu.push(node(c0, c1));
    }
    cout << "The Huffman Code: " << endl;
    qu.top().traverse();
}
int main(){
    string str = "ACCEBFFFFAAXXBLKE";
    huffmanCoding(str);
}

আউটপুট

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