2
\$\begingroup\$

Lately, I have been working on this Huffman algorithm and it is finally done, though I think it is improvable due to the fact that people say you have got to use two priority queues but I ended up just using one, so maybe it is even not correctly implemented.

Code:

#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <fstream>
#include <functional>

class HuffmanCoder{
    struct TreeNode {
        char character;
        unsigned frequency, code;

        TreeNode* left, *right;

        friend bool operator>(const TreeNode& a, const TreeNode& b) {
            return a.frequency > b.frequency;
        }

        TreeNode() = default;
        TreeNode(char chara, int freq)
            : character(chara), frequency(freq), code(0u), left(nullptr), right(nullptr) {}
    } m_root;

    //recursive function that assigns codes for every char in the map passed as a reference in the parameters
    void assignCodes(std::map<char, std::string>& map, const TreeNode& rootNode, unsigned currWord, unsigned depth) {
        if (!rootNode.left && !rootNode.right) {
            std::string s;
            for (auto d = 0u; d < depth; ++d) {
                s.push_back('0' + (currWord & 1));
                currWord >>= 1;
            }
            std::reverse(s.begin(), s.end());
            map[rootNode.character] = std::move(s);
        }
        else {
            assignCodes(map, *rootNode.left, currWord << 1, depth + 1);
            assignCodes(map, *rootNode.right, (currWord << 1) | 1, depth + 1);
        }
    }

public:
    HuffmanCoder() = default;

    std::string encodeMessage(const std::string& message) {
        std::map<char, int> frequencies;
        for (const auto& character : message)
            frequencies[character]++;

        std::priority_queue<TreeNode,std::vector<TreeNode>, std::greater<>> pairs;
        for (auto&& value : frequencies)
            pairs.push({ value.first, value.second });

        //huffman algorithm
        while (pairs.size() > 1) {
            const auto pair1 = pairs.top();
            pairs.pop();
            const auto pair2 = pairs.top();
            pairs.pop();

            TreeNode temp('*', pair1.frequency + pair2.frequency);
            temp.left = new TreeNode(pair1);
            temp.right = new TreeNode(pair2);
            pairs.push(temp);
        }

        m_root = pairs.top();

        std::map<char, std::string> map;
        assignCodes(map, m_root, 0u, 0u);

        std::string ret;
        for (auto&& character : message)
            ret += map[character];      
        return std::move(ret);
    }

    std::string decodeMessage(const std::string& binaryMessage) {
        std::string decodedStr;
        auto temp = m_root;
        for (auto&& character : binaryMessage) {
            if (character == '1')
                temp = *temp.right;
            else 
                temp = *temp.left;

            if (!temp.left && !temp.right) {
                decodedStr += temp.character;
                temp = m_root;
            }
        }
        return std::move(decodedStr);
    }
};

int main() {
    std::ifstream file("text.txt");
    std::string message, line;
    while (std::getline(file, line)) 
        message += line;

    HuffmanCoder hf;
    const auto& a = hf.encodeMessage(message);
    const auto& b = hf.decodeMessage(a);

    std::cout << a << "\n\n" << b;
}

Input for the encoder:

Here's the thing. You said a "jackdaw is a crow."
Is it in the same family ? Yes.No one's arguing that.
As someone who is a scientist who studies crows, I am telling you, specifically, in science, no one calls jackdaws crows.If you want to be "specific" like you said, then you shouldn't either. They're not the same thing.
If you're saying "crow family" you're referring to the taxonomic grouping of Corvidae, which includes things from nutcrackers to blue jays to ravens.
So your reasoning for calling a jackdaw a crow is because random people "call the black ones crows?" Let's get grackles and blackbirds in there, then, too.
Also, calling someone a human or an ape ? It's not one or the other, that's not how taxonomy works.They're both. A jackdaw is a jackdaw and a member of the crow family. But that's not what you said.You said a jackdaw is a crow, which is not true unless you're okay with calling all members of the crow family crows, which means you'd call blue jays, ravens, and other birds crows, too.Which you said you don't.
It's okay to just admit you're wrong, you know ?

Output.

Characters and their binds.

\$\endgroup\$
3
\$\begingroup\$

There's really no need to do all that bit manipulation when you can simply do:

assignCodes(map, *(rootNode.left), currWord * 2, depth + 1);
assignCodes(map, *(rootNode.right), currWord * 2 + 1, depth + 1);

and let the compiler worry about those kinds of "instead of multiplying by 2, shift by 1" optimizations and have it handle it for us. That version (to me at least) is much clearer than the one you previously had.

EDIT: I would also put parenthesis around the expression that the * operator is supposed to dereference to make it clearer as I've done above. A similar syntactical fix needs to be done in decodeMessage() too.

I think you're trying to force move semantics in areas where they aren't necessary. An example is the code snippet below:

std::string ret;
for (auto&& character : message)
    ret += map[character];
return std::move(ret);

There is no reason to have an r-value reference (and consequently moving characters out of the message string) when you're updating the ret string. You're passing in message by const reference so you should not be modifying the message in the function. This loop really should be:

std::string ret;
ret.reserve(message.size()); // reserve memory up front to avoid  repeated allocations
for (const auto& c : message) {
    ret += map[c];
}

This also applies for the similar loop in decodeMessage().

Having std::move to move the return value out of the function may inhibit the compiler from performing RVO (which is even faster than move assignment). Just return the value normally and only add the std::move when you have evidence that the return value is returned by a copy.

There is no need to have this line in the code:

 HuffmanCoder() = default;

The compiler generates the default constructor for you so there's no reason to declare it here.

In your assignCodes function, you're creating a binary representation of the currWord number here:

std::string s;
for (auto d = 0u; d < depth; ++d) {
     s.push_back('0' + (currWord & 1));
     currWord >>= 1;
}
std::reverse(s.begin(), s.end());

I would be inclined to have this as a private member method to do this for me:

std::string numToBin(unsigned num, unsigned depth)
{
    std::string s;
    s.reserve(depth);
    for (unsigned i = 0; i < depth; ++i, num >>= 1){
        s.push_back('0' + (num & 1));
    }
    std::reverse(s.begin(), s.end());
    return s;
}

Now I can just simply call the function inside of assignCodes():

map[rootNode.character] = numToBin(currWord, depth);

You can avoid having to do a string reverse by doing this:

std::string numToBin(unsigned num, unsigned depth)
{
    std::string s;
    s.reserve(depth);
    unsigned bits = sizeof(unsigned) * 8 - 1;
    for (unsigned i = 0, shift = bits; i < depth && shift <= bits; 
                  ++i, --shift){
        s.push_back('0' + ((num & (1 << shift)) >> shift));
    }
    return s;
}

A similar transformation can be done for this code inside of encodeMessage():

std::map<char, int> frequencies;
for (const auto& character : message)
    frequencies[character]++;

std::priority_queue<TreeNode,std::vector<TreeNode>, std::greater<>> pairs;
for (auto&& value : frequencies)
    pairs.push({ value.first, value.second });

Turn that into a function that returns the priority_queue:

std::priority_queue<TreeNode,std::vector<TreeNode>, std::greater<>>
getPairs(const std::string& message)
{
    std::map<char, int> frequencies;
    for (const auto& c : message)
        ++frequencies[c];

    std::priority_queue<TreeNode,std::vector<TreeNode>, std::greater<>> pairs;
    for (const auto& value : frequencies)
        pairs.push(value.first, value.second);

    return pairs;
}

Finally, in your TreeNode() initializer list, you're initializing frequency (which is an unsigned type) using a signed value. If you don't need negative numbers (and you don't), then use only unsigned numbers:

TreeNode(char chara, unsigned freq)
            : character(chara), frequency(freq), code(0), left(nullptr), right(nullptr)

EDIT:

I can't believe I failed to mention this:

Your class dynamically creates Nodes using new but I don't see delete anywhere; as a result, your class will leak all that memory. Use std::unique_ptr to avoid having to deal with memory management issues.

\$\endgroup\$
  • \$\begingroup\$ Oh, I see. I'll edit the answer then. Thanks for the clarification. \$\endgroup\$ – Bizkit Apr 7 '16 at 19:31
  • \$\begingroup\$ Thank you for answering! I just cannot get my head around move semantics so I use it when I feel to. I know this is not good practice but I felt like that would improve my code :/ . Also, what looked interesting since it could potentially speed up my algorithm was avoiding using reverse, however, the code that you put there does not work :P \$\endgroup\$ – Levon Apr 8 '16 at 0:50
  • \$\begingroup\$ @Levon Oops! Silly me... I forgot to add one more shift. I edited my answer :) This is why you should test code before posting it haha but I didn't have a compiler environment to work on at the time. \$\endgroup\$ – Bizkit Apr 8 '16 at 13:25
  • \$\begingroup\$ Are you sure it works? It does since num & (1 << shift) ALWAYS returns 0. I do not really know why it returns 0 every time, does not matter the number or what shift's value is \$\endgroup\$ – Levon Apr 8 '16 at 19:22
  • \$\begingroup\$ Yes, I'm sure it works. I let it run for all 4 billion integers in the unsigned range and it worked correctly. How are you testing the function? What values are you assigning to depth? \$\endgroup\$ – Bizkit Apr 11 '16 at 11:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.