哈夫曼树和哈夫曼编码

哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。
核心思想：频率高的字符用短编码，频率低的字符用长编码，从而实现数据压缩。

哈夫曼树

结点的权：根据需要赋予结点的有意义的数值，本问题中通常取字符出现的频率。
结点的带权路径长度：该结点到根的路径长度与该结点权值的乘积。
树的带权路径长度（Weighted Path Length, WPL）：树中所有叶子结点的带权路径长度之和，记作：

W P L = \sum_{i = 1}^{n} w_{i} \cdot L_{i}

其中 $w_{i}$ 为第 $i$ 个叶子结点的权值， $L_{i}$ 为第 $i$ 个叶子结点到根的路径长度。

对于给定一组具有确定权值的叶子结点，可以构造出许多棵形态不同的二叉树，其中 WPL 最小的二叉树称为哈夫曼树（Huffman Tree），又称最优二叉树（Optimal Binary Tree）。

哈夫曼树具有以下性质：

每个叶子结点对应一个原始字符（带权值）。
每个内部结点不存储字符，其权值为两个子结点权值之和。

构造算法

根据给定的 $n$ 个权值 $w_{1}, w_{2}, \dots, w_{n}$ ，构造一个由 $n$ 棵二叉树组成的森林 $F$ ，其中每棵二叉树只有一个带权 $w_{i}$ 的根结点，左右子树均为空。
在森林 $F$ 中选出两棵根结点权值最小的树（若有多棵则任选两棵），以它们作为左右子树合并成一棵新的二叉树；新根结点的权值为原两棵树根结点的权值之和，新根结点不存储字符。
从森林 $F$ 中删除这两棵子树，并将新建立的二叉树加入森林 $F$ 。
对新的森林 $F$ 重复步骤 2、3，直到森林中只剩下一棵树为止，该树即为哈夫曼树。

构造示例

示例：以 $W = (5, 15, 40, 30, 10)$ 为权构造一棵哈夫曼树。
图中橙色为本步新建的内部结点及其连边，绿色为之前已合并得到的内部子树，蓝色为带权叶子。

哈夫曼树构造示例：初始森林

最终各叶子到根的路径长度为： $5$ 和 $10$ 深度为 $4$ 、 $15$ 深度为 $3$ 、 $30$ 深度为 $2$ 、 $40$ 深度为 $1$ ，因此

W P L = 5 \times 4 + 10 \times 4 + 15 \times 3 + 30 \times 2 + 40 \times 1 = 205 .

哈夫曼编码

在数据通信中，我们希望用尽可能短的二进制编码来表示字符。如果使用固定长度编码（如 ASCII 每字符 8 位），则无法利用字符出现频率的差异。哈夫曼编码（Huffman Coding）是一种可变长度编码方法，根据字符出现的频率分配不同长度的编码，使得总体编码长度最短。

构造好哈夫曼树后，可以通过 DFS 遍历树来生成每个字符的编码。从根结点出发，沿途记录路径：向左走记为 "0"，向右走记为 "1"。当到达叶子结点时，当前路径字符串即为该字符的哈夫曼编码。

哈夫曼编码的核心性质：

前缀编码：没有编码是另一个编码的前缀。
最优压缩：哈夫曼树使 WPL 最小，即编码后的总比特流长度最短。

Baseline

依赖代码位于 Tree\Baseline\huffman 目录下。学生需要在 huffman-tree-impl.hpp 中实现 construct_huffman_tree() 函数，使用输入的频率数据构建哈夫曼树。

数据结构定义

本项目中使用以下数据结构（定义在 huffman-tree.h）：

通用 N 叉树结点（Node）

cpp

template <typename T, std::size_t N = 2>
struct Node {
    T data;
    std::array<std::unique_ptr<Node>, N> children;

    Node(const T &data);
    Node(T &&data);
    static std::unique_ptr<Node> get_new_node(const T &data);
    static std::unique_ptr<Node> get_new_node(T &&data);
};

Node 是一个模板化的通用结点，N 为子结点数量（默认为 2，即二叉树结点）。子结点存储在固定大小的 std::array 中，所有权通过 std::unique_ptr 管理。

哈夫曼树结点数据（HuffmanTreeNodeData）

cpp

template <typename data_t, typename weight_t>
struct HuffmanTreeNodeData {
    std::optional<data_t> data;   // 叶子结点存储字符，内部结点为 nullopt
    weight_t weight;              // 权值（频率）
};

HuffmanTreeNodeData 使用 std::optional<data_t> 来区分叶子结点（有字符数据）和内部结点（无字符数据）。

哈夫曼树结点类型别名

cpp

template <typename data_t, typename weight_t>
using HuffmanTreeNode = Node<HuffmanTreeNodeData<data_t, weight_t>, 2>;

HuffmanTreeNode 是一个携带 HuffmanTreeNodeData 作为数据载荷的二叉树结点。

待实现函数

函数签名：

cpp

template <typename data_t, typename weight_t>
std::unique_ptr<HuffmanTreeNode<data_t, weight_t>>
construct_huffman_tree(const std::vector<std::pair<data_t, weight_t>> &leaves);

学生需要按照上述哈夫曼树构造算法实现该函数。

测试程序

huffman-coding.cpp 是一个交互式测试程序，读取一行文本，统计字符频率，构建哈夫曼树，并 DFS 遍历输出每个字符的编码。

cpp

#include <functional>
#include <iostream>
#include <map>
#include <string>

#include "huffman-tree.h"

#include "huffman-tree-impl.hpp"

int main() {
  std::string line;
  std::cout << "Enter one line of string: ";
  std::getline(std::cin, line);
  std::map<char, int> cnts;
  for (const auto &chr : line)
    ++cnts[chr];
  for (const auto &[chr, cnt] : cnts)
    std::cout << "char " << chr << " cnt " << cnt << std::endl;

  std::vector<std::pair<char, int>> leaves(cnts.begin(), cnts.end());
  const auto tree_root = construct_huffman_tree(leaves);

  std::map<char, std::string> codes;
  const std::function<void(const decltype(tree_root) &, const std::string &)>
      traversal =
          [&](const decltype(tree_root) &node, const std::string &code) {
            if (node->data.data.has_value())
              codes[node->data.data.value()] = code;
            else {
              traversal(node->children[0], code + "0");
              traversal(node->children[1], code + "1");
            }
          };
  traversal(tree_root, "");
  for (const auto &[chr, code] : codes)
    std::cout << "char " << chr << " code " << code << std::endl;

  return 0;
}

测试样例

注：以下测试样例仅用于说明格式，不代表完整测试覆盖范围。学生需要根据该格式自行设计并生成更多测试样例，覆盖边界情况。

输入样例

text

Enter one line of string: hello world

输出样例（不唯一）

text

char   cnt 1
char d cnt 1
char e cnt 1
char h cnt 1
char r cnt 1
char w cnt 1
char o cnt 2
char l cnt 3
char   code 000
char d code 001
char e code 010
char h code 011
char r code 100
char w code 101
char o code 11
char l code 10

评分标准：以编码后整个字符串的二进制比特流总长度作为评分依据。编码结果不要求与参考实现完全一致，只要 WPL 相同（即总比特流长度相同）即可。

提交要求

你提交的材料中这部分内容需要包含：

construct_huffman_tree() 的完整实现代码。
对哈夫曼树构造算法的原理说明，以及对你的实现的时间和空间复杂度的分析。
自行设计测试用例，包含不同字符频率分布（均匀分布、极端分布等），测试编码结果并计算 WPL。

思考题

分析为什么哈夫曼编码是前缀码，以及为什么它能保证最优压缩。

哈夫曼树和哈夫曼编码 ​

哈夫曼树 ​

构造算法 ​

构造示例 ​

哈夫曼编码 ​

Baseline ​

数据结构定义 ​

通用 N 叉树结点（Node） ​

哈夫曼树结点数据（HuffmanTreeNodeData） ​

哈夫曼树结点类型别名 ​

待实现函数 ​

测试程序 ​

测试样例 ​

输入样例 ​

输出样例（不唯一） ​

提交要求 ​

思考题 ​