সাজানো ইনপুটের জন্য দক্ষ হাফম্যান কোডিং

আগের হাফম্যান কোড সমস্যায়, ফ্রিকোয়েন্সি সাজানো হয়নি। যদি ফ্রিকোয়েন্সি তালিকাটি সাজানো ক্রমে দেওয়া হয়, তাহলে কোড বরাদ্দ করার কাজটি আরও দক্ষ হচ্ছে৷

এই সমস্যায়, আমরা দুটি খালি সারি ব্যবহার করব। তারপর প্রতিটি অনন্য অক্ষরের জন্য একটি লিফ নোড তৈরি করুন এবং ফ্রিকোয়েন্সির ক্রমবর্ধমান ক্রমে সারিতে প্রবেশ করান৷

এই পদ্ধতিতে, অ্যালগরিদমের জটিলতা হল O(n).

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

Input:
Different letters and their frequency in sorted order
Letters: {L, K, X, C, E, B, A, F}
Frequency: {1, 1, 2, 2, 2, 2, 3, 4}
Output:
Codes for the letters
L: 0000
K: 0001
X: 001
C: 010
E: 011
F: 10
B: 110
A: 111

অ্যালগরিদম

হাফম্যানকোডস (dataList, freqList, n)

ইনপুট: ডেটা তালিকা এবং ফ্রিকোয়েন্সির তালিকা, এবং তালিকায় ডেটার সংখ্যা n.

আউটপুট - কোডে অক্ষর বরাদ্দ করা হয়েছে।

Begin
   root := huffmanTree(dataList, freqList, n) //create root of Huffman tree create an array to store codes, and top pointer for that array.
   call getCodes(root, array, top) to find codes for each character.
End

কোড পান (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
      display the character ch of root
      for all entries of the array do
         display the code in array[i] for character ch
      done
End

হাফম্যানট্রি(ডেটালিস্ট, ফ্রিকলিস্ট, n)

ইনপুট - ডেটা তালিকা এবং ফ্রিকোয়েন্সির তালিকা, এবং তালিকায় ডেটার সংখ্যা n.

আউটপুট - একটি হাফম্যান গাছ তৈরি করে

Begin
   for all different character ch do
      add node with ch and frequency of ch into queue q1
   done

   while q1 is not empty OR size of q2 ≠ 1 do
      find two minimum node using q1 and q2 and add them as left and
      right child of a new node.
      add new node in q2
   done

   delete node from q2 and return that node.
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()) { //if first queue is empty, delete and return node from second queue
      minNode = q2.front();
      q2.pop();
      return minNode;
   }

   if(q2.empty()) { //if second queue is empty, delete and return node from first queue
      minNode = q1.front();
      q1.pop();
      return minNode;
   }

   if((q1.front()->freq) < (q2.front()->freq)) { //find smaller from two queues
      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++) { //add all node to queue 1
      newNode = getNode(data[i], frequency[i]);
      qu1.push(newNode);
   }

   while(!(qu1.empty() && (qu2.size() == 1))) {
      c0 = findMinNode(qu1, qu2); //find two minimum as two child
      c1 = findMinNode(qu1, qu2);
      node *newNode = getNode('#', c0->freq+c1->freq);

      //intermediate node holds special character
      par = newNode;
      par->child0 = c0;
      par->child1 = c1;
      qu2.push(par); //add sub tree into queue 2
   }

   node *retNode = qu2.front();
   qu2.pop();
   return retNode;
}

void getCodes(node *rootNode, int array[], int n) {  //array to store the code
   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) {  // when root is leaf node
      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