-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathhuffman2.cpp
More file actions
163 lines (143 loc) · 3.61 KB
/
Copy pathhuffman2.cpp
File metadata and controls
163 lines (143 loc) · 3.61 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
// C++ program to encode and decode a string using
// Huffman Coding.
#include <bits/stdc++.h>
#define MAX_TREE_HT 256
using namespace std;
// to map each character its huffman value
map<char, string> codes;
// to store the frequency of character of the input data
map<char, int> freq;
// A Huffman tree node
struct MinHeapNode
{
char data; // One of the input characters
int freq; // Frequency of the character
MinHeapNode *left, *right; // Left and right child
MinHeapNode(char data, int freq)
{
left = right = NULL;
this->data = data;
this->freq = freq;
}
};
// utility function for the priority queue
struct compare
{
bool operator()(MinHeapNode* l, MinHeapNode* r)
{
return (l->freq > r->freq);
}
};
// utility function to print characters along with
// there huffman value
void printCodes(struct MinHeapNode* root, string str)
{
if (!root)
return;
if (root->data != '$')
cout << root->data << ": " << str << "\n";
printCodes(root->left, str + "0");
printCodes(root->right, str + "1");
}
// utility function to store characters along with
// there huffman value in a hash table, here we
// have C++ STL map
void storeCodes(struct MinHeapNode* root, string str)
{
if (root==NULL)
return;
if (root->data != '$')
codes[root->data]=str;
storeCodes(root->left, str + "0");
storeCodes(root->right, str + "1");
}
// STL priority queue to store heap tree, with respect
// to their heap root node value
priority_queue<MinHeapNode*, vector<MinHeapNode*>, compare> minHeap;
// function to build the Huffman tree and store it
// in minHeap
void HuffmanCodes(int size)
{
struct MinHeapNode *left, *right, *top;
for (map<char, int>::iterator v=freq.begin(); v!=freq.end(); v++)
minHeap.push(new MinHeapNode(v->first, v->second));
while (minHeap.size() != 1)
{
left = minHeap.top();
minHeap.pop();
right = minHeap.top();
minHeap.pop();
top = new MinHeapNode('$', left->freq + right->freq);
top->left = left;
top->right = right;
minHeap.push(top);
}
storeCodes(minHeap.top(), "");
}
// utility function to store map each character with its
// frequency in input string
void calcFreq(string str, int n)
{
for (int i=0; i<str.size(); i++)
freq[str[i]]++;
}
// function iterates through the encoded string s
// if s[i]=='1' then move to node->right
// if s[i]=='0' then move to node->left
// if leaf node append the node->data to our output string
string decode_file(struct MinHeapNode* root, string s)
{
string ans = "";
struct MinHeapNode* curr = root;
for (int i=0;i<s.size();i++)
{
if (s[i] == '0')
curr = curr->left;
else
curr = curr->right;
// reached leaf node
if (curr->left==NULL and curr->right==NULL)
{
ans += curr->data;
curr = root;
}
}
// cout<<ans<<endl;
return ans+'\0';
}
// Driver program to test above functions
int main()
{
string str = "computerscience";
string encodedString, decodedString;
calcFreq(str, str.length());
HuffmanCodes(str.length());
cout << "Character With there Frequencies:\n";
for (auto v=codes.begin(); v!=codes.end(); v++)
cout << v->first <<' ' << v->second << endl;
for (auto i: str)
encodedString+=codes[i];
cout << "\nEncoded Huffman data:\n" << encodedString << endl;
decodedString = decode_file(minHeap.top(), encodedString);
cout << "\nDecoded Huffman Data:\n" << decodedString << endl;
return 0;
}
// g++ huffman2.cpp -o huffman2.out
// ./huffman2.out
//output
// Character With there Frequencies:
// c 111
// e 01
// i 0010
// m 1000
// n 1001
// o 0011
// p 1100
// r 000
// s 1011
// t 1010
// u 1101
// Encoded Huffman data:
// 11100111000110011011010010001011111001001100111101
// Decoded Huffman Data:
// computerscience