I can't recognize that as huffman coding at all, so there's no advice I can give except to try implementing the actual huffman coding algorithm.
Last edited on
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
|
class Node
{
protected:
unsigned int weight{0};
std::shared_ptr<Node> left, right;
public:
virtual ~Node() = default;
virtual bool isLeaf() const = 0;
unsigned int getWeight() const {
return weight;
}
shared_ptr<Node> getLeft() const {
return left;
}
shared_ptr<Node> getRight() const {
return right;
}
};
class InternalNode : public Node {
public:
InternalNode(const std::shared_ptr<Node>& l, const std::shared_ptr<Node>& r) {
left = l;
right = r;
weight = l->getWeight() + r->getWeight();
}
~InternalNode() override = default;
bool isLeaf() const override {return false;}
};
class LeafNode : public Node {
public:
LeafNode(char d, int w) {
data = d;
weight = w;
left = right = nullptr;
}
~LeafNode() override = default;
bool isLeaf() const override {return true;}
unsigned char getData() const {return data;}
private:
unsigned char data;
};
bool cmp(const std::shared_ptr<Node> &n1, const std::shared_ptr<Node> &n2) {
return n1->getWeight() > n2->getWeight();
}
class HuffmanTree {
public:
Huffman() = default;
explicit Huffman(const map<unsigned char, unsigned int>& frequencyTable) {
std::priority_queue<std::shared_ptr<Node>, std::vector<std::shared_ptr<Node>>, decltype(&cmp)> pq(&cmp);
for (auto& e : frequencyTable) {
pq.push(std::make_shared<LeafNode>(e.first, e.second));
}
while (pq.size() != 1) {
std::shared_ptr<Node> left = pq.top();
pq.pop();
std::shared_ptr<Node> right = pq.top();
pq.pop();
std::shared_ptr<Node> parent = std::make_shared<InternalNode>(left,right);
pq.push(parent);
}
root = pq.top();
std::vector<bool> code;
encode(root, code);
}
private:
std::shared_ptr<Node> root;
std::map<unsigned char, std::vector<bool>> codeTable;
void encode(const std::shared_ptr<Node> &n, std::vector<bool>& code); //function from my originalpost
};
| |
Is there another way of doing it?
Last edited on
How does this compile?
std::map<unsigned char, std::vector<bool> codeTable;
Oops, my bad, forgot the bracket when transcribing.
I fixed the error btw, I had to make local copies of the passed in vector.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
void HuffmanTree::encode(const shared_ptr<Node> &n, const std::vector<bool>& code) {
if (n->getLeft() != nullptr) {
std::vector<bool> leftCode = code;
leftCode.push_back(false);
encode(n->getLeft(), leftCode);
}
if (n->getRight() != nullptr) {
std::vector<bool> rightCode = code;
rightCode.push_back(true);
encode(n->getRight(), rightCode);
}
if (n->isLeaf()) {
codeTable[std::dynamic_pointer_cast<LeafNode>(n)->getData()] = code;
}
}
| |
Last edited on