C++でハフマン符号を求めるプログラム

結局C++でも実装しました。 ブログネタないからハフマン符号記事で3つも書いたなんてことはありません

実装

解説はあらかた前の記事で書いたので早速実装を。

#include <iostream>
#include <utility>
#include <string>
#include <map>
#include <queue>
#include <vector>

using namespace std;
class HuffmanNode {
public:
    int weight;
    vector<HuffmanNode> child;
    string symbol;
    HuffmanNode(const string& initSymbol, int initWeight);
    HuffmanNode(const char& initSymbol, int initWeight);
    void addChild(const HuffmanNode &node);
    bool operator<(const HuffmanNode &n) const {
        return weight < n.weight;
    }
    bool operator>(const HuffmanNode &n) const {return weight > n.weight;}
    bool operator==(const HuffmanNode &n) {return weight == n.weight;}
    bool operator!=(const HuffmanNode &n) {return weight != n.weight;}
    bool operator<=(const HuffmanNode &n) {return weight <= n.weight;}
    bool operator>=(const HuffmanNode &n) {return weight >= n.weight;}
    HuffmanNode operator+(HuffmanNode &n) {
        HuffmanNode tmp("", weight + n.weight);
        return tmp;
    }
};
HuffmanNode::HuffmanNode(const string& initSymbol, int initWeight) : symbol(initSymbol), weight(initWeight), child() {}
HuffmanNode::HuffmanNode(const char& initSymbol, int initWeight) : weight(initWeight), child() {
    symbol = initSymbol;
}
void HuffmanNode::addChild(const HuffmanNode &node) {child.push_back(node);}

void count(vector<HuffmanNode> &res, const string& str) {
    map<char, int> counter;
    string::const_iterator s = str.begin();
    while (s != str.end()) {
        if (counter.find(*s) == counter.end()) counter[*s] = 0;
        counter[*s] = counter[*s] + 1;
        ++s;
    }
    int i = 0;
    map<char, int>::iterator it = counter.begin();
    while (it != counter.end()) {
        HuffmanNode hn(it->first, it->second);
        res.push_back(hn);
        ++it;
    }
}
HuffmanNode createHuffmanTree(const vector<HuffmanNode> &tree) {
    priority_queue<HuffmanNode, vector<HuffmanNode>, greater<HuffmanNode>> pq;

    vector<HuffmanNode>::const_iterator it = tree.begin();
    while (it != tree.end()) {
        pq.push(*it);
        ++it;
    }
    while (pq.size() > 1) {
        HuffmanNode a = pq.top();
        pq.pop();
        HuffmanNode b = pq.top();
        pq.pop();

        HuffmanNode parent = a + b;
        parent.addChild(a);
        parent.addChild(b);
        pq.push(parent);
    }
    return pq.top();
}
void HuffmanCoding(const HuffmanNode &tree, map<string, string> &dic, const string& s = "") {
    if (tree.symbol != "") dic[tree.symbol] = s;
    if (tree.child.size() >= 1) HuffmanCoding(tree.child[0], dic, s + "0");
    if (tree.child.size() >= 2) HuffmanCoding(tree.child[1], dic, s + "1");
}

int main() {
    vector<HuffmanNode> res;
    count(res, "Lorem ipsum dolor sit amet, consectetur adipiscing elit");

    HuffmanNode tree = createHuffmanTree(res);

    map<string, string> dic;
    HuffmanCoding(tree, dic);

    map<string, string>::iterator it = dic.begin();
    while(it != dic.end()) {
        cout << it->first << ": " << it->second << endl;
        ++it;
    }
    return 0;
}

JavaScript版との違い

JavaScript版では二分ヒープに関数を持たせることで無理やりHuffmanNodeに対応させました。しかし、C++には演算子オーバーロードが存在するので、比較演算子もろもろをオーバーロードするだけで、HuffmanNodeの優先度付きキューを利用することができ、かなり直感的に書けました。

また、C++には参照渡しがあります。参照渡しを利用することでJavaScriptよりも簡潔になりました。

終わりに

結構、引数や戻り値まわりの書き方が怪しかったです…まだ経験が足りてないのでもう少しC++を書く必要がありますね。