C++ Huffman coder and decoder

Question

I've implemented a Huffman encoder and decoder.

The code is a bit long, I'm worrying if it is easy to grasp it. Also it is my first time using std::shared_ptr<>, so I'm worrying if I used them in a most effective way.

Any comments are welcome.

Huffman.cpp:

#include <memory>
#include <string>
#include <map>
#include <queue>
#include <cmath>
#include <vector>
#include <algorithm>

struct HuffmanTreeNode
{
    unsigned int weight;
    char c;

    std::shared_ptr<HuffmanTreeNode> left = nullptr, right = nullptr;

    friend bool operator<(const HuffmanTreeNode& t1, const HuffmanTreeNode& t2)
    {
        return t1.weight > t2.weight; // to have a min-heap priority queue
    }
};

void get_codes_from_tree(const HuffmanTreeNode& tree, std::map<char, std::string>& codes, std::string current_code="")
{
    if(!tree.left && !tree.right) // leave
        codes[tree.c] = current_code;
    else
    {
        if(tree.left)
            get_codes_from_tree(*tree.left, codes, current_code + "0");
        if(tree.right)
            get_codes_from_tree(*tree.right, codes, current_code + "1");
    }
}

HuffmanTreeNode get_tree_from_codes(std::vector<std::string> codes)
{
    HuffmanTreeNode root;

    std::vector<std::string> left_codes, right_codes;
    for(std::string code: codes)
    {
        if(!code.empty())
        {
            if(code[0] == '0')
                left_codes.push_back(code.substr(1));
            else
                right_codes.push_back(code.substr(1));
        }
    }

    if(!left_codes.empty())
    {
        HuffmanTreeNode l = get_tree_from_codes(left_codes);
        root.left = std::shared_ptr<HuffmanTreeNode>(new HuffmanTreeNode(l));
    }
    if(!right_codes.empty())
    {
        HuffmanTreeNode r = get_tree_from_codes(right_codes);
        root.right = std::shared_ptr<HuffmanTreeNode>(new HuffmanTreeNode(r));
    }

    return root;
}

std::string next_bin(std::string bin)
{
    int k = bin.size() - 1;
    while(bin[k] == '1')
    {
        bin[k] = '0';
        k--;
    }
    if(k == -1)
        bin = "1" + bin;
    else
        bin[k] = '1';
    return bin;
}

// get canonical huffman codes from the sizes of the original huffman codes
std::map<char, std::string> get_canonical_codes(std::vector<int> code_sizes)
{
    int min_size = 0, max_size = 0;
    for(int n: code_sizes)
    {
        if(n > 0 && (min_size == 0 || n < min_size))
            min_size = n;
        if(n > max_size)
            max_size = n;
    }

    std::string bin(min_size, '0');
    std::map<char, std::string> canonical_codes;

    for(int i = min_size; i <= max_size; i++)
    {
        for(int j = 0; j < code_sizes.size(); j++)
        {
            if(code_sizes[j] == i)
            {
                canonical_codes[j] = bin;
                bin = next_bin(bin);
            }
        }
        bin += "0";
    }

    return canonical_codes;
}

int bin_to_dec(std::string bin)
{
    int dec = 0;
    int n = bin.size();
    int k = 1;
    for(int i = 0; i < n; i++)
    {
        if(bin[n-1-i] == '1')
            dec += k;
        k *= 2;
    }
    return dec;
}

// if nb_bits > 1, add 0s at the beginning of the output strings so that its size is nb_bits
std::string dec_to_bin(int dec, int nb_bits=-1)
{
    std::string bin;
    while(dec != 0)
    {
        if(dec % 2 == 0)
        {
            bin = "0" + bin;
            dec /= 2;
        }
        else
        {
            bin = "1" + bin;
            dec = (dec - 1) / 2;
        }
    }

    if(nb_bits > 0 && bin.size() < nb_bits)
    {
        std::string fill(nb_bits - bin.size(), '0');
        return fill + bin;
    }
    return bin;
}

/**
-3 bits: number of bits (between 0 and 7 which represents numbers from 1 to 8) used to represent the size of each code
-256 bits: for each char, 0 if the char has no code and 1 if the char's code size will be sent
-encoded message
-between 0 and 7 blank 1s to fill the last byte
*/
std::string huffman(const std::string& input)
{
    if(input.empty())
        return "";

    // get counts for each char
    std::map<char, unsigned int> weights;
    for(char c: input)
        weights[c] += 1;

    // build priority queue with leaves
    std::priority_queue<HuffmanTreeNode> nodes;
    for(auto kv: weights)
    {
        HuffmanTreeNode node;
        node.c = kv.first;
        node.weight = kv.second;
        nodes.push(node);
    }

    // construct Huffman tree
    while(nodes.size() > 1)
    {
        HuffmanTreeNode node1 = nodes.top();
        nodes.pop();
        HuffmanTreeNode node2 = nodes.top();
        nodes.pop();

        HuffmanTreeNode node_fusion;
        node_fusion.weight = node1.weight + node2.weight;
        node_fusion.left = std::shared_ptr<HuffmanTreeNode>(new HuffmanTreeNode(node1));
        node_fusion.right = std::shared_ptr<HuffmanTreeNode>(new HuffmanTreeNode(node2));

        nodes.push(node_fusion);
    }
    HuffmanTreeNode huffman_tree = nodes.top();

    // get codes from Huffman tree recursively
    std::map<char, std::string> codes;
    get_codes_from_tree(huffman_tree, codes);

    // get canonical Huffman codes
    std::vector<int> code_sizes;
    for(int i = 0; i < 256; i++)
        code_sizes.push_back(codes[(char)i].size());
    codes = get_canonical_codes(code_sizes);

    // no code of length < 8 can contain only ones
    for(int i = 0; i < 256; i++)
    {
        if(code_sizes[i] > 0 && code_sizes[i] < 8 && codes[(char)i] == std::string(codes[(char)i].size(), '1'))
        {
            codes[(char)i] += "0";
            code_sizes[i]++;
        }
    }

    // add header to output
    std::string bin_output;

    int nb_codes = codes.size();
    int longest_code_size = *std::max_element(code_sizes.begin(), code_sizes.end()); // between 1 and 256
    int nb_max_bits_for_code_size = ceil(log2(longest_code_size)); // between 1 and 8, number of bits to represent each code size

    bin_output += dec_to_bin(nb_max_bits_for_code_size - 1, 3);
        // add which code sizes will be sent
    for(int i = 0; i < 256; i++)
    {
        if(code_sizes[i] == 0)
            bin_output += "0";
        else
            bin_output += "1";
    }
        // add code sizes
    for(int i = 0; i < 256; i++)
    {
        if(code_sizes[i] > 0)
            bin_output += dec_to_bin(code_sizes[i] - 1, nb_max_bits_for_code_size);

    }

    // add encoded string to output
    std::string output;
    for(char c: input)
    {
        bin_output += codes[c];
        while(bin_output.size() >= 8)
        {
            output += bin_to_dec(bin_output.substr(0, 8));
            bin_output.erase(0, 8);
        }
    }

    // add blank ones to fill the last byte
    if(!bin_output.empty())
        bin_output += std::string(8 - bin_output.size(), '1');
    output += bin_to_dec(bin_output.substr(0, 8));

    return output;
}


/**
-3 bits: number of bits (between 0 and 7 which represents numbers from 1 to 8) used to represent the size of each code
-256 bits: for each char, 0 if the char has no code and 1 if the char's code size will be sent
-encoded message
-between 0 and 7 blank 1s to fill the last byte
*/
std::string ihuffman(const std::string& input)
{
    std::string bin_input;
    int input_i = 0;
    int n = input.size();

    // header max size: 3+256+256*8 = 2307 bits < 289 bytes
    // get enough data to extract header
    while(input_i < std::min(n, 289))
    {
        bin_input += dec_to_bin((int)(unsigned char)input[input_i], 8);
        input_i++;
    }

    // extract header
    int nb_bits_for_code_size = bin_to_dec(bin_input.substr(0, 3)) + 1; // shift back from 0-7 to 1-8
    bin_input.erase(0, 3);

        // get which codes are sent
    std::map<char, int> code_sizes;
    std::vector<int> sent_code_sizes_indexs;
    for(int i = 0; i < 256; i++)
    {
        if(bin_input[i] == '1')
            sent_code_sizes_indexs.push_back(i);
    }
    bin_input.erase(0, 256);

        // get the sent codes sizes
    int bin_input_i = 0;
    for(int i = 0; i < sent_code_sizes_indexs.size(); i++)
    {
        std::string bin_code_size = bin_input.substr(bin_input_i, nb_bits_for_code_size);
        code_sizes[(char)sent_code_sizes_indexs[i]] = bin_to_dec(bin_code_size) + 1;
        bin_input_i += nb_bits_for_code_size;
    }
    bin_input.erase(0, sent_code_sizes_indexs.size() * nb_bits_for_code_size);

    // get canonical huffman codes
    std::vector<int> code_sizes_vect;
    for(int i = 0; i < 256; i++)
        code_sizes_vect.push_back(code_sizes[(char)i]);
    std::map<char, std::string> codes = get_canonical_codes(code_sizes_vect);

    // build associated huffman tree (without the chars at the leaves)
    std::vector<std::string> code_strings;
    for(auto code: codes)
        code_strings.push_back(code.second);

    std::shared_ptr<HuffmanTreeNode> root(new HuffmanTreeNode(get_tree_from_codes(code_strings)));

    // process the output
    std::string output;

    std::map<std::string, char> decodes;
    for(auto kv: codes)
        decodes[kv.second] = kv.first;

    std::string current_code;
    std::shared_ptr<HuffmanTreeNode> current_node = root;

    while(input_i < n || !bin_input.empty())
    {
        if(input_i < n)
        {
            bin_input += dec_to_bin((int)(unsigned char)input[input_i], 8);
            input_i++;
        }

        while(!bin_input.empty())
        {
            current_code += bin_input[0];
            if(bin_input[0] == '0')
                current_node = current_node->left;
            else
                current_node = current_node->right;
            bin_input.erase(0, 1);

            if(!current_node) // blanc '1' bits at the end
                return output;
            if(!current_node->left && !current_node->right) // leave
            {
                output += decodes[current_code];
                current_code = "";
                current_node = root;
            }
        }
    }

    return output;
}

main.cpp:

#include <iostream>
#include "Huffman.cpp"

int main()
{
    std::cout << ihuffman(huffman("Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua."));
}

Answer 1

Your public interface can be as simple as

std::string huffman(const std::string& input);
std::string ihuffman(const std::string& input);

On that matter, the rest of the functions and even the struct are probably better off as local to the translation unit (i.e. wrapped in an anonymous namespace):

namespace {
    // Code here
}

std::string huffman(const std::string& input) { ... }
std::string ihuffman(const std::string& input) { ... }

---

Also, you are not using a header file. In main.cpp, you wrote:

#include "Huffman.cpp"

This is bad. You almost never want to directly include a source file, only header files. Instead, write a Huffman.h file:

#pragma once

#include <string>

std::string huffman(const std::string& input);
std::string ihuffman(const std::string& input);

Also, note that you usually want to use namespaces:

#pragma once

#include <string>

namespace huffman {
    std::string huffman(const std::string& input);
    std::string ihuffman(const std::string& input);
}

At this point, you might realize that huffman::huffman(myString) looks kind of ridiculous. Indeed, using the namespace brings out that you could name these functions better as encode and decode:

#pragma once

#include <string>

namespace huffman {
    std::string encode(const std::string& input);
    std::string decode(const std::string& input);
}

After these changes, your source file is changed to be:

#include "Huffman.h" // it is best to put the associated header as the first include
// other includes...

// other code...

std::string huffman::encode(const std::string& input) { ... }
std::string huffman::decode(const std::string& input) { ... }

---

struct HuffmanTreeNode
{
    unsigned int weight;
    char c;

    std::shared_ptr<HuffmanTreeNode> left = nullptr, right = nullptr;

    friend bool operator<(const HuffmanTreeNode& t1, const HuffmanTreeNode& t2)
    {
        return t1.weight > t2.weight; // to have a min-heap priority queue
    }
};

First, you do not want to be using std::shared_ptr here. Simple tree-based data structures are better modeled with std::unique_ptr, as unique_ptr is much cheaper than shared_ptr (for one, there's no reference count, and it can also frequently be compiled down to the same code as raw news and deletes). The only time you might want to use a std::shared_ptr for a tree is if you are allowing anyone to take a HuffmanTreeNode and keep it alive — in this case, the shared_ptr prevents the nodes from being deleted too early.

The operator< does not need to be a friend because HuffmanTreeNode is a struct. This also works:

struct HuffmanTreeNode
{
    unsigned int weight;
    char c;

    std::shared_ptr<HuffmanTreeNode> left = nullptr, right = nullptr;
};

bool operator<(const HuffmanTreeNode& t1, const HuffmanTreeNode& t2)
{
    return t1.weight > t2.weight; // to have a min-heap priority queue
}

friend makes it so a function (or a class) can access the private and protected members of a class. Since you declared it as a struct, everything is by default public, so friend is completely unneeded. Also note that a function declared as a friend inside a class is effectively declared in the enclosing namespace, so the two versions above are actually equivalent.

    friend bool operator<(const HuffmanTreeNode& t1, const HuffmanTreeNode& t2)
    {
        return t1.weight > t2.weight; // to have a min-heap priority queue
    }

This is not intuitive for an operator<; it appears to be making the comparison >. This would be better:

bool operator<(const HuffmanTreeNode& t1, const HuffmanTreeNode& t2)
{
    return t1.weight < t2.weight;
}

It might even be better to forgo the operator altogether, as with this operator, you might have !(n1 < n2) && !(n2 < n1), but n1 != n2 because the char is different. This breaks some expectations.

You were defining the operator< for use with a std::priority_queue, but you could just as well define a comparator struct.

---

void get_codes_from_tree(const HuffmanTreeNode& tree, std::map<char, std::string>& codes, std::string current_code="")

A function with the name get_foo should return a value, but this function returns void.

Also, since the operation isn't cheap, and "get" tends to bring to mind a getter, I would instead use the word "compute" or something similar.

I would expect the signature to look more like:

std::map<char, std::string> compute_codes_from_tree(const HuffmanTreeNode& tree);

current_code is an implementation detail and does not need to be on the interface to this function.

Also, note that you take a const HuffmanTreeNode& as your first parameter. You are effectively defining a member function on HuffmanTreeNode. Why not put it there?

struct HuffmanTreeNode
{
    unsigned int weight;
    char c;

    std::shared_ptr<HuffmanTreeNode> left = nullptr, right = nullptr;

    std::map<char, std::string> compute_codes() const;
};

At this point, you might have to define a constructor for HuffmanTreeNode, in which case you might as well make it a full fledged class.

Also note that you have HuffmanTreeNodes which you are treating as entire trees. This tends to be harder to understand; I would instead recommend having a HuffmanTree class which internally has nodes as an implementation detail:

class HuffmanTree
{
    struct Node
    {
        unsigned int weight;
        char c;

        std::shared_ptr<HuffmanTreeNode> left = nullptr, right = nullptr;
    };

    Node root;
public:
    // constructor

    std::map<char, std::string> compute_codes() const;
};

This might be overkill if you only use the HuffmanTree inside the one source file Huffman.cpp, but you definitely want to do this if the class will be used externally to the source file as well.

---

HuffmanTreeNode get_tree_from_codes(std::vector<std::string> codes)

You aren't actually consuming codes; that is, you don't take ownership of the vector (you wouldn't be making a copy anyway). This is a sign that it should be a const&. As a general rule of thumb, make function parameters const& unless you would be making a copy of them, then take them by value:

HuffmanTreeNode get_tree_from_codes(const std::vector<std::string>& codes)

Naturally, this could be a constructor of the HuffmanTree class instead, or possibly a static factory function.

---

std::vector<std::string> left_codes, right_codes;

Try to avoid declaring two variables on the same line. Instead, make them separate declarations:

std::vector<std::string> left_codes;
std::vector<std::string> right_codes;

---

for(std::string code: codes)
{
    if(!code.empty())
    {
        if(code[0] == '0')
            left_codes.push_back(code.substr(1));
        else
            right_codes.push_back(code.substr(1));
    }
}

It tends to improve readability to put a space between for, if, etc and the opening ( (like so: for (), although it is a matter of style.

for(std::string code: codes)

This copies every string in codes, at the very least write for (const std::string& code : codes).

Even better, use a standard algorithm. In general, whenever you write a for loop, especially a for each loop, look for a standard algorithm.

In this case, std::partition comes to mind (this would make it so that you would take codes by value, as it modifies the range):

auto middle = std::partition(codes.begin(), codes.end(), [](const auto& code) {
    return code[0] == '0';
});

Then to create left_codes and right_codes:

std::vector<std::string> left_codes(codes.begin(), middle);
std::vector<std::string> right_codes(middle, codes.end());

Removing the first char could be done with std::transform.

---

root.left = std::shared_ptr<HuffmanTreeNode>(new HuffmanTreeNode(l));

Use std::make_shared. Not only does it avoid potential problems with memory leaks, it also is more efficient because it can declare the reference count in the same block of memory as the allocated object:

 root.left = std::make_shared<HuffmanTreeNode>(l);

Also note that l is a bad name for a variable:

1l

Both 1 and l and I look similar in some fonts, and you can avoid it by using a more descriptive name such as left.

About the memory leak, IIRC, the following code could leak (before C++17):

f(std::shared_ptr<Type>{ new Type }, some_function());

Basically, the compiler is allowed to order the assembly such that the following happens (psuedocode):

auto* type = new Type
auto result = some_function()
auto ptr = std::shared_ptr<Type>{ type }
f(ptr, result)

If some_function() throws, then you leak memory.

---

std::string huffman(const std::string& input)
{
   ...
}

This function is really big. It's 97 lines long. Break it up into smaller functions. Notice how you have comments for several small sections of code? Those are ideal for turning into functions. Yes, you will have many functions, but the readability greatly improves.

However, many of your "functions" can be replaced with standard algorithms.