Huffman-encoding

Posted on Edited on In , , , , , , Views: Word count in article: 948 Reading time ≈ 3 mins.

刚学还热乎的算法

  • 哈夫曼（Huffman）编码

Prefix Codes (前缀码)

考虑使用不同长度的 bit string 来编码不同的字符串，其中一种保证没有一个 bit string 对应两个及以上的字符串的编码叫做 prefix codes（前缀码）。
prefix code 可以通过二叉树来表示，每一个树中的叶节点的标签即为对应的字符串，而一条连接 left child 的边的标签被指定为 ，对应的连接 right child 的边的标签为 。那么，一个字符串对应的 bit string 为从根到该叶节点的唯一通路上的边的标签的序列。

例子

Kenneth Rosen - Discrete Mathematics and Its Applications - 8th edition - Chapter 11.2 - Figure 5

对于这棵树，其中 对应的编码分别是

Huffman Coding

那么哈夫曼编码是什么呢？其实是为了解决生成一颗比较”好”的 Prefix Tree，来实现更短的 bit string 编码长度，哈夫曼编码是一种基本的数据压缩算法，通过压缩编码长度，我们便能减小压缩文件的大小。

原理

先给出算法的伪代码

Kenneth Rosen - Discrete Mathematics and Its Applications - 8th edition - Chapter 11.2 - Algorithm2

这是一个贪心的算法，其通过某个字符串出现的频率（概率）来建立前缀树，容易知道，我们如果让出现频率越高的字符的编码越短，那么压缩比自然就越大，而这个算法实现中，是从叶节点建起，也就是每次将两子树合并到一个新的根节点上，那么可以知道，因为越先合并的节点，在树的越深的层，也就意味着更长的编码，那么反向思维，我们应该先从出现频率低的字符开始。由此来保证每次两个子树的总权重（出现频率）和是最小的，于是可以获得一个全局最优。

这有一个值得注意的问题：这里给出的算法并未指定存在两子树权重相等时的行为，在实际实现中应当指定，但这并不会影响编码效果。

M-ary Huffman Coding（m 叉树的 huffman Coding）

m 叉树的的算法与二叉树并不完全相同

m-ary

其中主要差别在于对于 -ary， 个符号的编码体系，在初始步骤中，由权重最小的单个顶点组成的 棵树被组合成一棵以这些顶点为叶子的有根树。

根据定义: A vertex of a rooted tree is called a leaf if it has no children.
一棵树只有 个 vertex（root），似乎也能被称作 leaf.

对于 的情况，其实 ，那么其实合成一颗 个叶子节点的有根树我们只需要将它本身作为根节点即可（ 因为如果我们构造一颗 2 个顶点，由一个根节点连接一个叶节点的树时，到这个叶节点的路径上就多了一条边，这条边是可以省去的，这样是成立的是对 来说的，当 时，编码无意义（），有效编码情况下应当是 ）。因此此时我们可以合并前两步，直接选择两个最小的权重作为叶节点并合并为一颗有根树。

对于 的情况，，当其不等于 时，按照计算得的个数建立有这么多个叶节点的根树，而等于 时，每一步都可以直接取 个最小权值作为叶节点。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <cctype>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;

class HuffmanTree {
 public:
  int freq;
  char c;
  HuffmanTree *left, *right;

  // 构造函数
  HuffmanTree(char ch, int freqcy)
      : freq(freqcy), c(ch), left(nullptr), right(nullptr) {}

  // 前序遍历：仅打印叶子节点（哈夫曼树的叶子是原始字符）
  void preorder(string path = "") {
    if (!left && !right) {
      cout << path << " " << freq << "  " << (int)c << " " << "\"" << c << "\""
           << endl;  // 叶子节点打印字符
    }
    if (left) left->preorder(path + "0");
    if (right) right->preorder(path + "1");
  }

  int encodingSize(string path = "") {
    if (!left && !right) {
      return freq * path.length();
    }
    int sum = 0;
    if (left) sum += left->encodingSize(path + "0");
    if (right) sum += right->encodingSize(path + "1");
    return sum;
  }

  // 析构函数：递归释放子节点内存
  ~HuffmanTree() {
    delete left;
    delete right;
  }
};

// 优先队列的比较器：按频率升序排列（小顶堆）
struct CompareHuffmanNode {
  bool operator()(HuffmanTree* a, HuffmanTree* b) const {
    return a->freq > b->freq;  // 优先队列默认是大顶堆，反向比较实现小顶堆
  }
};

void HuffmanEncoder(vector<char>& str) {
  map<char, int> freq;
  // 统计字符频率
  for (auto c : str) {
    freq[c]++;
  }

  // 优先队列存储指针，使用自定义比较器
  priority_queue<HuffmanTree*, vector<HuffmanTree*>, CompareHuffmanNode> pq;

  // 初始化：为每个字符创建叶子节点并加入优先队列
  for (auto& pr : freq) {
    pq.push(new HuffmanTree(pr.first, pr.second));
  }

  // 特殊情况：如果只有一种字符
  if (pq.size() == 0) return;
  if (pq.size() == 1) {
    auto root = pq.top();
    root->preorder();
    delete root;  // 释放内存
    return;
  }

  // 构建哈夫曼树
  while (pq.size() > 1) {
    // 取出频率最小的两个节点
    HuffmanTree* u = pq.top();
    pq.pop();
    HuffmanTree* v = pq.top();
    pq.pop();

    // 创建父节点（非叶子节点用'*'标识）
    HuffmanTree* parent = new HuffmanTree('*', u->freq + v->freq);
    parent->left = u;   // 左子节点为较小的节点（或任意，不影响结构）
    parent->right = v;  // 右子节点为次小的节点

    // 父节点加入优先队列
    pq.push(parent);
  }

  // 根节点是最后剩下的节点
  HuffmanTree* root = pq.top();
  pq.pop();  // 弹出根节点（避免析构时重复释放）

  // 前序遍历打印叶子节点（原始字符）
  root->preorder();
  cout << endl;  // 换行，优化输出
  cout << root->encodingSize() << endl;
  // 释放哈夫曼树的内存
  delete root;
}

void solve() {
  string str = "The pandemic of COVID is a test of social system";
  vector<char> input;
  // 预处理：大写转小写，存入vector
  for (auto c : str) {
    if (isupper(c)) {
      c = tolower(c);
    }
    input.push_back(c);
  }
  // 编码并打印前序遍历的叶子节点
  HuffmanEncoder(input);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  int t = 1;
  while (t--) {
    solve();
  }

  return 0;
}