हफमैन कोडिंग

हफमैन कोडिंग एक लॉसलेस डेटा कम्प्रेशन एल्गोरिदम है। इस एल्गोरिदम में इनपुट के विभिन्न कैरेक्टर को एक वेरिएबल-लेंथ कोड असाइन किया जाता है। कोड की लंबाई इस बात से संबंधित होती है कि कैरेक्टर कितनी बार उपयोग किए जाते हैं। सबसे अधिक बार आने वाले कैरेक्टर के सबसे छोटे कोड होते हैं, और कम बार आने वाले कैरेक्टर के लंबे कोड होते हैं।

मुख्य रूप से दो भाग हैं। पहला हफमैन ट्री बनाना, और दूसरा कोड खोजने के लिए ट्री को ट्रैवर्स करना।

उदाहरण के लिए, कुछ स्ट्रिंग "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
    कैरेक्टर, फ्रीक्वेंसी, नोड के लेफ्ट और राइट चाइल्ड के साथ एक नोड परिभाषित करें हफमैन ट्री के लिए।
    'freq' नामक एक लिस्ट बनाएं प्रत्येक कैरेक्टर की फ्रीक्वेंसी संग्रहीत करने के लिए, प्रारंभ में सभी 0 हैं
    स्ट्रिंग में प्रत्येक कैरेक्टर c के लिए do
        freq लिस्ट में कैरेक्टर ch की फ्रीक्वेंसी बढ़ाएं।
    done
    सभी प्रकार के कैरेक्टर ch के लिए do
        यदि ch की फ्रीक्वेंसी नॉन-ज़ीरो है तो ch और उसकी फ्रीक्वेंसी को प्रायोरिटी क्यू Q के नोड के रूप में जोड़ें।
    done
    while Q खाली नहीं है do
        Q से आइटम हटाएं और नोड के लेफ्ट चाइल्ड को असाइन करें
        Q से आइटम हटाएं और नोड के राइट चाइल्ड को असाइन करें
        नोड को ट्रैवर्स करें असाइन किए गए कोड को खोजने के लिए
    done
End

traverseNode(n: node, code)

इनपुट − हफमैन ट्री का नोड n, और पिछले कॉल से असाइन किया गया कोड

आउटपुट − प्रत्येक कैरेक्टर के साथ असाइन किया गया कोड

if नोड n का लेफ्ट चाइल्ड ≠ φ then
    traverseNode(लेफ्टचाइल्ड(n), code+'0') //लेफ्ट चाइल्ड के माध्यम से ट्रैवर्स करें
    traverseNode(राइटचाइल्ड(n), code+'1') //राइट चाइल्ड के माध्यम से ट्रैवर्स करें
else
    वर्तमान नोड के कैरेक्टर और डेटा प्रदर्शित करें।

उदाहरण (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'); //लेफ्ट चाइल्ड के रूप में कोड के साथ 0 जोड़ें
            child1->traverse(code+'1'); //राइट चाइल्ड के रूप में कोड के साथ 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