सॉर्टेड इनपुट के लिए कुशल हफमैन कोडिंग

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

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

इस दृष्टिकोण में, एल्गोरिदम की जटिलता O(n) है।

इनपुट और आउटपुट

इनपुट: विभिन्न अक्षर और सॉर्टेड क्रम में उनकी फ्रीक्वेंसी
अक्षर: {L, K, X, C, E, B, A, F}
फ्रीक्वेंसी: {1, 1, 2, 2, 2, 2, 3, 4}
आउटपुट: अक्षरों के लिए कोड
L: 0000
K: 0001
X: 001
C: 010
E: 011
F: 10
B: 110
A: 111

एल्गोरिदम

huffmanCodes(dataList, freqList, n)

इनपुट: डेटा लिस्ट और फ्रीक्वेंसी की लिस्ट, और लिस्ट में डेटा की संख्या n।

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

Begin
    root := huffmanTree(dataList, freqList, n) // हफमैन ट्री की रूट बनाएं
    कोड स्टोर करने के लिए एक ऐरे बनाएं, और उस ऐरे के लिए टॉप पॉइंटर।
    प्रत्येक कैरेक्टर के लिए कोड ढूंढने के लिए getCodes(root, array, top) कॉल करें।
End

getCodes(root: node, array, top)

इनपुट: रूट नोड, कोड स्टोर करने के लिए ऐरे, ऐरे का टॉप।

आउटपुट: प्रत्येक कैरेक्टर के लिए कोड

Begin
    if leftChild(root) ≠ ∅ then
        array[top] := 0
        getCodes(leftChild(root), array, top)
    if rightChild(root) ≠ ∅ then
        array[top] = 1
        getCode(rightChild(root), array, top)
    if leftChild(root) = ∅ AND rightChild(root) = ∅ then
        रूट का कैरेक्टर ch प्रदर्शित करें
        ऐरे की सभी एंट्रीज़ के लिए do
            कैरेक्टर ch के लिए ऐरे[i] में कोड प्रदर्शित करें
        done
End

huffmanTree(dataList, freqList, n)

इनपुट: डेटा लिस्ट और फ्रीक्वेंसी की लिस्ट, और लिस्ट में डेटा की संख्या n।

आउटपुट: एक हफमैन ट्री बनाता है

Begin
    for all different character ch do
        ch और ch की फ्रीक्वेंसी के साथ नोड को क्यू q1 में जोड़ें
    done
    while q1 is not empty OR size of q2 ≠ 1 do
        q1 और q2 का उपयोग करके दो न्यूनतम नोड ढूंढें और उन्हें एक नए नोड के लेफ्ट और राइट चाइल्ड के रूप में जोड़ें।
        नए नोड को q2 में जोड़ें
    done
    q2 से नोड डिलीट करें और वह नोड वापस करें।
End

उदाहरण

#include <iostream>
#include <queue>
using namespace std;

struct node {
    char data;
    int freq;
    node *child0, *child1;
};

node *getNode(char d, int f) {
    node *newNode = new node;
    newNode->data = d;
    newNode->freq = f;
    newNode->child0 = NULL;
    newNode->child1 = NULL;
    return newNode;
}

node *findMinNode(queue<node*> &q1, queue<node*> &q2) {
    node *minNode;
    if(q1.empty()) { // यदि पहली क्यू खाली है, तो दूसरी क्यू से नोड डिलीट करके वापस करें
        minNode = q2.front();
        q2.pop();
        return minNode;
    }
    if(q2.empty()) { // यदि दूसरी क्यू खाली है, तो पहली क्यू से नोड डिलीट करके वापस करें
        minNode = q1.front();
        q1.pop();
        return minNode;
    }
    if((q1.front()->freq) < (q2.front()->freq)) { // दो क्यूज़ से छोटा ढूंढें
        minNode = q1.front();
        q1.pop();
        return minNode;
    } else {
        minNode = q2.front();
        q2.pop();
        return minNode;
    }
}

node *huffmanTree(char data[], int frequency[], int n) {
    node *c0, *c1, *par;
    node *newNode;
    queue<node*> qu1, qu2;
    for(int i = 0; i < n; i++) { // सभी नोड्स को क्यू 1 में जोड़ें
        newNode = getNode(data[i], frequency[i]);
        qu1.push(newNode);
    }
    while(!(qu1.empty() && (qu2.size() == 1))) {
        c0 = findMinNode(qu1, qu2); // दो न्यूनतम को दो चाइल्ड के रूप में ढूंढें
        c1 = findMinNode(qu1, qu2);
        node *newNode = getNode('#', c0->freq + c1->freq);
        // इंटरमीडिएट नोड स्पेशल कैरेक्टर रखता है
        par = newNode;
        par->child0 = c0;
        par->child1 = c1;
        qu2.push(par); // सब ट्री को क्यू 2 में जोड़ें
    }
    node *retNode = qu2.front();
    qu2.pop();
    return retNode;
}

void getCodes(node *rootNode, int array[], int n) {
    // कोड स्टोर करने के लिए ऐरे
    if(rootNode->child0 != NULL) {
        array[n] = 0;
        getCodes(rootNode->child0, array, n + 1);
    }
    if(rootNode->child1 != NULL) {
        array[n] = 1;
        getCodes(rootNode->child1, array, n + 1);
    }
    if(rootNode->child0 == NULL && rootNode->child1 == NULL) {
        // जब रूट लीफ नोड हो
        cout << rootNode->data << ": ";
        for(int i = 0; i < n; i++)
            cout << array[i];
        cout << endl;
    }
}

void huffmanCodes(char data[], int frequency[], int n) {
    node *rootNode = huffmanTree(data, frequency, n);
    int array[50], top = 0;
    getCodes(rootNode, array, top);
}

int main() {
    char data[] = {'L', 'K', 'X', 'C', 'E', 'B', 'A', 'F'};
    int frequency[] = {1, 1, 2, 2, 2, 2, 3, 4};
    int n = sizeof(data) / sizeof(data[0]);
    huffmanCodes(data, frequency, n);
}

आउटपुट

L: 0000 K: 0001 X: 001 C: 010 E: 011 F: 10 B: 110 A: 111