jpeg/huffman.hpp at master · bjohnsonfl/jpeg · GitHub

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
//
//  huffman.hpp
//  jpeg
//
//  Created by Blake Johnson on 9/16/19.
//  Copyright © 2019 Blake Johnson. All rights reserved.
//

#ifndef huffman_hpp
#define huffman_hpp

#include <stdio.h>
#include <string>
#include <unordered_map>


#include "binaryTree.hpp"


typedef std::unordered_map<std::string,int> map;
typedef std::unordered_map<int,std::string> codeMap;

struct huffNode{

    int symbol;
    double prob;
    std::string code;
    //BinaryTree<int> tree = BinaryTree<int>();

    huffNode(){
        symbol = 0;
        prob = 0.0;
        code = "";
    }

    huffNode(int symbol){
        this->symbol = symbol;
        prob = 0.0;
        code = "";
    }

    huffNode(int symbol, int prob){
        this -> symbol = symbol;
        this -> prob = prob;
        code = "";
    }

    huffNode(int symbol, float prob, std::string code){
        this -> symbol = symbol;
        this -> prob = prob;
        this -> code = code;
    }

};

//When creating the min heap, we use a priority queue with a comparison of each symbols probability
class comparator{
public:

    bool operator() (const huffNode& lhs, const huffNode& rhs) const
    {
        return lhs.prob > rhs.prob;
    }
    bool operator() ( BinaryTree<huffNode>& lhs,  BinaryTree<huffNode>& rhs) const
    {

        return (lhs.getRoot())->data.prob > (rhs.getRoot())->data.prob;

    }
    bool operator() ( BinaryTree<huffNode>* lhs,  BinaryTree<huffNode>* rhs) const
    {

        return (lhs->getRoot())->data.prob > (rhs->getRoot())->data.prob;

    }
};

/*
 take in a string.

 (optional) parse string into 8 bit values

 store values into a map and count the number of values

 create an array of structures that hold the symbol, the prob, and the code

 build the huffman tree

 traverse the huffman tree to the leafs to create the codes

 create a map of symobols to codes

 encode a string

 decode a string

 */

class Huffman{

private:
    std::string rawData;
    std::string encodedData;
    std::string uncodedData;
    int numOfSymbols;
    //std::priority_queue<huffNode, std::vector<huffNode>, comparator> minHeap;
    std::priority_queue<BinaryTree<huffNode> *, std::vector<BinaryTree<huffNode>* > , comparator> minHeap;
    BinaryTree<huffNode> huffmanTree;
    codeMap dictionary;
    map decodeDictionary;

public:
    Huffman(){numOfSymbols = 0;
        rawData = "";
        encodedData = "";
        uncodedData = "";
    };
    //wrapper function to start compression of input string
    //counts occurences and calculates probabilities of symbols


    void compress (std::string data) {compress(data, 0);};
    void compress (std::string data, int bits);


    void parseBits (int bits);  //if the string is binary, parse the number of desired bits to create symbols
    void createTree();
    bool generateCodes(BinaryTreeNode<huffNode> * node, std::string code);
    void encodeString();

    void decodeString (std::string codedString); //for debugging purposes. Would need a way to take in huffman codes for any random coded string

    void postOrder (BinaryTreeNode<huffNode> * node){
        if(node != NULL){
            postOrder(node -> left);
            postOrder(node -> right);
            std::cout << node -> data.prob << " ";

        }
    }
};

/*
 test data

 std::string str = " 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2  2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 6 6 6 6 6 6 5 5 5 5";

 5 0.04
 6 0.06
 3 0.1
 4 0.1
 2 0.3
 1 0.4


 */

#endif /* huffman_hpp */