哈夫曼编码 | Bowen's Academic Home

问题描述

前缀码：编码的任意前缀不是其他编码。

问题：如何求得编码后二进制串总长最短的前缀码？

形式化定义

输入：

字符数 $n$ 以及各个字符的频数 $F = ⟨ f_{1}, f_{2}, \dots, f_{n} ⟩$

输出：

解析结果唯一的二进制编码方案 $C = ⟨ c_{1}, c_{2}, \dots, c_{n} ⟩$

优化目标：

min \sum_{i = 1}^{n} | c_{i} | f_{i}

其中 $c_{i}$ 为字符 $i$ 的编码二进制串长度。

问题分析

我们可以很容易想到如下策略：

优先处理高频字符
优先处理低频字符

上述两种策略到底哪种是最优方案呢？会不会还有其他更优的方案？

实际上，优先处理低频字符是最优的方案。为什么呢？我们首先来看看带权路径长度的概念。

带权路径长度

假设二叉树中每个叶子结点有一个权值 $w_{i}$ ，到根的路径长度为 $l_{i}$ ，其他结点权值为 $0$ 。则有 $n$ 个叶子结点的树的带权路径长度为

\begin{array}{r} W P L = \sum_{i = 0}^{n - 1} w_{i} l_{i} \end{array}

Huffman 树

带权路径长度达到最小的二叉树即为 Huffman 树。在 Huffman 树中，权值越大的结点离根越近。

构造 Huffman 树

首先构造 $n$ 棵二叉树的森林 $F = {T_{1}, T_{2}, \dots, T_{n}}$ ，每棵二叉树 $T_{i}$ 只有一个带权值为 $w_{i}$ 的根结点。然后重复以下步骤，直到只剩一棵树为止：

在 $F$ 中选两棵根结点权值最小的二叉树，作为左右子树构造一棵新的二叉树，新树的根结点权值等于其左右子树根结点权值之和。
在 $F$ 中删除这两棵二叉树。
把新构造的二叉树加入 $F$ 。

算法代码

结点定义

struct HuffmanNode
{
    int freq; // 频数
    char ch;  // 字符，如果是非叶子结点则为空
    struct HuffmanNode *left;
    struct HuffmanNode *right;
};

初始化 Huffman 树

struct HuffmanNode *initHuffmanTree(map<char, int> &F, vector<struct HuffmanNode> &treeNode)
{
    const int chNum = F.size();
    auto p = F.begin();
    for (int i = 0; i < chNum && p != F.end(); ++i, ++p)
    {
        treeNode[i].ch = p->first;
        treeNode[i].freq = p->second;
        treeNode[i].left = treeNode[i].right = nullptr;
    }
    auto begin = treeNode.begin(), end = begin + chNum;
    while (end != treeNode.end())
    {
        auto lambda = [](struct HuffmanNode &n1,
                         struct HuffmanNode &n2) { return n1.freq < n2.freq; };
        sort(begin, end, lambda);
        end->ch = '\0';
        end->freq = begin->freq + (begin + 1)->freq;
        end->left = &(*begin);
        end->right = &(*(begin + 1));
        begin += 2;
        ++end;
    }
    return &treeNode.at(treeNode.size() - 1);
}

先序遍历

void LDR(HuffmanNode *p,
         string &code,
         map<char, string> &encodeTable)
{
    if (!p->left && !p->right)
    {
        encodeTable[p->ch] = code;
        return;
    }
    if (p->left)
    {
        code.push_back('0');
        LDR(p->left, code, encodeTable);
        code.pop_back();
    }
    if (p->right)
    {
        code.push_back('1');
        LDR(p->right, code, encodeTable);
        code.pop_back();
    }
}

编码

map<char, string> encode(struct HuffmanNode *root)
{
    map<char, string> encodeTable;
    string code = "";
    LDR(root, code, encodeTable);
    return encodeTable;
}

主调函数

int main()
{
    map<char, int> F = {
        {'a', 45},
        {'b', 13},
        {'c', 12},
        {'d', 16},
        {'e', 9},
        {'f', 5}};
    vector<struct HuffmanNode> node(F.size() * 2 - 1);
    auto ans = encode(initHuffmanTree(F, node));
    for (auto &i : ans)
    {
        cout << i.first << ": " << i.second << endl;
    }
}