线性时间复杂度下实现Huffman编码

July 25, 2021

2193 views

3122 words

Huffman编码作为一种无损数据压缩的权编码，在信息通信等领域有重要应用。在传统算法教材以及网络文章上介绍Huffman编码的实现多在$O(n\log{n})$时间复杂度下使用堆排序实现。然而，对于Huffman编码问题，存在一种$O(n)$的做法构建，本文就这种方法进行介绍。

传统Huffman编码的实现

重编码-Huffman树WPL问题

题目描述有一篇文章，文章包含$n$ 种单词，单词的编号从$1$至 $n$，第$i$种单词的出现次数为$w_{i}$...

如上博文所述，可以观察到，对于Huffman编码的实现，一个最为关键的步骤其实是对可能出现的字符集按照频率从大到小进行排序，从而使用贪心的思想构建Huffman树。一个经典的实现方式是采用堆排序的方式，通过构建一个二叉堆实现自底向上地更新累加权重，从而实现WPL最优。

事实上，若所给的字符集已经按照出现频率进行排列，是有时间更优的方式构建Huffman树的。那么，问题就来到了如何更快地进行排序上。

更快的排序方式

要实现更快的排序，不妨考虑不基于比较的排序算法进行排序？

基数排序

基数排序（Radix Sort）与快速排序不同，是一种非比较的排序算法，本质上属于一种特殊的桶排序，将桶的范围缩小...

从以上提及的文章中介绍的基数排序来看，我们可以用$O(kn)$的时间复杂度来完成对字符集的排序。

的确，基数排序的时间复杂度并非为$O(n)$，也有可能造成算法整体时间复杂度的退化，但实际应用过程中，若合适地选取基数排序所使用的进制，算法是可以在接近$O(n)$的时间复杂度下完成任务的。

再言之，不基于比较的排序算法还有很多，在可接受的情况下是完全可以牺牲空间复杂度换取更优的时间复杂度的。

用$O(n)$的时间复杂度实现Huffman编码

首先，我们需要初始化两个队列A与B，其中A填入待编码字符集（按照词频从小到大排列）执行以下操作：

从A与B两个队列队首中选取频率最小的两个节点出队（为空则跳过，从另一队列中取）。
将二者合并作为一个虚节点放入队列B中（第一个出队的作为左子节点，第二个作为右子节点）。
重复以上步骤，直到两个队列中只有一个节点，算法结束。

由此，我们完成了自顶向下构建Huffman树的过程，所剩下的节点即可展开为一颗自顶向下的Huffman树。可以很容易发现，算法时间复杂度为$O(n)$，但是若前置的排序算法时间复杂度过高，会造成算法整体时间复杂度退化。

参考代码

#include <bits/stdc++.h>
using std::vector;
using std::pair;
using std::queue;

template<typename T>
class Node {
public:
    T value;
    char code;
    Node *left, *right;
    
    Node(T value, char code): value(value), code(code) {};
    Node(T value, Node* left, Node* right): value(value), left(left), right(right) {}; 
};

queue<Node<int> *> a, b;

int main() {
    vector<pair<int, char>> demo_data = {{1, 'A'}, {22, 'B'}, {13, 'E'}, {245, 'D'}};
    
    /*
        For demostration, not using O(n) sort algorithm.
        Can be easily switched by changing the implementation here.
    */
    sort(demo_data.begin(), demo_data.end());

    for (auto x : demo_data) {
        Node<int> *element = new Node<int>(x.first, x.second);
        a.push(element);
    }

    while (a.size() + b.size() > 1) {
        Node<int> *first, *second;
        if (!a.empty() && !b.empty() && a.front()->value < b.front()->value) {
            first = a.front();
            a.pop();
        } else if (a.empty()) {
            first = b.front();
            b.pop();
        } else if (b.empty()) {
            first = a.front();
            a.pop();
        } else {
            first = b.front();
            b.pop();
        }

        if (!a.empty() && !b.empty() && a.front()->value < b.front()->value) {
            second = a.front();
            a.pop();
        } else if (a.empty()) {
            second = b.front();
            b.pop();
        } else if (b.empty()) {
            second = a.front();
            a.pop();
        } else {
            second = b.front();
            b.pop();
        }
        // Redundant code to show the logic within. :D

        Node<int> *merged = new Node<int>(first->value + second->value, first, second);
        b.push(merged);
    }

    Node<int> *ans = b.empty() ? a.front() : b.front(); // That's the answer!

    return 0;
}