การเข้ารหัส Huffman ที่มีประสิทธิภาพสำหรับการจัดเรียงอินพุต

ในปัญหาโค้ด Huffman ก่อนหน้านี้ ความถี่ไม่ได้รับการจัดเรียง หากรายการความถี่เรียงตามลำดับงาน การกำหนดรหัสจะมีประสิทธิภาพมากขึ้น

ในปัญหานี้ เราจะใช้คิวว่างสองคิว จากนั้นสร้างโหนดปลายสุดสำหรับอักขระที่ไม่ซ้ำกันแต่ละตัว และแทรกลงในคิวโดยเรียงลำดับความถี่เพิ่มขึ้น

ในแนวทางนี้ ความซับซ้อนของอัลกอริทึมคือ 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

อัลกอริทึม

huffmanCodes (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

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
      display the character ch of root
      for all entries of the array do
         display the code in array[i] for character ch
      done
End

huffmanTree(dataList, freqList, 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