树的应用

编码和解码

编码（Encoding）是将信息从一种形式（通常是人类可读的符号或数据）转换为另一种形式（通常是机器可处理的格式，如二进制比特流）的过程。其目的是为了便于存储、传输或处理信息。编码通常涉及将原始数据（如字符、数字等）映射为特定的代码，这些代码由一组规则或编码表定义。

解码（Decoding）是编码的逆过程，即将编码后的数据（如二进制比特流）转换回原始形式的过程。解码需要依赖编码时使用的规则或编码表，以确保正确还原原始信息。

编码集分类

编码集是一组用于表示特定符号或数据的 编码规则的集合。

编码集常按以下方式分类：

• 固定长度 vs 非固定长度
  • 固定长度编码集：每个代码的长度相同，例如 ASCII 编码中每个字符都用 8 位表示。
  • 可变长度编码集：代码长度可以不同，例如 哈夫曼编码 中高频符号用较短代码，低频符号用较长代码，以实现数据压缩。
• 前缀 vs 非前缀
  • 前缀编码：没有一个编码是另一个编码的前缀
  • 非前缀编码：有编码是其他编码的前缀

定长编码

定长编码是指：为每个符号分配长度完全相同的二进制编码。
也就是说，不管某个符号出现得多还是少，它所占用的比特数都是一样的。

定长编码的 构建方式 如下：

1. 统计符号集合：先确定总共有多少个不同的符号，记为 $n$。
2. 计算编码长度：要为每个符号分配一个不同的二进制码，所需的最小码长 $l$ 满足：

$$l = \lceil \log_2 n \rceil$$

也就是说，使用 $l$ 位二进制，可以最多表示 $2^l$ 个不同的符号。

3. 为每个符号分配编码：从 $0$ 开始，依次将二进制数分配给每个符号，使用前导零补足到长度 $l$。

举个实例 说明一下

假设有 5 个符号：A、B、C、D、E

• 总数 $n = 5$，因此编码长度 $l = \lceil \log_2 5 \rceil = 3$
• 3 位二进制能编码最多 $2^3 = 8$ 个符号，足够使用
• 分配如下：

根据以上构建过程可知：在定长编码中，所有叶子结点（对应字符的结点）都位于同一层，在变长编码中，叶子结点可以不位于同一层。

前缀编码

前缀编码（Prefix Code）是一种编码方式，其中没有任何编码是另一个编码的前缀。换句话说，在一组编码中，任何一个编码字符串都不会是另一个编码字符串的开头部分。这种特性确保了编码可以被唯一且无歧义地解码，常用于数据压缩和通信系统。

编码集 {1, 01, 001, 0000} 对应的二叉树如上面的左图所示。该编码集为前缀编码，可以观察到，前缀编码的每一个编码都处于叶结点的位置，这说明在对比特流进行解码的过程中不会出现歧义（想要获取到编码需要唯一地到达叶结点）。

编码集 {0, 10, 110, 1011} 对应的二叉树如上面的右图所示。该编码集为非前缀编码，可以观察到，非前缀编码有编码处于中间结点的位置，这说明在对比特流进行解码的过程中会出现歧义，比如对于 10110，解码器无法确认是将开始的 10 解码为 B 还是将 1011 解码为 D。

编码长度计算

在信息编码相关的试题中，常会考察两种编码长度的计算方式：加权路径长度 和 加权平均长度。这两个概念虽相关，但含义和用途不同，需要仔细辨别。

此外，计算这两个指标时还涉及到两个基本的量：频次 和 概率。它们在形式上相似，但在理解和运用时也要有所区分。

• 频次：表示某个符号在整体数据中实际出现的次数。
• 概率：表示某个符号出现的相对频率，即该符号出现的频次除以总频次。

举个简单的例子：

假设一段文本中总共有 100 个符号，其中字母 A 出现了 20 次。 那么 A 的频次是 20，概率是 $\frac{20}{100} = 0.2$。

编码长度的计算可以基于频次，也可以基于概率。两种方法在数值上本质一致，只是表达形式不同，使用频次适用于原始统计数据，使用概率则适用于标准化分析。

接下来我们就分别介绍这两种编码长度的具体含义及其数学计算方式。

加权路径长度

加权路径长度 是指：所有符号的编码长度与其出现频次的乘积之和。

这个量表示整体编码所需的总比特数，是衡量编码总开销的重要指标。

设：

• 一共有 $n$ 个符号；
• 第 $i$ 个符号的出现频次为 $f_i$；
• 该符号的编码长度为 $l_i$；

则加权路径长度为：

$$ \text{WPL} = \sum_{i=1}^{n} f_i \cdot l_i $$

加权平均长度

加权平均长度 是指：在整个编码过程中，平均每个符号所占用的编码长度。它是在加权路径长度的基础上，除以总频次得到的平均值。

设：

• 第 $i$ 个符号的出现频次为 $f_i$；
• 编码长度为 $l_i$；
• 总频次为 $F = \sum_{i=1}^{n} f_i$；

则加权平均长度 $L$ 为：

$$ L = \frac{\sum_{i=1}^{n} f_i \cdot l_i}{\sum_{i=1}^{n} f_i} $$

如果已将频次标准化为概率 $p_i = \frac{f_i}{\sum f_i}$，也可以表示为：

$$ L = \sum_{i=1}^{n} p_i \cdot l_i $$

接下来通过一个 实例 来说明一下两个概念的计算：

假设我们有如下符号统计信息：

计算一：加权路径长度（WPL）

$$ \text{WPL} = 50 \cdot 1 + 20 \cdot 2 + 20 \cdot 3 + 10 \cdot 3 = 50 + 40 + 60 + 30 = \boxed{180 \text{ 位}} $$

表示：这段编码文本总共用了 180 位。

计算二：加权平均长度

方法一（基于频次）：

$$ L = \frac{180}{50 + 20 + 20 + 10} = \frac{180}{100} = \boxed{1.8 \text{ 位/符号}} $$

方法二（基于概率）：

$$ L = 0.5 \cdot 1 + 0.2 \cdot 2 + 0.2 \cdot 3 + 0.1 \cdot 3 = 0.5 + 0.4 + 0.6 + 0.3 = \boxed{1.8 \text{ 位/符号}} $$ 对比总结

哈夫曼树

哈夫曼树（Huffman Tree）是一种特殊的二叉树，通常用于数据压缩算法中，特别是用于构建哈夫曼编码（Huffman Coding）。哈夫曼树的主要目标是实现数据的无损压缩，通过赋予不同的数据符号不同长度的编码来减少数据的存储空间。

特点

1. 哈夫曼树是一棵二叉树，通常是带权二叉树，其中每个叶子节点都对应一个数据符号，而每个内部节点都没有数据，只有权值。
2. 哈夫曼树的叶子节点的权值通常表示数据符号的出现频率，而内部节点的权值等于其子节点权值之和。
3. 哈夫曼树的构建目标是找到一棵树，使得权值较高的数据符号拥有较短的编码，权值较低的数据符号拥有较长的编码。

构建过程

1. 创建一个包含所有数据符号的森林（初始状态下，每个数据符号都是一棵单节点树）。
2. 从森林中选择两棵树，这两棵树的权值最小。将它们合并为一棵新的树，新树的权值为两棵树的权值之和。
3. 将新的树放回森林中，重复步骤 2，直到森林中只剩下一棵树，这棵树就是哈夫曼树。
4. 构建好的哈夫曼树具有一个重要的性质：权值较高的数据符号在树中的深度较浅，而权值较低的数据符号在树中的深度较深。

一旦构建了哈夫曼树，就可以生成数据符号的哈夫曼编码。哈夫曼编码是一种变长编码，用于表示不同数据符号。在哈夫曼编码中，权值较高的数据符号通常对应较短的编码，权值较低的数据符号对应较长的编码。这种编码方式可以实现数据的高效压缩和解压缩。

哈夫曼树和哈夫曼编码在数据压缩领域具有广泛的应用，例如在无损压缩算法中，如 ZIP 文件压缩，图像压缩（如 JPEG）等。通过构建适用的哈夫曼树和编码，可以大幅减少数据的存储和传输成本。

哈夫曼编码

遍历哈夫曼树，为每个数据符号生成相应的哈夫曼编码。编码的生成方式如下（左 0 右 1）：

• 向左走时添加一个 0 位。
• 向右走时添加一个 1 位。
• 沿着树的路径一直到达叶子节点时，即可生成该叶子节点对应的数据符号的编码。

实例

为 a, b, c, d 四个字母生成哈夫曼编码，其对应的权值分别为 7, 5, 2, 4

并查集

并查集（Union-Find）是一种数据结构，主要用于解决集合划分及查询问题。它主要支持两种操作：查找（Find）和合并（Union）。其核心思想是使用一个数组（或其他数据结构）来存储每个元素的父节点信息。

查找

查找操作的目的是找到给定元素所属集合的代表。这可以通过追踪父节点来实现，直到找到根元素（即父节点为其自身的元素）。路径压缩可以在查找过程中应用，使得从指定节点到其根的路径上的每个节点都直接指向根，从而提高后续查找的效率。

合并

合并操作的目的是将两个集合合并为一个集合。为了执行合并，首先使用 Find 操作找到两个集合的代表，然后决定哪个代表成为新的根。为了保持树的平衡性，并减少查找时间，常用的策略是按秩合并。其中，秩通常表示树的高度。较低的树会被附加到较高的树的根上。

#define MAXN 1000

int parent[MAXN];  // 存储每个点的父节点
int rank[MAXN];    // 秩

// 初始化
void initialize(int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;  // 初始时，每个元素的父节点是其自身
        rank[i] = 0;    // 初始时，每个元素的秩为 0
    }
}

// 查找
int find(int x) {
    if (parent[x] != x) {
        // 路径压缩
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

// 合并
void unionSet(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}