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

1// C program for Huffman Coding 
2#include <stdio.h> 
3#include <stdlib.h> 
4  
5// This constant can be avoided by explicitly 
6// calculating height of Huffman Tree 
7#define MAX_TREE_HT 100 
8  
9// A Huffman tree node 
10struct MinHeapNode { 
11  
12    // One of the input characters 
13    char data; 
14  
15    // Frequency of the character 
16    unsigned freq; 
17  
18    // Left and right child of this node 
19    struct MinHeapNode *left, *right; 
20}; 
21  
22// A Min Heap:  Collection of 
23// min-heap (or Huffman tree) nodes 
24struct MinHeap { 
25  
26    // Current size of min heap 
27    unsigned size; 
28  
29    // capacity of min heap 
30    unsigned capacity; 
31  
32    // Array of minheap node pointers 
33    struct MinHeapNode** array; 
34}; 
35  
36// A utility function allocate a new 
37// min heap node with given character 
38// and frequency of the character 
39struct MinHeapNode* newNode(char data, unsigned freq) 
40{ 
41    struct MinHeapNode* temp 
42        = (struct MinHeapNode*)malloc
43(sizeof(struct MinHeapNode)); 
44  
45    temp->left = temp->right = NULL; 
46    temp->data = data; 
47    temp->freq = freq; 
48  
49    return temp; 
50} 
51  
52// A utility function to create 
53// a min heap of given capacity 
54struct MinHeap* createMinHeap(unsigned capacity) 
55  
56{ 
57  
58    struct MinHeap* minHeap 
59        = (struct MinHeap*)malloc(sizeof(struct MinHeap)); 
60  
61    // current size is 0 
62    minHeap->size = 0; 
63  
64    minHeap->capacity = capacity; 
65  
66    minHeap->array 
67        = (struct MinHeapNode**)malloc(minHeap-> 
68capacity * sizeof(struct MinHeapNode*)); 
69    return minHeap; 
70} 
71  
72// A utility function to 
73// swap two min heap nodes 
74void swapMinHeapNode(struct MinHeapNode** a, 
75                     struct MinHeapNode** b) 
76  
77{ 
78  
79    struct MinHeapNode* t = *a; 
80    *a = *b; 
81    *b = t; 
82} 
83  
84// The standard minHeapify function. 
85void minHeapify(struct MinHeap* minHeap, int idx) 
86  
87{ 
88  
89    int smallest = idx; 
90    int left = 2 * idx + 1; 
91    int right = 2 * idx + 2; 
92  
93    if (left < minHeap->size && minHeap->array[left]-> 
94freq < minHeap->array[smallest]->freq) 
95        smallest = left; 
96  
97    if (right < minHeap->size && minHeap->array[right]-> 
98freq < minHeap->array[smallest]->freq) 
99        smallest = right; 
100  
101    if (smallest != idx) { 
102        swapMinHeapNode(&minHeap->array[smallest], 
103                        &minHeap->array[idx]); 
104        minHeapify(minHeap, smallest); 
105    } 
106} 
107  
108// A utility function to check 
109// if size of heap is 1 or not 
110int isSizeOne(struct MinHeap* minHeap) 
111{ 
112  
113    return (minHeap->size == 1); 
114} 
115  
116// A standard function to extract 
117// minimum value node from heap 
118struct MinHeapNode* extractMin(struct MinHeap* minHeap) 
119  
120{ 
121  
122    struct MinHeapNode* temp = minHeap->array[0]; 
123    minHeap->array[0] 
124        = minHeap->array[minHeap->size - 1]; 
125  
126    --minHeap->size; 
127    minHeapify(minHeap, 0); 
128  
129    return temp; 
130} 
131  
132// A utility function to insert 
133// a new node to Min Heap 
134void insertMinHeap(struct MinHeap* minHeap, 
135                   struct MinHeapNode* minHeapNode) 
136  
137{ 
138  
139    ++minHeap->size; 
140    int i = minHeap->size - 1; 
141  
142    while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) { 
143  
144        minHeap->array[i] = minHeap->array[(i - 1) / 2]; 
145        i = (i - 1) / 2; 
146    } 
147  
148    minHeap->array[i] = minHeapNode; 
149} 
150  
151// A standard function to build min heap 
152void buildMinHeap(struct MinHeap* minHeap) 
153  
154{ 
155  
156    int n = minHeap->size - 1; 
157    int i; 
158  
159    for (i = (n - 1) / 2; i >= 0; --i) 
160        minHeapify(minHeap, i); 
161} 
162  
163// A utility function to print an array of size n 
164void printArr(int arr[], int n) 
165{ 
166    int i; 
167    for (i = 0; i < n; ++i) 
168        printf("%d", arr[i]); 
169  
170    printf("\n"); 
171} 
172  
173// Utility function to check if this node is leaf 
174int isLeaf(struct MinHeapNode* root) 
175  
176{ 
177  
178    return !(root->left) && !(root->right); 
179} 
180  
181// Creates a min heap of capacity 
182// equal to size and inserts all character of 
183// data[] in min heap. Initially size of 
184// min heap is equal to capacity 
185struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) 
186  
187{ 
188  
189    struct MinHeap* minHeap = createMinHeap(size); 
190  
191    for (int i = 0; i < size; ++i) 
192        minHeap->array[i] = newNode(data[i], freq[i]); 
193  
194    minHeap->size = size; 
195    buildMinHeap(minHeap); 
196  
197    return minHeap; 
198} 
199  
200// The main function that builds Huffman tree 
201struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) 
202  
203{ 
204    struct MinHeapNode *left, *right, *top; 
205  
206    // Step 1: Create a min heap of capacity 
207    // equal to size.  Initially, there are 
208    // modes equal to size. 
209    struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size); 
210  
211    // Iterate while size of heap doesn't become 1 
212    while (!isSizeOne(minHeap)) { 
213  
214        // Step 2: Extract the two minimum 
215        // freq items from min heap 
216        left = extractMin(minHeap); 
217        right = extractMin(minHeap); 
218  
219        // Step 3:  Create a new internal 
220        // node with frequency equal to the 
221        // sum of the two nodes frequencies. 
222        // Make the two extracted node as 
223        // left and right children of this new node. 
224        // Add this node to the min heap 
225        // '$' is a special value for internal nodes, not used 
226        top = newNode('$', left->freq + right->freq); 
227  
228        top->left = left; 
229        top->right = right; 
230  
231        insertMinHeap(minHeap, top); 
232    } 
233  
234    // Step 4: The remaining node is the 
235    // root node and the tree is complete. 
236    return extractMin(minHeap); 
237} 
238  
239// Prints huffman codes from the root of Huffman Tree. 
240// It uses arr[] to store codes 
241void printCodes(struct MinHeapNode* root, int arr[], int top) 
242  
243{ 
244  
245    // Assign 0 to left edge and recur 
246    if (root->left) { 
247  
248        arr[top] = 0; 
249        printCodes(root->left, arr, top + 1); 
250    } 
251  
252    // Assign 1 to right edge and recur 
253    if (root->right) { 
254  
255        arr[top] = 1; 
256        printCodes(root->right, arr, top + 1); 
257    } 
258  
259    // If this is a leaf node, then 
260    // it contains one of the input 
261    // characters, print the character 
262    // and its code from arr[] 
263    if (isLeaf(root)) { 
264  
265        printf("%c: ", root->data); 
266        printArr(arr, top); 
267    } 
268} 
269  
270// The main function that builds a 
271// Huffman Tree and print codes by traversing 
272// the built Huffman Tree 
273void HuffmanCodes(char data[], int freq[], int size) 
274  
275{ 
276    // Construct Huffman Tree 
277    struct MinHeapNode* root 
278        = buildHuffmanTree(data, freq, size); 
279  
280    // Print Huffman codes using 
281    // the Huffman tree built above 
282    int arr[MAX_TREE_HT], top = 0; 
283  
284    printCodes(root, arr, top); 
285} 
286  
287// Driver program to test above functions 
288int main() 
289{ 
290  
291    char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' }; 
292    int freq[] = { 5, 9, 12, 13, 16, 45 }; 
293  
294    int size = sizeof(arr) / sizeof(arr[0]); 
295  
296    HuffmanCodes(arr, freq, size); 
297  
298    return 0; 
299}

1// C++ program for Huffman Coding 
2#include <iostream> 
3#include <cstdlib> 
4using namespace std; 
5  
6// This constant can be avoided by explicitly 
7// calculating height of Huffman Tree 
8#define MAX_TREE_HT 100 
9  
10// A Huffman tree node 
11struct MinHeapNode { 
12  
13    // One of the input characters 
14    char data; 
15  
16    // Frequency of the character 
17    unsigned freq; 
18  
19    // Left and right child of this node 
20    struct MinHeapNode *left, *right; 
21}; 
22  
23// A Min Heap: Collection of 
24// min-heap (or Huffman tree) nodes 
25struct MinHeap { 
26  
27    // Current size of min heap 
28    unsigned size; 
29  
30    // capacity of min heap 
31    unsigned capacity; 
32  
33    // Attay of minheap node pointers 
34    struct MinHeapNode** array; 
35}; 
36  
37// A utility function allocate a new 
38// min heap node with given character 
39// and frequency of the character 
40struct MinHeapNode* newNode(char data, unsigned freq) 
41{ 
42    struct MinHeapNode* temp 
43        = (struct MinHeapNode*)malloc
44(sizeof(struct MinHeapNode)); 
45  
46    temp->left = temp->right = NULL; 
47    temp->data = data; 
48    temp->freq = freq; 
49  
50    return temp; 
51} 
52  
53// A utility function to create 
54// a min heap of given capacity 
55struct MinHeap* createMinHeap(unsigned capacity) 
56  
57{ 
58  
59    struct MinHeap* minHeap 
60        = (struct MinHeap*)malloc(sizeof(struct MinHeap)); 
61  
62    // current size is 0 
63    minHeap->size = 0; 
64  
65    minHeap->capacity = capacity; 
66  
67    minHeap->array 
68        = (struct MinHeapNode**)malloc(minHeap-> 
69capacity * sizeof(struct MinHeapNode*)); 
70    return minHeap; 
71} 
72  
73// A utility function to 
74// swap two min heap nodes 
75void swapMinHeapNode(struct MinHeapNode** a, 
76                    struct MinHeapNode** b) 
77  
78{ 
79  
80    struct MinHeapNode* t = *a; 
81    *a = *b; 
82    *b = t; 
83} 
84  
85// The standard minHeapify function. 
86void minHeapify(struct MinHeap* minHeap, int idx) 
87  
88{ 
89  
90    int smallest = idx; 
91    int left = 2 * idx + 1; 
92    int right = 2 * idx + 2; 
93  
94    if (left < minHeap->size && minHeap->array[left]-> 
95freq < minHeap->array[smallest]->freq) 
96        smallest = left; 
97  
98    if (right < minHeap->size && minHeap->array[right]-> 
99freq < minHeap->array[smallest]->freq) 
100        smallest = right; 
101  
102    if (smallest != idx) { 
103        swapMinHeapNode(&minHeap->array[smallest], 
104                        &minHeap->array[idx]); 
105        minHeapify(minHeap, smallest); 
106    } 
107} 
108  
109// A utility function to check 
110// if size of heap is 1 or not 
111int isSizeOne(struct MinHeap* minHeap) 
112{ 
113  
114    return (minHeap->size == 1); 
115} 
116  
117// A standard function to extract 
118// minimum value node from heap 
119struct MinHeapNode* extractMin(struct MinHeap* minHeap) 
120  
121{ 
122  
123    struct MinHeapNode* temp = minHeap->array[0]; 
124    minHeap->array[0] 
125        = minHeap->array[minHeap->size - 1]; 
126  
127    --minHeap->size; 
128    minHeapify(minHeap, 0); 
129  
130    return temp; 
131} 
132  
133// A utility function to insert 
134// a new node to Min Heap 
135void insertMinHeap(struct MinHeap* minHeap, 
136                struct MinHeapNode* minHeapNode) 
137  
138{ 
139  
140    ++minHeap->size; 
141    int i = minHeap->size - 1; 
142  
143    while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) { 
144  
145        minHeap->array[i] = minHeap->array[(i - 1) / 2]; 
146        i = (i - 1) / 2; 
147    } 
148  
149    minHeap->array[i] = minHeapNode; 
150} 
151  
152// A standard function to build min heap 
153void buildMinHeap(struct MinHeap* minHeap) 
154  
155{ 
156  
157    int n = minHeap->size - 1; 
158    int i; 
159  
160    for (i = (n - 1) / 2; i >= 0; --i) 
161        minHeapify(minHeap, i); 
162} 
163  
164// A utility function to print an array of size n 
165void printArr(int arr[], int n) 
166{ 
167    int i; 
168    for (i = 0; i < n; ++i) 
169        cout<< arr[i]; 
170  
171    cout<<"\n"; 
172} 
173  
174// Utility function to check if this node is leaf 
175int isLeaf(struct MinHeapNode* root) 
176  
177{ 
178  
179    return !(root->left) && !(root->right); 
180} 
181  
182// Creates a min heap of capacity 
183// equal to size and inserts all character of 
184// data[] in min heap. Initially size of 
185// min heap is equal to capacity 
186struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) 
187  
188{ 
189  
190    struct MinHeap* minHeap = createMinHeap(size); 
191  
192    for (int i = 0; i < size; ++i) 
193        minHeap->array[i] = newNode(data[i], freq[i]); 
194  
195    minHeap->size = size; 
196    buildMinHeap(minHeap); 
197  
198    return minHeap; 
199} 
200  
201// The main function that builds Huffman tree 
202struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) 
203  
204{ 
205    struct MinHeapNode *left, *right, *top; 
206  
207    // Step 1: Create a min heap of capacity 
208    // equal to size. Initially, there are 
209    // modes equal to size. 
210    struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size); 
211  
212    // Iterate while size of heap doesn't become 1 
213    while (!isSizeOne(minHeap)) { 
214  
215        // Step 2: Extract the two minimum 
216        // freq items from min heap 
217        left = extractMin(minHeap); 
218        right = extractMin(minHeap); 
219  
220        // Step 3: Create a new internal 
221        // node with frequency equal to the 
222        // sum of the two nodes frequencies. 
223        // Make the two extracted node as 
224        // left and right children of this new node. 
225        // Add this node to the min heap 
226        // '$' is a special value for internal nodes, not used 
227        top = newNode('$', left->freq + right->freq); 
228  
229        top->left = left; 
230        top->right = right; 
231  
232        insertMinHeap(minHeap, top); 
233    } 
234  
235    // Step 4: The remaining node is the 
236    // root node and the tree is complete. 
237    return extractMin(minHeap); 
238} 
239  
240// Prints huffman codes from the root of Huffman Tree. 
241// It uses arr[] to store codes 
242void printCodes(struct MinHeapNode* root, int arr[], int top) 
243  
244{ 
245  
246    // Assign 0 to left edge and recur 
247    if (root->left) { 
248  
249        arr[top] = 0; 
250        printCodes(root->left, arr, top + 1); 
251    } 
252  
253    // Assign 1 to right edge and recur 
254    if (root->right) { 
255  
256        arr[top] = 1; 
257        printCodes(root->right, arr, top + 1); 
258    } 
259  
260    // If this is a leaf node, then 
261    // it contains one of the input 
262    // characters, print the character 
263    // and its code from arr[] 
264    if (isLeaf(root)) { 
265  
266        cout<< root->data <<": "; 
267        printArr(arr, top); 
268    } 
269} 
270  
271// The main function that builds a 
272// Huffman Tree and print codes by traversing 
273// the built Huffman Tree 
274void HuffmanCodes(char data[], int freq[], int size) 
275  
276{ 
277    // Construct Huffman Tree 
278    struct MinHeapNode* root 
279        = buildHuffmanTree(data, freq, size); 
280  
281    // Print Huffman codes using 
282    // the Huffman tree built above 
283    int arr[MAX_TREE_HT], top = 0; 
284  
285    printCodes(root, arr, top); 
286} 
287  
288// Driver program to test above functions 
289int main() 
290{ 
291  
292    char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' }; 
293    int freq[] = { 5, 9, 12, 13, 16, 45 }; 
294  
295    int size = sizeof(arr) / sizeof(arr[0]); 
296  
297    HuffmanCodes(arr, freq, size); 
298  
299    return 0; 
300}

1// C++ program for Huffman Coding 
2#include <bits/stdc++.h> 
3using namespace std; 
4  
5// A Huffman tree node 
6struct MinHeapNode { 
7  
8    // One of the input characters 
9    char data; 
10  
11    // Frequency of the character 
12    unsigned freq; 
13  
14    // Left and right child 
15    MinHeapNode *left, *right; 
16  
17    MinHeapNode(char data, unsigned freq) 
18  
19    { 
20  
21        left = right = NULL; 
22        this->data = data; 
23        this->freq = freq; 
24    } 
25}; 
26  
27// For comparison of 
28// two heap nodes (needed in min heap) 
29struct compare { 
30  
31    bool operator()(MinHeapNode* l, MinHeapNode* r) 
32  
33    { 
34        return (l->freq > r->freq); 
35    } 
36}; 
37  
38// Prints huffman codes from 
39// the root of Huffman Tree. 
40void printCodes(struct MinHeapNode* root, string str) 
41{ 
42  
43    if (!root) 
44        return; 
45  
46    if (root->data != '$') 
47        cout << root->data << ": " << str << "\n"; 
48  
49    printCodes(root->left, str + "0"); 
50    printCodes(root->right, str + "1"); 
51} 
52  
53// The main function that builds a Huffman Tree and 
54// print codes by traversing the built Huffman Tree 
55void HuffmanCodes(char data[], int freq[], int size) 
56{ 
57    struct MinHeapNode *left, *right, *top; 
58  
59    // Create a min heap & inserts all characters of data[] 
60    priority_queue<MinHeapNode*, vector<MinHeapNode*>, compare> minHeap; 
61  
62    for (int i = 0; i < size; ++i) 
63        minHeap.push(new MinHeapNode(data[i], freq[i])); 
64  
65    // Iterate while size of heap doesn't become 1 
66    while (minHeap.size() != 1) { 
67  
68        // Extract the two minimum 
69        // freq items from min heap 
70        left = minHeap.top(); 
71        minHeap.pop(); 
72  
73        right = minHeap.top(); 
74        minHeap.pop(); 
75  
76        // Create a new internal node with 
77        // frequency equal to the sum of the 
78        // two nodes frequencies. Make the 
79        // two extracted node as left and right children 
80        // of this new node. Add this node 
81        // to the min heap '$' is a special value 
82        // for internal nodes, not used 
83        top = new MinHeapNode('$', left->freq + right->freq); 
84  
85        top->left = left; 
86        top->right = right; 
87  
88        minHeap.push(top); 
89    } 
90  
91    // Print Huffman codes using 
92    // the Huffman tree built above 
93    printCodes(minHeap.top(), ""); 
94} 
95  
96// Driver program to test above functions 
97int main() 
98{ 
99  
100    char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' }; 
101    int freq[] = { 5, 9, 12, 13, 16, 45 }; 
102  
103    int size = sizeof(arr) / sizeof(arr[0]); 
104  
105    HuffmanCodes(arr, freq, size); 
106  
107    return 0; 
108} 
109  
110// This code is contributed by Aditya Goel

1edit
2play_arrow
3
4brightness_4
5import java.util.PriorityQueue; 
6import java.util.Scanner; 
7import java.util.Comparator; 
8  
9// node class is the basic structure 
10// of each node present in the Huffman - tree. 
11class HuffmanNode { 
12  
13    int data; 
14    char c; 
15  
16    HuffmanNode left; 
17    HuffmanNode right; 
18} 
19  
20// comparator class helps to compare the node 
21// on the basis of one of its attribute. 
22// Here we will be compared 
23// on the basis of data values of the nodes. 
24class MyComparator implements Comparator<HuffmanNode> { 
25    public int compare(HuffmanNode x, HuffmanNode y) 
26    { 
27  
28        return x.data - y.data; 
29    } 
30} 
31  
32public class Huffman { 
33  
34    // recursive function to print the 
35    // huffman-code through the tree traversal. 
36    // Here s is the huffman - code generated. 
37    public static void printCode(HuffmanNode root, String s) 
38    { 
39  
40        // base case; if the left and right are null 
41        // then its a leaf node and we print 
42        // the code s generated by traversing the tree. 
43        if (root.left 
44                == null
45            && root.right 
46                   == null
47            && Character.isLetter(root.c)) { 
48  
49            // c is the character in the node 
50            System.out.println(root.c + ":" + s); 
51  
52            return; 
53        } 
54  
55        // if we go to left then add "0" to the code. 
56        // if we go to the right add"1" to the code. 
57  
58        // recursive calls for left and 
59        // right sub-tree of the generated tree. 
60        printCode(root.left, s + "0"); 
61        printCode(root.right, s + "1"); 
62    } 
63  
64    // main function 
65    public static void main(String[] args) 
66    { 
67  
68        Scanner s = new Scanner(System.in); 
69  
70        // number of characters. 
71        int n = 6; 
72        char[] charArray = { 'a', 'b', 'c', 'd', 'e', 'f' }; 
73        int[] charfreq = { 5, 9, 12, 13, 16, 45 }; 
74  
75        // creating a priority queue q. 
76        // makes a min-priority queue(min-heap). 
77        PriorityQueue<HuffmanNode> q 
78            = new PriorityQueue<HuffmanNode>(n, new MyComparator()); 
79  
80        for (int i = 0; i < n; i++) { 
81  
82            // creating a Huffman node object 
83            // and add it to the priority queue. 
84            HuffmanNode hn = new HuffmanNode(); 
85  
86            hn.c = charArray[i]; 
87            hn.data = charfreq[i]; 
88  
89            hn.left = null; 
90            hn.right = null; 
91  
92            // add functions adds 
93            // the huffman node to the queue. 
94            q.add(hn); 
95        } 
96  
97        // create a root node 
98        HuffmanNode root = null; 
99  
100        // Here we will extract the two minimum value 
101        // from the heap each time until 
102        // its size reduces to 1, extract until 
103        // all the nodes are extracted. 
104        while (q.size() > 1) { 
105  
106            // first min extract. 
107            HuffmanNode x = q.peek(); 
108            q.poll(); 
109  
110            // second min extarct. 
111            HuffmanNode y = q.peek(); 
112            q.poll(); 
113  
114            // new node f which is equal 
115            HuffmanNode f = new HuffmanNode(); 
116  
117            // to the sum of the frequency of the two nodes 
118            // assigning values to the f node. 
119            f.data = x.data + y.data; 
120            f.c = '-'; 
121  
122            // first extracted node as left child. 
123            f.left = x; 
124  
125            // second extracted node as the right child. 
126            f.right = y; 
127  
128            // marking the f node as the root node. 
129            root = f; 
130  
131            // add this node to the priority-queue. 
132            q.add(f); 
133        } 
134  
135        // print the codes by traversing the tree 
136        printCode(root, ""); 
137    } 
138} 
139  
140// This code is contributed by Kunwar Desh Deepak Singh