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

۳۰۹ بازدید
آخرین به‌روزرسانی: ۱۰ تیر ۱۴۰۲
زمان مطالعه: ۸ دقیقه
کدگذاری هافمن (Huffman Coding) برای ورودی های مرتب — راهنمای کاربردی

پیش از این، در مطلب «الگوریتم هافمن (Huffman Coding) -- به زبان ساده»، الگوریتم هافمن به طور کامل مورد بررسی قرار گرفت و پیاده‌سازی آن نیز در زبان‌های برنامه‌نویسی گوناگون انجام شد. پیچیدگی زمانی الگوریتم مورد بررسی در مطلب بیان شده، از درجه (O(nLogn است. اگر آرایه ورودی مرتب شده باشد (با مرتبه تکرار غیرنزولی)، می‌توان کد هافمن را با پیچیدگی زمانی از درجه (O(n تولید کرد. در ادامه، روش کدگذاری هافمن از درجه (O(n برای آرایه مرتب ارائه و پیاده‌سازی آن در زبان‌های برنامه‌نویسی ++C و C انجام شده است.

997696
  1. دو صف خالی بساز.
  2. یک گره برگ برای هر کاراکتر یکتا بساز و آن را به اولین صف با درجه تکرار غیر نزولی اضافه کن. به صورت مقدماتی، دومین صف خالی است.
  3. دو گره با کمترین تکرار را با بررسی جلوی هر دوی صف‌ها از صف خارج کن. گام‌های زیر را دو بار تکرار کن:
    • اگر صف دوم خالی است، از صف اول گره را خارج کن.
    • اگر صف اول خالی است، از صف دوم گره را خارج کن.
    • در غیر این صورت، جلوی هر دو صف را بررسی کن و کمترین مقدار را از صف خارج کن.
  4. یک گره داخلی جدید با تکراری برابر با مجموعه تکرار دو گره را بساز. اولین گره خارج شده از صف را به عنوان فرزند سمت چپ و دومین گره خارج شده از صف را به عنوان فرزند سمت راست قرار بده. این گره را در دومین صف قرار بده.
  5. گام ۳ و ۴ را تا زمانی که بیش از یک گره در صف قرار دارد تکرار کن. گره باقی‌مانده گره ریشه و درخت کامل است.

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

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

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

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} 

خروجی قطعه کدهای بالا، برای ورودی‌های {'a', 'b', 'c', 'd', 'e', 'f'} با تعداد تکرار  5,9,12,13,16,45{5, 9, 12, 13, 16, 45} به صورت زیر است.

f: 0
c: 100
d: 101
a: 1100
b: 1101
e: 111

پیچیدگی زمانی این روش از درجه (O(n است. اگر ورودی مرتب شده نباشد، باید آن را پیش از پردازش، مرتب‌سازی کرد.

مرتب‌سازی می‌تواند با استفاده از «مرتب‌سازی هرمی» (Heap-Sort) یا «مرتب‌سازی ادغامی» (Merge-Sort) انجام شود که هر دو از درجه (Theta(nlogn هستند. بنابراین، پیچیدگی زمانی کلی، برای ورودی مرتب نشده از درجه (O(nlogn خواهد بود.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۰ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *