哈夫曼树与哈夫曼编码

字数统计: 3.9k字 | 阅读时长: 19分

2020-08-11

leetcode367, 代码模板118, 信息论15, 基础算法135, 数据结构158

摘要: 二叉哈夫曼树的数组实现，字符串编码解码的应用

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们学习一下二叉哈夫曼树与哈夫曼编码的原理，并给出基于数组实现的代码模板，并用代码模板解决力扣 271. 字符串的编码与解码。

2叉哈夫曼树的建树过程涉及到贪心算法，并且建树过程实际上就是贪心算法的构造性证明。这种贪心算法在一些其他问题中也有应用，可以参考文章贪心-模拟哈夫曼建树过程的合并问题。

$1 哈夫曼树

平衡树插入删除效率高的前提各个节点的访问概率相等, 哈夫曼树在建树过程中考虑了节点的访问概率。

哈夫曼树是 N 叉树，这里讨论的是二叉哈夫曼树。

定义带权路径长度: $WPL = \sum_{i=0}^{n-1}w_{i}l_{i}$ , 其中 n 表示有 n 个叶节点. $w_{i}$ 是叶节点的权，$l_{i}$ 是叶节点的深度，给定数据, 使得 WPL 最小的建树方法, 得到的是哈夫曼树。

哈夫曼树节点的定义

HFNode 是节点, 它的定义如下, 成员为数据, 权, 父节点, 左右子节点的位置。这里用的是数组实现。

using HFType = char;
struct HFNode
{
    HFType data;
    int weight;
    int parent, left, right;
};

哈夫曼树的定义

哈夫曼树的定义如下： build 使用构造算法建树。树用 vector 存储，节点间关系依赖于 parent, left, right 三个字段。

class HuffmanTree
{
public:
    HuffmanTree(){}
    ~HuffmanTree(){}
    build(const vector<HFType>& v, const vector<int>& w, int size);

private:
    vector<HFNode> elem;
    int length;
};

构造算法(贪心):

step1: 权值集合 ${w_{0}, w_{1}, …, w_{n-1}}$。
step2: 森林 $F = {T_{0}, T_{1}, …, T_{n-1}}$。
step3: 新建节点 node，在 F 中选权值最小(min1, min2)的两颗, 作为 node 的左右子树, 合为一棵树, node 的权为 min1 + min2，设置相关节点的关系字段 parent,left,right。
step4: 选中的两颗从 F 中删掉, 将合并后的新树加入 F 中。
step5: 重复 step3,step4 直到 F 中只有一棵树。

最终构造出的树，非叶子节点都有两个子节点，因此初始数据长度为 n，则建树后的节点个数为 $2n-1$，其中 n 个为叶子节点即原始数据，n - 1 个为新建的节点。

构造算法的实现

其中 v 是数据，如果 HFType 为 char，则 v 是字符串，它相当于构造算法中初始的森林，v[0..n-1] 每个点各自是一棵树。

这里用数组实现，根节点的父节点为 0，链式实现参考 k叉哈夫曼树。

void HuffmanTree::build(const vector<HFType>& v, const vector<int>& w)
{
    int size = v.size();
    length = 2 * size;
    // 节点共 size * 2 - 1 个，放在 elem[1..2*size-1] 中
    elem = vector<HFNode>(length);

    int min1, min2;
    int x, y;

    // size 个叶子节点放在 elem[size..2*size-1]
    for(int i = size; i < length; i++)
    {
        elem[i].weight = w[i - size];
        elem[i].data = v[i - size];
        elem[i].parent = elem[i].left = elem[i].right = 0;
    }

    // size - 1 个非叶子节点: elem[1..size-1]
    for(int i = size - 1; i > 0; i--)
    {
        min1 = min2 = INT_MAX;
        x = y = 0;
        for(int j = i + 1; j < length; j++)
        {
            if(elem[j].parent == 0)
            {
                if(elem[j].weight < min1)
                {
                    min2 = min1;
                    min1 = elem[j].weight;
                    x=y;
                    y=j;
                }
                else if(elem[j].weight<min2)
                {
                    min2 = elem[j].weight;
                    x=j;
                }
            }
        }
        elem[i].weight = min1 + min2;
        elem[i].left = x;
        elem[i].right = y;
        elem[i].parent = 0;
        elem[x].parent = i;
        elem[y].parent = i;
    }
}

优先级队列优化建树过程

void HuffmanTree::build(const vector<HFType>& v, const vector<int>& w)
{
    int size = v.size();
    length = 2 * size;
    // 节点共 size * 2 - 1 个，放在 elem[1..2*size-1] 中
    elem = vector<HFNode>(length);

    // size 个叶子节点放在 elem[size..2*size-1]
    priority_queue<PHI, vector<PHI>, greater<PHI>> pq; // 小顶堆
    for(int i = size; i < length; i++)
    {
        elem[i].weight = w[i - size];
        elem[i].data = v[i - size];
        elem[i].parent = elem[i].left = elem[i].right = 0;
        pq.push(PHI(elem[i], i));
    }

    // size - 1 个非叶子节点: elem[1..size-1]
    for(int i = size - 1; i > 0; i--)
    {
        PHI node1 = pq.top();
        pq.pop();
        PHI node2 = pq.top();
        pq.pop();
        int min1 = node1.first.weight;
        int min2 = node2.first.weight;
        int y = node1.second;
        int x = node2.second;
        elem[i].weight = min1 + min2;
        elem[i].left = x;
        elem[i].right = y;
        elem[i].parent = 0;
        elem[x].parent = i;
        elem[y].parent = i;
        pq.push(PHI(elem[i], i));
    }
}

模拟2叉哈夫曼建树的贪心问题

哈夫曼编码

哈夫曼树的应用是哈夫曼编码. 哈夫曼编码（Huffman Coding）是一种根据字符出现的概率对字符进行编码的编码方法，编码加过保存在 vector<HFNode> 中。

如果节点的数据类型(HFType)为 char, 可以视为字符串的哈夫曼编码。

struct HFCode
{
    HFType data; // HFType = char
    string code;
};

哈夫曼树 class HuffmanTree 用 vector<HFNode> 保存树结构, 它有两个行为: 一个是前面提到的建树 build, 另一个就是获取哈夫曼编码 get_code 。

获取字符集的哈夫曼编码

获取字符集的哈夫曼编码就枚举出所有的叶子节点。对每个节点打印出到根节点的路径即可。

这里延续之前写的哈夫曼树的数组实现，链式存储的实现方式参考：k叉哈夫曼树。

vector<HFCode> HuffmanTree::get_code()
{
    int n_leaf = length / 2; // 叶节点个数
    vector<HFCode> result(n_leaf);
    int p, s;
    // [n_leaf..length - 1] 为 elem 中的 n_leaf 个叶节点
    for(int i = n_leaf; i < length; i++)
    {
        result[i - n_leaf].data = elem[i].data;
        result[i - n_leaf].code = "";
        p = elem[i].parent;
        s = i;
        while(p)
        {
            if(elem[p].left == s)
                result[i - n_leaf].code = '0' + result[i - n_leaf].code;
            else
                result[i - n_leaf].code = '1' + result[i - n_leaf].code;
            s = p;
            p = elem[p].parent;
        }
    }
    return result;
}

字符集的哈夫曼编码测试

构造测试数据：

测试结果：

随机测试数据和结果：

$2 哈夫曼编码和解码

在哈夫曼树中增加编码和解码的接口：

1 2	string HuffmanTre::encode(const vector<HFType>& data) vector<HFType> HuffmanTree::decode(const string& seq)

编码

利用字符集和对应的频率建树之后，可以随时获取字符集的编码。有了字符集的编码，就可以对原数据进行编码了。编码的过程类似于查字典：

注：以下代码的查字典的过程可以用哈希表优化

string HuffmanTre::encode(const vector<HFType>& data)
{
    vector<HFCode> hfcode = get_code();
    string result;
    for(const HFType &item: data)
    {
        for(const HFCode &code_info: hfcode)
            if(code_info.data == item)
                result += code_info.code;
    }
    return result;
}

解码

基于以上的哈夫曼树实现的编码，产生的是前缀码，即没有任何码是其它码的前缀，这需要证明。

前缀码可以达到最优的压缩率，这也需要证明。

以上需要证明的内容参考信息论方面的理论，本文不展开。

前缀码的特性可以简化解码过程，如果产生的不是前缀码，在解码的时候可能还要用搜索引擎中常用的基于字典的中文分词的那一套：正向最大匹配算法、逆向最大匹配算法。

因为是前缀码，没有码是其它码的前缀，所以开头的码是没有歧义的，从编码序列开头开始，就可以无歧义地识别出第一个字符，对编码序列的剩余部分，依然可以重复这个过程。

vector<HFType> HuffmanTree::decode(const string& seq)
{
    vector<HFType> data;
    int n = seq.size();
    int iter = 0;
    while(iter < n)
    {
        int node = 1; // 根节点是 1
        while(elem[node].left != 0)
        {
            if(seq[iter] == '0')
                node = elem[node].left;
            else
                node = elem[node].right;
            ++iter;
        }
        data.push_back(elem[node].data);
    }
    return data;
}

$3 测试及完整代码

测试结果

代码 (C++，模板)

#include <string>
#include <vector>
#include <climits>
#include <unordered_map>
#include <iostream>
#include <queue>
#include <functional>

using namespace std;

using HFType = char;

struct HFNode
{
    HFType data;
    int weight;
    int parent, left, right;
    bool operator<(const HFNode& node) const
    {
        return this -> weight < node.weight;
    }
};

struct HFCode
{
    HFType data;
    string code;
};

using PHI = pair<HFNode, int>;

class HuffmanTree
{
public:
    HuffmanTree(){}
    ~HuffmanTree(){}

    void build(const vector<HFType>& v, const vector<int>& w)
    {
        int size = v.size();
        length = 2 * size;
        // 节点共 size * 2 - 1 个，放在 elem[1..2*size-1] 中
        elem = vector<HFNode>(length);

        // size 个叶子节点放在 elem[size..2*size-1]
        priority_queue<PHI, vector<PHI>, greater<PHI>> pq; // 小顶堆
        for(int i = size; i < length; i++)
        {
            elem[i].weight = w[i - size];
            elem[i].data = v[i - size];
            elem[i].parent = elem[i].left = elem[i].right = 0;
            pq.push(PHI(elem[i], i));
        }

        // size - 1 个非叶子节点: elem[1..size-1]
        for(int i = size - 1; i > 0; i--)
        {
            PHI node1 = pq.top();
            pq.pop();
            PHI node2 = pq.top();
            pq.pop();
            int min1 = node1.first.weight;
            int min2 = node2.first.weight;
            int y = node1.second;
            int x = node2.second;
            elem[i].weight = min1 + min2;
            elem[i].left = x;
            elem[i].right = y;
            elem[i].parent = 0;
            elem[x].parent = i;
            elem[y].parent = i;
            pq.push(PHI(elem[i], i));
        }
    }

    vector<HFCode> get_code()
    {
        int n_leaf = length / 2; // 叶节点个数
        vector<HFCode> result(n_leaf);
        int p, s;
        // [n_leaf..length - 1] 为 elem 中的 n_leaf 个叶节点
        for(int i = n_leaf; i < length; i++)
        {
            result[i - n_leaf].data = elem[i].data;
            result[i - n_leaf].code = "";
            p = elem[i].parent;
            s = i;
            while(p)
            {
                if(elem[p].left == s)
                    result[i - n_leaf].code = '0' + result[i - n_leaf].code;
                else
                    result[i - n_leaf].code = '1' + result[i - n_leaf].code;
                s = p;
                p = elem[p].parent;
            }
        }
        return result;
    }

    string encode(const vector<HFType>& data)
    {
        vector<HFCode> hfcode = get_code();
        string result;
        for(const HFType &item: data)
        {
            for(const HFCode &code_info: hfcode)
                if(code_info.data == item)
                    result += code_info.code;
        }
        return result;
    }

    vector<HFType> decode(const string& seq)
    {
        vector<HFType> data;
        int n = seq.size();
        int iter = 0;
        while(iter < n)
        {
            int node = 1; // 根节点是 1
            while(elem[node].left != 0)
            {
                if(seq[iter] == '0')
                    node = elem[node].left;
                else
                    node = elem[node].right;
                ++iter;
            }
            data.push_back(elem[node].data);
        }
        return data;
    }

private:
    vector<HFNode> elem;
    int length;
};


int main()
{
    string data;
    cout << "数据： " << endl;
    cin >> data;
    int n = data.size();
    cout << "数据长度： " << n << endl;
    // 统计字符和频率
    unordered_map<int, int> mapping;
    for(const char& ch: data)
        ++mapping[ch];
    vector<char> v;
    vector<int> w;
    for(const auto &item: mapping)
    {
        v.push_back(item.first);
        w.push_back(item.second);
    }
    int m = v.size();
    cout << "字符数： " << m << endl;
    cout << "(字符，频率)： " << endl;
    for(int i = 0; i < m; ++i)
        cout << v[i] << " " << w[i] << endl;
    HuffmanTree hftree;
    hftree.build(v, w);

    vector<HFCode> result = hftree.get_code();
    cout << endl;
    cout << "编码结果： " << endl;
    for(int i = 0; i < (int)result.size(); ++i)
    {
        HFCode cur = result[i];
        cout << cur.data << " : " << cur.code << endl;
    }

    cout << "原数据的编码序列: " << endl;
    string seq = hftree.encode(vector<HFType>(data.begin(), data.end()));
    cout << seq << endl;
    cout << "解码结果: " << endl;
    vector<HFType> d_seq = hftree.decode(seq);
    cout << string(d_seq.begin(), d_seq.end()) << endl;
}

$4 271. 字符串的编码与解码

请你设计一个算法，可以将一个字符串列表编码成为一个字符串。这个编码后的字符串是可以通过网络进行高效传送的，并且可以在接收端被解码回原来的字符串列表。

1 号机（发送方）有如下函数：

string encode(vector<string> strs) {
  // ... your code
  return encoded_string;
}

2 号机（接收方）有如下函数：

vector<string> decode(string s) {
  //... your code
  return strs;
}

1 号机（发送方）执行：

1	string encoded_string = encode(strs);

2 号机（接收方）执行：

1	vector<string> strs2 = decode(encoded_string);

此时，2 号机（接收方）的 strs2 需要和 1 号机（发送方）的 strs 相同。

请你来实现这个 encode 和 decode 方法。

注意：

1
2
3

因为字符串可能会包含 256 个合法 ascii 字符中的任何字符，所以您的算法必须要能够处理任何可能会出现的字符。
请勿使用 “类成员”、“全局变量” 或 “静态变量” 来存储这些状态，您的编码和解码算法应该是非状态依赖的。
请不要依赖任何方法库，例如 eval 又或者是 serialize 之类的方法。本题的宗旨是需要您自己实现 “编码” 和 “解码” 算法。

算法：哈夫曼编码

将前面实现的哈夫曼树套用过来，并将编码过程的查字典这一步用哈希表优化。

边界处理：

1
2
3

[]
[""]
字符集只有一个字符

代码 (C++)

struct HFNode
{
    char data;
    int weight;
    int parent, left, right;
    bool operator<(const HFNode& node) const
    {
        return this -> weight < node.weight;
    }
};

struct HFCode
{
    char data;
    string code;
};

using PHI = pair<HFNode, int>;

class HuffmanTree
{
public:
    HuffmanTree(){}
    ~HuffmanTree(){}

    void build(const string& v, const vector<int>& w)
    {
        int size = v.size();
        length = 2 * size;
        // 节点共 size * 2 - 1 个，放在 elem[1..2*size-1] 中
        elem = vector<HFNode>(length);

        // size 个叶子节点放在 elem[size..2*size-1]
        priority_queue<PHI, vector<PHI>, greater<PHI>> pq; // 小顶堆
        for(int i = size; i < length; i++)
        {
            elem[i].weight = w[i - size];
            elem[i].data = v[i - size];
            elem[i].parent = elem[i].left = elem[i].right = 0;
            pq.push(PHI(elem[i], i));
        }

        // size - 1 个非叶子节点: elem[1..size-1]
        for(int i = size - 1; i > 0; i--)
        {
            PHI node1 = pq.top();
            pq.pop();
            PHI node2 = pq.top();
            pq.pop();
            int min1 = node1.first.weight;
            int min2 = node2.first.weight;
            int y = node1.second;
            int x = node2.second;
            elem[i].weight = min1 + min2;
            elem[i].left = x;
            elem[i].right = y;
            elem[i].parent = 0;
            elem[x].parent = i;
            elem[y].parent = i;
            pq.push(PHI(elem[i], i));
        }
    }

    vector<HFCode> get_code()
    {
        int n_leaf = length / 2; // 叶节点个数
        vector<HFCode> result(n_leaf);
        int p, s;
        // [n_leaf..length - 1] 为 elem 中的 n_leaf 个叶节点
        for(int i = n_leaf; i < length; i++)
        {
            result[i - n_leaf].data = elem[i].data;
            result[i - n_leaf].code = "";
            p = elem[i].parent;
            s = i;
            while(p)
            {
                if(elem[p].left == s)
                    result[i - n_leaf].code = '0' + result[i - n_leaf].code;
                else
                    result[i - n_leaf].code = '1' + result[i - n_leaf].code;
                s = p;
                p = elem[p].parent;
            }
        }
        return result;
    }

    string encode(const string& data)
    {
        vector<HFCode> hfcode = get_code();
        unordered_map<char, string> hfcode_map;
        for(const HFCode &code_info: hfcode)
            hfcode_map[code_info.data] = code_info.code;
        string result;
        for(const char &item: data)
            result += hfcode_map[item];
        return result;
    }

    string decode(const string& seq)
    {
        string data;
        int n = seq.size();
        int iter = 0;
        while(iter < n)
        {
            int node = 1; // 根节点是 1
            while(elem[node].left != 0)
            {
                if(seq[iter] == '0')
                    node = elem[node].left;
                else
                    node = elem[node].right;
                ++iter;
            }
            data.push_back(elem[node].data);
        }
        return data;
    }

    int charset_size()
    {
        return length / 2;
    }

private:
    vector<HFNode> elem;
    int length;
};


class Codec {
public:
    // Encodes a list of strings to a single string.
    string encode(vector<string>& strs) {
        if(strs.empty()) return "";
        unordered_map<char, int> mapping = stat(strs);
        string v;
        vector<int> w;
        for(const auto &item: mapping)
        {
            v.push_back(item.first);
            w.push_back(item.second);
        }
        hftree.build(v, w);
        string seq;
        if(hftree.charset_size() <= 1)
        {
            p = (char)256;
            for(const string& str: strs)
                seq += str + p;
        }
        else
        {
            p = '2';
            for(const string& str: strs)
                seq += hftree.encode(str) + p;
        }
        return seq;
    }

    // Decodes a single string to a list of strings.
    vector<string> decode(string s) {
        if(s.empty()) return {};
        vector<string> result;
        int n = s.size();
        int left = 0;
        while(left < n)
        {
            int right = left;
            while(right < n && s[right] != p)
                ++right;
            string seq = s.substr(left, right - left);
            string d_seq;
            if(hftree.charset_size() <= 1)
                d_seq = seq;
            else
                d_seq = hftree.decode(seq);
            result.push_back(d_seq);
            left = right + 1;
        }
        return result;
    }

private:
    HuffmanTree hftree;
    char p;

    unordered_map<char, int> stat(const vector<string>& strs)
    {
        unordered_map<char, int> mapping;
        for(const string& str: strs)
        {
            for(const char& ch: str)
                ++mapping[ch];
        }
        return mapping;
    }
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

数信息论