সর্ট করা ইনপুটের জন্য দক্ষ হাফম্যান কোডিং (Efficient Huffman Coding for Sorted Input)

সাধারণ হাফম্যান কোডিং-এ ফ্রিকোয়েন্সি সর্টেড থাকে না। যদি ফ্রিকোয়েন্সি লিস্ট আগে থেকে সর্টেড থাকে, তবে কোড অ্যাসাইন করার কাজ আরও দক্ষ হয়। এই পদ্ধতিতে দুটি খালি কিউ (queue) ব্যবহার করা হয়।

ইনপুট এবং আউটপুট

Input: Letters: {L, K, X, C, E, B, A, F}
       Frequency: {1, 1, 2, 2, 2, 2, 3, 4} (সর্টেড)
Output: Codes:
L: 0000  K: 0001  X: 001  C: 010  E: 011  F: 10  B: 110  A: 111

অ্যালগরিদম

huffmanCodes(dataList, freqList, n)

Begin
    root := huffmanTree(dataList, freqList, n)
    codes অ্যারে এবং টপ পয়েন্টার তৈরি করুন
    getCodes(root, codes, top) কল করুন
End

getCodes(root, codes, top)

Begin
    if leftChild exists: codes[top]=0, getCodes(left, codes, top+1)
    if rightChild exists: codes[top]=1, getCodes(right, codes, top+1)
    if leaf node: print character and codes array
End

huffmanTree(dataList, freqList, n)

Begin
    সব ক্যারেক্টারের জন্য নোড তৈরি করে q1-এ পুশ করুন (সর্টেড অর্ডারে)
    while q1 not empty OR q2.size != 1 do
        q1, q2 থেকে দুটি মিনিমাম নোড বের করুন
        নতুন নোড তৈরি করুন (সামeric ফ্রিকোয়েন্সি)
        নতুন নোড q2-এ পুশ করুন
    done
    q2 থেকে নোড ডিলিট করে রিটার্ন করুন
End

C++ উদাহরণ

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

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

node* getNode(char d, int f) { ... }
node* findMinNode(queue<node*>&q1, queue<node*>&q2) { ... }

node* huffmanTree(char data[], int frequency[], int n) {
    queue<node*> qu1, qu2;
    for(int i=0; ifreq + c1->freq);
        par->child0 = c0; par->child1 = c1;
        qu2.push(par);
    }
    node *ret = qu2.front(); qu2.pop(); return ret;
}

void getCodes(node *root, int arr[], int n) { ... }

void huffmanCodes(char data[], int freq[], int n) {
    node *root = huffmanTree(data, freq, n);
    int arr[50]; getCodes(root, arr, 0);
}

int main() {
    char data[] = {'L','K','X','C','E','B','A','F'};
    int freq[] = {1,1,2,2,2,2,3,4};
    huffmanCodes(data, freq, 8);
}

আউটপুট

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