可变长度编码：修订间差异

删除的内容添加的内容

行内

2023年10月26日 (四) 05:08的版本

在编码理论中，可变长度编码是将源符号映射到可变位数的代码。计算机科学中的等效概念是位串。

可变长度编码可以允许源以零错误（无损数据压缩）进行压缩和解压缩，并且仍然可以逐个符号地读回。通过正确的编码策略，可以将独立同分布的源压缩到几乎任意接近其熵的程度。这与固定长度编码方法相反，固定长度编码方法只能对大数据块进行数据压缩，并且任何超出可能性总数的对数的压缩都会带来有限（尽管可能任意小）的失败概率。

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

代码及其扩展

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

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

可变长度编码的类别

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

非奇异码

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

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

独特的可解码代码

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

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

前缀码

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

上一段中的示例映射 $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) 出现的概率为 $\textstyle \left({\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{8}}\right)$ ，使用上述编码表示源符号的预期位数为：

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.0 ^1.1 This code is based on an example found in Berstel et al. (2009), Example 2.3.1, p. 63.

2023年10月26日 (四) 05:08的版本

代码及其扩展

可变长度编码的类别

非奇异码

独特的可解码代码

前缀码

优点

参见

参考

相关文献