题目

任一个字符的编码都不是其它字符编码的前缀，则称这种编码具有前缀特性。现有某字符集（字符个数 ≥ 2）的不等长编码，每个字符的编码均为二进制的 0、1 序列，最长为 L 位，且具有前缀特性。请回答下列问题：

(1) 哪种数据结构适宜保存上述具有前缀特性的不等长编码？

(2) 基于你所设计的数据结构，简述从 0/1 串到字符串的译码过程。

(3) 简述判定某字符集的不等长编码是否具有前缀特性的过程。

解析

(1) 适合存放前缀编码的数据结构

答案：二叉树（编码树 / 前缀码 trie）。

构造规则：

• 每个字符存放在一个叶子结点——保证从根到该叶子的 0/1 路径就是该字符的编码；
• 内部结点不存字符——只起"路径分叉"作用；
• 左分支记 0，右分支记 1（约定即可，反过来也行）；
• 树最多有 层（编码最长 L 位 → 路径最长 L 条边）。

为什么这种结构天然就是"前缀码"：因为字符只在叶子。叶子的祖先全是内部结点，任何字符的编码（根→叶子路径）都不可能是另一字符编码（也是根→另一叶子路径）的前缀——否则前者那个叶子会出现在后者的路径中间，与"叶子"地位矛盾。

编者注（生僻术语）：哈夫曼树（Huffman tree）就是这种"编码树"的一种特殊构造（按字符频率构造使加权路径长度最短）。本题不要求最优编码，任何"字符全在叶子"的二叉树都满足前缀特性。

(2) 译码过程

答案：从根开始，按位读 0/1 串，0 走左、1 走右；遇到叶子就输出该叶子上的字符并回到根；继续读下一位。直到 0/1 串读完。

伪代码：

cur ← 根
result ← 空字符串
对 0/1 串中每一位 b：
    若 b = 0：cur ← cur.left
    否则：    cur ← cur.right
    若 cur 是叶子：
        result ← result + cur.char
        cur ← 根         // 回到根，准备下一个字符
返回 result

关键点：

• 由于编码具备前缀特性，每次到达叶子的时刻是唯一确定的——没有"提前停下"或"该停而没停"的歧义；
• 若读完 0/1 串时 cur 不在根（说明最后一段路径走了一半还没到叶子），则 0/1 串本身有问题（不是合法编码）；
• 时间复杂度 ，每位常数次操作。

(3) 判定一组不等长编码是否具备前缀特性

答案：把每个编码作为一条 0/1 路径插入空二叉树，过程中违反以下两条之一即不具备前缀特性，全部插完未违反则具备：

1. "穿越"已有叶子：插入新编码时，途中走到了一个已经被标记为叶子的结点（说明已有某字符的编码是新编码的前缀）；
2. 新叶子位置已是分叉：把新编码的最后一位走到的结点要标为新叶子，但这个结点已经有左/右孩子（说明新编码是某已有编码的前缀）。

伪代码：

建一棵只有根的空树
对每个字符的编码 code：
    cur ← 根
    对 code 中每一位 b：
        若 cur 已被标记为叶子：返回 "不具备前缀特性"   // 情况 1
        若 cur 沿 b 方向无孩子：建该孩子
        cur ← cur 沿 b 方向的孩子
    若 cur 已有孩子：返回 "不具备前缀特性"             // 情况 2
    把 cur 标记为叶子（绑定到当前字符）
返回 "具备前缀特性"

关键点说明：

• 两种违反情况对称：情况 1 是"老编码是新编码前缀"；情况 2 是"新编码是老编码前缀"；
• 复杂度 ，即总比特数；最坏情况下 （k 个字符、最长 L 位）；
• 替代方法——也可以两两比较所有编码对，看一个是否是另一个的前缀串。但这要 ，比建树法慢，且代码更繁琐，不推荐。