定义

串的运算

一个串 $a$ 的长度定义为它包含的字符个数，记为 $|a|$。

连接运算

给定一符号集 $S$，我们可以定义 $S$ 上串的连接运算，运算符记为 $\times$：若 $a,b$ 是 $S$ 上的串，那么 $a\times b$ 表示两个串顺次相连产生的新串。在不引起歧义时，连接运算的运算符也可以省略不写，如 $ab$。串的连接运算具有以下性质：

1. 不满足乘法交换律，例如 $\mathrm{abc\times de=abcde}$，而 $\mathrm{de\times abc=deabc}$；
2. 满足乘法结合律，例如 $\mathrm{abc\times(de\times f)=abcdef}$，而 $\mathrm{(abc\times de)\times f=abcdef}$；
3. 对所有的串 $a$，都满足 $\varepsilon a=a\varepsilon=a$，其中 $\varepsilon$ 是空字符串；

前缀和后缀

• 我们称串 $a$ 是串 $b$ 的前缀，如果存在串 $c$，使得 $b=ac$。我们用 $a\sqsubset b$ 来表示串 $a$ 是串 $b$ 的前缀这一关系。例如，hel 是 hello 的一个前缀。
• 我们称串 $a$ 是串 $b$ 的后缀，如果存在串 $c$，使得 $b=ca$。我们用 $b\sqsupset a$ 来表示串 $a$ 是串 $b$ 的后缀这一关系。例如，ello 是 hello 的一个后缀。

特别地，对于任一符号串 $a$，$a$ 和 $\epsilon$ 都是 $a$ 的前缀，也都是 $a$ 的后缀。

唯一可译码

在一个非奇异码中，虽然我们规定消息集到语言的映射是单射，但还并不能保证计算机能对输入的符号进行正确的解码。这是因为，在一次输入会话中，我们将一个消息序列中的消息依次进行编码，然后将得到的符号串连接在一起作为一个整体输入，因而解码时对符号串的划分可能存在歧义。

对于一个非奇异码来说，如果其语言包含的串无论如何相互连接，得到的长串都仅能以一种方式分解为串的乘积，则称这个码为唯一可译码。形式化地，如果非奇异码 $f:M\to L$ 中 $L$ 满足

$$\begin{aligned} p_1p_2\cdots p_n=q_1q_2\cdots q_m, p_i\in L, q_j\in L, \forall i=1,\cdots, n; j=1,\cdots,m \\ \Rightarrow n=m,p_i=q_i,\forall i=1,\cdots,n \end{aligned}$$

唯一可译码的 Kraft–McMillan 不等式

定理 给定唯一可译码 $f:M\to L$，$L$ 对应的符号集 $S$ 的大小为 $r$，并且语言 $L$ 所包含的 $n$ 个符号串 $l_1,\cdots,l_n$ 的长度分别为 $w_1,\cdots,w_n$，那么

$$\sum_{i=1}^nr^{-w_i}\le 1$$

证明参考附录。

Kraft-McMillan 不等式给出了唯一可译码的一个必要条件，但它并不是一个充分条件。下面我们探讨一类容易构造的唯一可译码。

前缀码

我们称一个码 $f:M\to L$ 是前缀码，如果 $L$ 中任两个串 $a$ 和 $b$ 都满足 $a$ 不是 $b$ 的前缀、$b$ 也不是 $a$ 的前缀。形式上地，

$$a,b \in L \Rightarrow \neg (a\sqsubset b) \wedge \neg (b\sqsubset a)$$

所有前缀码都是唯一码。（需要说明）

然而，不是所有唯一可译码都是前缀码。假设消息集 $M$ 包含两个消息，符号集为 $\{0,1\}$，我们来看这个语言：

$$L=\{10,1\}$$

（一定的论证）所以，它也是唯一可译码。

顶功码

我们称所有不是前缀码的唯一可译码为顶功码。

唯一可译码在线验证

检验一个码是否为前缀码是容易的，但是检验是否为唯一可译码则不那么容易。在这里我们提供一个在线应用对其进行检测。

前缀码与顶功码的等价性

我们定义码 $f:M\to L$ 和码 $g:M\to L'$ 等价，如果它们的语言 $L,L'$ 共享了同一个符号集 $S$，并且存在一个双射 $\sigma:L\to L'$，将 $L$ 中的每一个串 $a$ 映成 $b$ 时 $a$ 和 $b$ 具有相同种类和数量的符号，也即 $b$ 是 $a$ 的一个重新排列。

由于前缀码总是比顶功码更易于理解，我们总希望将顶功码通过等价关系转化为前缀码加以研究。虽然我们尚未进行证明，但是我们接下来默认这一事实的正确性：对于任意一个顶功码，可以找到一个前缀码与之等价。