可变长度编码

编码理论中的可变长度编码（英語：variable-length code）指将源“符号”映射到可变位元的编码。计算机科学中的等效概念是位串。

提示：此条目的主题不是可变宽度编码。

可变长度编码允许源信息被以零误（无损数据压缩）的结果完成压缩和解压缩，且仍可读取每个符号。通过妥善的编码策略，能将独立同分布的源信息压缩到几乎任意接近其熵的程度。而固定长度编码方法只能对大数据块进行数据压缩，且任何超过可能性总数的对数的压缩都存在有限的失败概率，尽管这可能任意小。

知名的可变长度编码策略包括霍夫曼编码、Lempel-Ziv编码、算术编码和CAVLC（上下文自适应可变长度编码）。

代码与其扩展

对代码的扩展指通过将源序列的每个符号与原始码产生的相应码字连接而获得的有限长度源序列到有限长度比特串的映射。

使用形式语言理论中的术语，精确的数学定义如下：令${\displaystyle S}$和${\displaystyle T}$是两个有限集，分别称为源字母表和目标字母表。一个代码${\displaystyle C:S\to T^{*}}$表示一个全函数^[1]，将${\displaystyle S}$中的每一个符号映射到${\displaystyle T}$上的符号序列，并将${\displaystyle C}$扩展到${\displaystyle S^{*}}$和${\displaystyle T^{*}}$的同态 ，这自然地映射了每个源符号序列到目标序列，称为它的扩展。

可变长度编码的类别

可变长度编码可以按照通用性递减的顺序严格嵌套，如非奇异码、唯一可解码代码和前缀代码。前缀码始终是唯一可解码的，后两者始终是非奇异的：

非奇异码

如果每个源符号映射到不同的非空比特串，则代码是非奇异的，即从源符号到比特串的映射是单射。

• 例如，映射${\displaystyle M_{1}=\{\,a\mapsto 0,b\mapsto 0,c\mapsto 1\,\}}$不是非奇异的，因为“a”和“b”都映射到相同的位串“0”；此映射的任何扩展都会生成有损（非无损）编码。当一些信息丢失是可以接受的时候（例如当这样的代码用于音频或视频压缩时，其中有损编码变得等同于源量化），这样的单一编码可能仍然有用。
• 然而，映射${\displaystyle M_{2}=\{\,a\mapsto 1,b\mapsto 011,c\mapsto 01110,d\mapsto 1110,e\mapsto 10011,f\mapsto 0\}}$是非奇异的；它的扩展将生成无损编码，这对于一般数据传输很有用（但并不总是需要此功能）。请注意，非奇异代码不必比源代码更紧凑（并且在许多应用中，较大的代码是有用的，例如作为检测编码或传输错误和/或从编码或传输错误中恢复的方法，或者在安全应用程序，以保护源免受不可检测的篡改）。

唯一可解码代码

如果代码的扩展是非奇异的 ，则该代码是唯一可解码的。给定的代码是否是唯一可解码的可以使用Sardinas-Patterson 算法（英语：Sardinas–Patterson_algorithm）来确定。

• 映射${\displaystyle M_{3}=\{\,a\mapsto 0,b\mapsto 01,c\mapsto 011\,\}}$是唯一可解码的（可以通过查看映射中每个目标位字符串后面的后续集来证明，因为一旦我们看到 0 位，位字符串就终止，该 0 位不能跟随任何现有代码来创建更长的有效代码，但能明确地开始一个新代码）。
• 对于来自上一节的代码${\displaystyle M_{2}}$^[1]，该代码不是唯一可解码的，因为字符串011101110011可以解释为码字序列01110 – 1110 – 011 ，也可以解释为码字序列011 – 1 – 011 – 10011 。因此， cdb和babe给出了该编码字符串的两种可能的解码。然而，当所有可能的源符号的集合完全已知且有限时，或者当存在“确定该扩展的源元素是否可接受”的限制（例如形式文法）时，这样的代码是有用的。这些限制允许通过检查映射到同一符号的可能源符号中，哪些在这些限制下是有效的来解码原始消息。

前缀码

如果映射中没有目标比特串是同一映射中不同源符号的目标比特串的前缀，则该代码是前缀码。这意味着符号可以在接收到整个码字后立即解码。此概念的其他常用名称包括无前缀代码、瞬时代码或上下文无关代码。

• 上一段中的示例映射${\displaystyle M_{3}}$不是前缀码，因为我们在读取位串“0”后不知道它是否编码“a”源符号，或者它是否是编码“b”或“c”的前缀符号。
• 前缀代码的示例如下所示。

符号	码字
a	0
b	10
c	110
d	111

编码和解码示例：

aabacdab → 00100110111010 → |0|0|10|0|110|111|0|10| → aabacdab

前缀码的一个特例是块码。这里所有码字必须具有相同的长度。后者在信源编码中不是很有用，但通常在信道编码中用作前向纠错。

前缀码的另一个特殊情况是LEB128和可变长度数量(VLQ) 码，它们将任意大的整数编码为八位位组序列，即每个码字都是 8 位的倍数。

优点

可变长度码的优点在于，不太可能出现的源符号會分配到较长的码字，而常出现的源符号會分配到较短的码字，从而给出较低的预期码字长度。对于上面的例子，如果 (a, b, c, d) 出现的概率为${\displaystyle \textstyle \left({\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{8}}\right)}$ ，使用上述编码表示源符号的预期位数为：

${\displaystyle 1\times {\frac {1}{2}}+2\times {\frac {1}{4}}+3\times {\frac {1}{8}}+3\times {\frac {1}{8}}={\frac {7}{4}}}$

由于该源的熵为每个符号 1.7500 位，因此该编码能尽可能地压缩源，以便可以以零错误恢复源。

参见

• 格倫布編碼

参考

1. This code is based on an example found in Berstel et al. (2009), Example 2.3.1, p. 63.

相关文献

• Salomon, David. Variable-Length Codes for Data Compression 1. Springer Verlag. September 2007. ISBN 978-1-84628-958-3. (xii+191 pages) Errata 1Errata 2
• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe. Codes and automata. Encyclopedia of Mathematics and its Applications 129. Cambridge, UK: Cambridge University Press. 2010. ISBN 978-0-521-88831-8. Zbl 1187.94001. Draft available online （页面存档备份，存于互联网档案馆）