-
Notifications
You must be signed in to change notification settings - Fork 0
/
huffmantree.h
130 lines (101 loc) · 2.61 KB
/
huffmantree.h
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
#ifndef HUFFMANTREE_H
#define HUFFMANTREE_H
#include <bits/stdc++.h>
#include "readwrite.h"
using namespace std;
vector<int> freq(256, 0);
void CountFreq(vector<uint8_t> arr, int size)
{
for (int i = 0; i < size; i++)
{
freq[int(arr[i])]++;
}
}
class TreeNode
{
public:
int pixel;
int freq;
//int width;
//int hight;
TreeNode *left;
TreeNode *right;
TreeNode(int data, int frequency)
{
pixel = data;
freq = frequency;
left = right = NULL;
}
};
class Compare
{
public:
bool operator()(TreeNode *l, TreeNode *r)
{
return l->freq > r->freq;
}
};
TreeNode *generateTree(priority_queue<TreeNode *, vector<TreeNode *>, Compare> pq)
{
// We keep on looping till
// only one node remains in
// the Priority Queue
while (pq.size() != 1)
{
TreeNode *left = pq.top();
pq.pop();
TreeNode *right = pq.top();
pq.pop();
TreeNode *node = new TreeNode(-1, left->freq + right->freq);
node->left = left;
node->right = right;
pq.push(node);
}
return pq.top();
}
void storeCodes(TreeNode *root, map<int, string> &codes, string top)
{
if (root->pixel != -1)
codes[root->pixel] = top;
if (root->left != NULL)
storeCodes(root->left, codes, top + "0");
if (root->right != NULL)
storeCodes(root->right, codes, top + "1");
}
map<int, string> HuffmanCodes(vector<int> freq)
{
priority_queue<TreeNode *, vector<TreeNode *>, Compare> pq;
for (int i = 0; i < 256; ++i)
if (freq[i] > 0)
pq.push(new TreeNode(i, freq[i]));
TreeNode *root = generateTree(pq);
string top = "";
map<int, string> codes;
storeCodes(root, codes, top);
return codes;
}
map<string, int> InverseCode(const map<int, string> encTable)
{
map<string, int> invTable;
//Constructing an inverse table for the coded table
for (auto it = encTable.begin(); it != encTable.end(); it++)
invTable[it->second] = it->first;
return invTable;
}
vector<uint8_t> decode(const string bits, map<string, int> &invTable, const int width, const int height)
{
string temp = "";
int x = 0;
vector<uint8_t> newimg;
for (int i = 0; i < bits.size(); i++) //making the origin data
{
temp += bits[i];
if (invTable.count(temp))
{
newimg.push_back(invTable[temp]);
temp = "";
}
}
return newimg;
}
#endif // HUFFMANTREE_H