کدگذاری هافمن (Huffman Coding) برای ورودی های مرتب — راهنمای کاربردی

1// C++ Program for Efficient Huffman Coding for Sorted input  
2#include <bits/stdc++.h> 
3using namespace std; 
4  
5// This constant can be avoided by explicitly  
6//calculating height of Huffman Tree  
7#define MAX_TREE_HT 100  
8  
9// A node of huffman tree  
10class QueueNode  
11{  
12    public: 
13    char data;  
14    unsigned freq;  
15    QueueNode *left, *right;  
16};  
17  
18// Structure for Queue: collection 
19// of Huffman Tree nodes (or QueueNodes)  
20class Queue  
21{  
22    public: 
23    int front, rear;  
24    int capacity;  
25    QueueNode **array;  
26};  
27  
28// A utility function to create a new Queuenode  
29QueueNode* newNode(char data, unsigned freq)  
30{  
31    QueueNode* temp = new QueueNode[(sizeof(QueueNode))];  
32    temp->left = temp->right = NULL;  
33    temp->data = data;  
34    temp->freq = freq;  
35    return temp;  
36}  
37  
38// A utility function to create a Queue of given capacity  
39Queue* createQueue(int capacity)  
40{  
41    Queue* queue = new Queue[(sizeof(Queue))];  
42    queue->front = queue->rear = -1;  
43    queue->capacity = capacity;  
44    queue->array = new QueueNode*[(queue->capacity * sizeof(QueueNode*))];  
45    return queue;  
46}  
47  
48// A utility function to check if size of given queue is 1  
49int isSizeOne(Queue* queue)  
50{  
51    return queue->front == queue->rear && queue->front != -1;  
52}  
53  
54// A utility function to check if given queue is empty  
55int isEmpty(Queue* queue)  
56{  
57    return queue->front == -1;  
58}  
59  
60// A utility function to check if given queue is full  
61int isFull(Queue* queue)  
62{  
63    return queue->rear == queue->capacity - 1;  
64}  
65  
66// A utility function to add an item to queue  
67void enQueue(Queue* queue, QueueNode* item)  
68{  
69    if (isFull(queue))  
70        return;  
71    queue->array[++queue->rear] = item;  
72    if (queue->front == -1)  
73        ++queue->front;  
74}  
75  
76// A utility function to remove an item from queue  
77QueueNode* deQueue(Queue* queue)  
78{  
79    if (isEmpty(queue))  
80        return NULL;  
81    QueueNode* temp = queue->array[queue->front];  
82    if (queue->front == queue->rear) // If there is only one item in queue  
83        queue->front = queue->rear = -1;  
84    else
85        ++queue->front;  
86    return temp;  
87}  
88  
89// A utility function to get from of queue  
90QueueNode* getFront(Queue* queue)  
91{  
92    if (isEmpty(queue))  
93        return NULL;  
94    return queue->array[queue->front];  
95}  
96  
97/* A function to get minimum item from two queues */
98QueueNode* findMin(Queue* firstQueue, Queue* secondQueue)  
99{  
100    // Step 3.a: If first queue is empty, dequeue from second queue  
101    if (isEmpty(firstQueue))  
102        return deQueue(secondQueue);  
103  
104    // Step 3.b: If second queue is empty, dequeue from first queue  
105    if (isEmpty(secondQueue))  
106        return deQueue(firstQueue);  
107  
108    // Step 3.c: Else, compare the front of two queues and dequeue minimum  
109    if (getFront(firstQueue)->freq < getFront(secondQueue)->freq)  
110        return deQueue(firstQueue);  
111  
112    return deQueue(secondQueue);  
113}  
114  
115// Utility function to check if this node is leaf  
116int isLeaf(QueueNode* root)  
117{  
118    return !(root->left) && !(root->right) ;  
119}  
120  
121// A utility function to print an array of size n  
122void printArr(int arr[], int n)  
123{  
124    int i;  
125    for (i = 0; i < n; ++i)  
126        cout<<arr[i];  
127    cout<<endl;  
128}  
129  
130// The main function that builds Huffman tree  
131QueueNode* buildHuffmanTree(char data[], int freq[], int size)  
132{  
133    QueueNode *left, *right, *top;  
134  
135    // Step 1: Create two empty queues  
136    Queue* firstQueue = createQueue(size);  
137    Queue* secondQueue = createQueue(size);  
138  
139    // Step 2:Create a leaf node for each unique character and Enqueue it to  
140    // the first queue in non-decreasing order of frequency. Initially second  
141    // queue is empty  
142    for (int i = 0; i < size; ++i)  
143        enQueue(firstQueue, newNode(data[i], freq[i]));  
144  
145    // Run while Queues contain more than one node. Finally, first queue will  
146    // be empty and second queue will contain only one node  
147    while (!(isEmpty(firstQueue) && isSizeOne(secondQueue)))  
148    {  
149        // Step 3: Dequeue two nodes with the minimum frequency by examining  
150        // the front of both queues  
151        left = findMin(firstQueue, secondQueue);  
152        right = findMin(firstQueue, secondQueue);  
153  
154        // Step 4: Create a new internal node with frequency equal to the sum  
155        // of the two nodes frequencies. Enqueue this node to second queue.  
156        top = newNode('$' , left->freq + right->freq);  
157        top->left = left;  
158        top->right = right;  
159        enQueue(secondQueue, top);  
160    }  
161  
162    return deQueue(secondQueue);  
163}  
164  
165// Prints huffman codes from the root of Huffman Tree. It uses arr[] to  
166// store codes  
167void printCodes(QueueNode* root, int arr[], int top)  
168{  
169    // Assign 0 to left edge and recur  
170    if (root->left)  
171    {  
172        arr[top] = 0;  
173        printCodes(root->left, arr, top + 1);  
174    }  
175  
176    // Assign 1 to right edge and recur  
177    if (root->right)  
178    {  
179        arr[top] = 1;  
180        printCodes(root->right, arr, top + 1);  
181    }  
182  
183    // If this is a leaf node, then it contains one of the input  
184    // characters, print the character and its code from arr[]  
185    if (isLeaf(root))  
186    {  
187        cout<<root->data<<": ";  
188        printArr(arr, top);  
189    }  
190}  
191  
192// The main function that builds a Huffman Tree and print codes by traversing  
193// the built Huffman Tree  
194void HuffmanCodes(char data[], int freq[], int size)  
195{  
196// Construct Huffman Tree  
197QueueNode* root = buildHuffmanTree(data, freq, size);  
198  
199// Print Huffman codes using the Huffman tree built above  
200int arr[MAX_TREE_HT], top = 0;  
201printCodes(root, arr, top);  
202}  
203  
204// Driver code 
205int main()  
206{  
207    char arr[] = {'a', 'b', 'c', 'd', 'e', 'f'};  
208    int freq[] = {5, 9, 12, 13, 16, 45};  
209    int size = sizeof(arr)/sizeof(arr[0]);  
210    HuffmanCodes(arr, freq, size);  
211    return 0;  
212}  
213  
214  
215// This code is contributed by rathbhupendra

1// C Program for Efficient Huffman Coding for Sorted input 
2#include <stdio.h> 
3#include <stdlib.h> 
4  
5// This constant can be avoided by explicitly calculating height of Huffman Tree 
6#define MAX_TREE_HT 100 
7  
8// A node of huffman tree 
9struct QueueNode 
10{ 
11    char data; 
12    unsigned freq; 
13    struct QueueNode *left, *right; 
14}; 
15  
16// Structure for Queue: collection of Huffman Tree nodes (or QueueNodes) 
17struct Queue 
18{ 
19    int front, rear; 
20    int capacity; 
21    struct QueueNode **array; 
22}; 
23  
24// A utility function to create a new Queuenode 
25struct QueueNode* newNode(char data, unsigned freq) 
26{ 
27    struct QueueNode* temp = 
28       (struct QueueNode*) malloc(sizeof(struct QueueNode)); 
29    temp->left = temp->right = NULL; 
30    temp->data = data; 
31    temp->freq = freq; 
32    return temp; 
33} 
34  
35// A utility function to create a Queue of given capacity 
36struct Queue* createQueue(int capacity) 
37{ 
38    struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue)); 
39    queue->front = queue->rear = -1; 
40    queue->capacity = capacity; 
41    queue->array = 
42      (struct QueueNode**) malloc(queue->capacity * sizeof(struct QueueNode*)); 
43    return queue; 
44} 
45  
46// A utility function to check if size of given queue is 1 
47int isSizeOne(struct Queue* queue) 
48{ 
49    return queue->front == queue->rear && queue->front != -1; 
50} 
51  
52// A utility function to check if given queue is empty 
53int isEmpty(struct Queue* queue) 
54{ 
55    return queue->front == -1; 
56} 
57  
58// A utility function to check if given queue is full 
59int isFull(struct Queue* queue) 
60{ 
61    return queue->rear == queue->capacity - 1; 
62} 
63  
64// A utility function to add an item to queue 
65void enQueue(struct Queue* queue, struct QueueNode* item) 
66{ 
67    if (isFull(queue)) 
68        return; 
69    queue->array[++queue->rear] = item; 
70    if (queue->front == -1) 
71        ++queue->front; 
72} 
73  
74// A utility function to remove an item from queue 
75struct QueueNode* deQueue(struct Queue* queue) 
76{ 
77    if (isEmpty(queue)) 
78        return NULL; 
79    struct QueueNode* temp = queue->array[queue->front]; 
80    if (queue->front == queue->rear)  // If there is only one item in queue 
81        queue->front = queue->rear = -1; 
82    else
83        ++queue->front; 
84    return temp; 
85} 
86  
87// A utility function to get from of queue 
88struct QueueNode* getFront(struct Queue* queue) 
89{ 
90    if (isEmpty(queue)) 
91        return NULL; 
92    return queue->array[queue->front]; 
93} 
94  
95/* A function to get minimum item from two queues */
96struct QueueNode* findMin(struct Queue* firstQueue, struct Queue* secondQueue) 
97{ 
98    // Step 3.a: If first queue is empty, dequeue from second queue 
99    if (isEmpty(firstQueue)) 
100        return deQueue(secondQueue); 
101  
102    // Step 3.b: If second queue is empty, dequeue from first queue 
103    if (isEmpty(secondQueue)) 
104        return deQueue(firstQueue); 
105  
106    // Step 3.c:  Else, compare the front of two queues and dequeue minimum 
107    if (getFront(firstQueue)->freq < getFront(secondQueue)->freq) 
108        return deQueue(firstQueue); 
109  
110    return deQueue(secondQueue); 
111} 
112  
113// Utility function to check if this node is leaf 
114int isLeaf(struct QueueNode* root) 
115{ 
116    return !(root->left) && !(root->right) ; 
117} 
118  
119// A utility function to print an array of size n 
120void printArr(int arr[], int n) 
121{ 
122    int i; 
123    for (i = 0; i < n; ++i) 
124        printf("%d", arr[i]); 
125    printf("\n"); 
126} 
127  
128// The main function that builds Huffman tree 
129struct QueueNode* buildHuffmanTree(char data[], int freq[], int size) 
130{ 
131    struct QueueNode *left, *right, *top; 
132  
133    // Step 1: Create two empty queues 
134    struct Queue* firstQueue  = createQueue(size); 
135    struct Queue* secondQueue = createQueue(size); 
136  
137    // Step 2:Create a leaf node for each unique character and Enqueue it to 
138    // the first queue in non-decreasing order of frequency. Initially second 
139    // queue is empty 
140    for (int i = 0; i < size; ++i) 
141        enQueue(firstQueue, newNode(data[i], freq[i])); 
142  
143    // Run while Queues contain more than one node. Finally, first queue will 
144    // be empty and second queue will contain only one node 
145    while (!(isEmpty(firstQueue) && isSizeOne(secondQueue))) 
146    { 
147        // Step 3: Dequeue two nodes with the minimum frequency by examining 
148        // the front of both queues 
149        left = findMin(firstQueue, secondQueue); 
150        right = findMin(firstQueue, secondQueue); 
151  
152        // Step 4: Create a new internal node with frequency equal to the sum 
153        // of the two nodes frequencies. Enqueue this node to second queue. 
154        top = newNode('$' , left->freq + right->freq); 
155        top->left = left; 
156        top->right = right; 
157        enQueue(secondQueue, top); 
158    } 
159  
160    return deQueue(secondQueue); 
161} 
162  
163// Prints huffman codes from the root of Huffman Tree.  It uses arr[] to 
164// store codes 
165void printCodes(struct QueueNode* root, int arr[], int top) 
166{ 
167    // Assign 0 to left edge and recur 
168    if (root->left) 
169    { 
170        arr[top] = 0; 
171        printCodes(root->left, arr, top + 1); 
172    } 
173  
174    // Assign 1 to right edge and recur 
175    if (root->right) 
176    { 
177        arr[top] = 1; 
178        printCodes(root->right, arr, top + 1); 
179    } 
180  
181    // If this is a leaf node, then it contains one of the input 
182    // characters, print the character and its code from arr[] 
183    if (isLeaf(root)) 
184    { 
185        printf("%c: ", root->data); 
186        printArr(arr, top); 
187    } 
188} 
189  
190// The main function that builds a Huffman Tree and print codes by traversing 
191// the built Huffman Tree 
192void HuffmanCodes(char data[], int freq[], int size) 
193{ 
194   //  Construct Huffman Tree 
195   struct QueueNode* root = buildHuffmanTree(data, freq, size); 
196  
197   // Print Huffman codes using the Huffman tree built above 
198   int arr[MAX_TREE_HT], top = 0; 
199   printCodes(root, arr, top); 
200} 
201  
202// Driver program to test above functions 
203int main() 
204{ 
205    char arr[] = {'a', 'b', 'c', 'd', 'e', 'f'}; 
206    int freq[] = {5, 9, 12, 13, 16, 45}; 
207    int size = sizeof(arr)/sizeof(arr[0]); 
208    HuffmanCodes(arr, freq, size); 
209    return 0; 
210}