Skip to main content
edited tags
Link
200_success
  • 144.2k
  • 22
  • 188
  • 473
deleted 11 characters in body
Source Link
BCdotWEB
  • 11.3k
  • 2
  • 27
  • 45

Thanks.

Thanks.

Source Link
Levon
  • 295
  • 1
  • 2
  • 9

Huffman algorithm implementation in C++

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.

Thanks.