हफमैन कोडिंग एल्गोरिदम

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

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

उदाहरण के लिए, स्ट्रिंग "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 is not empty do
        Q से आइटम हटाएं और इसे नोड के लेफ्ट चाइल्ड को असाइन करें
        Q से आइटम हटाएं और इसे नोड के राइट चाइल्ड को असाइन करें
        नोड को ट्रैवर्स करके असाइन किया गया कोड ढूंढें
    done
End

traverseNode(n: node, code)

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

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

if a left child of node n ≠ ∅ then
    traverseNode(leftChild(n), code + '0')  // लेफ्ट चाइल्ड के माध्यम से ट्रैवर्स करें
    traverseNode(rightChild(n), code + '1') // राइट चाइल्ड के माध्यम से ट्रैवर्स करें
else
    वर्तमान नोड का कैरेक्टर और डेटा प्रदर्शित करें。

उदाहरण

#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;
    }
    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;
        }
    }
};

int main() {
    string str = "ACCEBFFFFAAXXBLKE";
    priority_queue<node> qu;
    int frequency[256];
    for(int i = 0; i < 256; i++)
        frequency[i] = 0; // सभी फ्रीक्वेंसी क्लियर करें
    for(int i = 0; i < str.size(); i++)
        frequency[str[i]]++;
    for(int i = 0; i < 256; i++)
        if(frequency[i] > 0)
            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: ";
    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