算法 & 数据结构——霍夫曼编码

霍夫曼编码_简介

上周一个尝试入坑C++的朋友说, 打算用C++写一个霍夫曼编码, 用于压缩JPEG?

他吐槽C++要自己delete很麻烦. 很多人对C++都有这个误解, 主要原因是, 大多数人并不知道RAII, 更不知道怎么用RAII. 很多情况下, 是不需要自己写一堆delete的. 内存控制并不是C++的难点, 这更应该算是逻辑问题. 因为用任何语言去实现内存管理相关的功能, 都会面临这个问题. C++的难点应该是泛型/多范式/元编程/缺少高级标准库/语言自身的复杂度/(省略N条...).

以下是C++实现霍夫曼编码(也不知道这是不是霍夫曼编码, 毕竟已经很多年没听过这个词了), 需要手写delete的地方非常少, 只有两行, 而需要手动释放内存的地方压根就没有.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <fstream>
#include <memory>
#include <vector>
#include <string>
#include <limits>
#include <queue>
#include <tuple>
#include <list>

#define SAFE_DELETE(p)          { delete p; p = nullptr; }
#define CHECK_RET(cod, ret)     { if (cod) return (ret); }

template <class T>
struct Node {
    Node(): lchild(nullptr), rchild(nullptr), weight(0), value(T())
    { }

    ~Node()
    {
        SAFE_DELETE(lchild);
        SAFE_DELETE(rchild);
    }

    size_t GetHeight() const
    {
        auto lh = lchild != nullptr ? lchild->GetHeight() : 0;
        auto rh = rchild != nullptr ? rchild->GetHeight() : 0;
        return std::max(lh, rh) + 1;
    }

    T value;
    Node * lchild;
    Node * rchild;
    size_t weight;
};

template <class T>
class HuffmanTree {
public:
    using Node_t = Node<T>;

    bool Init(const std::string & fname)
    {
        std::ifstream ifile(fname);
        return Init(ifile);
    }

    bool Init(std::ifstream & ifile)
    {
        CHECK_RET(!ifile, false);
        std::list<Node_t*> list;
        size_t w; T v;
        while (ifile >> w >> v)
        {
            Node_t *node = new Node_t();
            list.push_back(node);
            node->weight = w;
            node->value = v;
        }
        return Init(list);
    }

    const T & Translate(const std::string & coding) const
    {
        auto node = _root.get();
        for (const auto & code : coding)
        {
            if (code == '0')
            {
                node = node->lchild;
            }
            else if (code == '1')
            {
                node = node->rchild;
            }
        }
        return node->value;
    }

    std::vector<T> Translate(const std::vector<std::string> & codings) const
    {
        std::vector<T> result;
        for (const auto & coding : codings)
        {
            result.push_back(Translate(coding));
        }
        return std::move(result);
    }

    void Print(std::ostream & os) const
    {
        if (!IsEmpty())
        {
            std::queue<Node_t *> queue;
            queue.push(_root.get());
            while (!queue.empty())
            {
                auto node = queue.front();
                queue.pop();

                os  << "node: " << node << ", "
                    << "value: " << node->value << ", "
                    << "weight: " << node->weight << ", ";

                if (node->lchild != nullptr)
                {
                    os << "lchild: " << node->lchild << ", ";
                    queue.push(node->lchild);
                }

                if (node->rchild != nullptr)
                {
                    os << "rchild: " << node->rchild << ", ";
                    queue.push(node->rchild);
                }
                os << std::endl;
            }
        }
    }

    bool IsEmpty() const
    {
        return nullptr == _root;
    }

private:
    bool Init(std::list<Node_t *> & list)
    {
        CHECK_RET(list.size() == 0, false);
        if (list.size() == 1)
        {
            _root.reset(list.front());
        }
        else
        {
            auto[first, second] = MaxPair(list);
            auto parent = new Node_t();
            parent->weight = (*first)->weight 
                            + (*second)->weight;
            parent->rchild = *second;
            parent->lchild = *first;
            list.push_back(parent);
            list.erase(second);
            list.erase(first);
            return Init(list);
        }
        return !IsEmpty();
    }

    std::tuple<
        typename std::list<Node_t *>::iterator,
        typename std::list<Node_t *>::iterator>
    MaxPair(std::list<Node_t *> & list)
    {
        auto first = std::next(list.begin(), 0);
        auto second = std::next(list.begin(), 1);
        
        if ((*first)->weight < (*second)->weight)
        {
            std::swap(first, second);
        }

        for (auto it = std::next(list.begin(), 2); it != list.end(); ++it)
        {
            if ((*it)->weight > (*first)->weight)
            {
                second = first;
                first = it;
            }
            else if ((*it)->weight > (*second)->weight)
            {
                second = it;
            }
        }
        return { first, second };
    }

private:
    std::unique_ptr<Node_t> _root;
};

int main()
{
    HuffmanTree<int> tree;
    tree.Init("huffman.txt");

    std::cout << "----tree----" << std::endl;
    tree.Print(std::cout);
    
    std::cout << "----coding----" << std::endl;
    std::cout << "code: 01 value: " << tree.Translate("01") << std::endl;
    std::cout << "code: 001 value: " << tree.Translate("001") << std::endl;
    std::cout << "code: 0001 value: " << tree.Translate("0001") << std::endl;
    std::cout << "code: 0000 value: " << tree.Translate("0000") << std::endl;
    std::cin.get();
    return 0;
}