查看“︁可变长度编码”︁的源代码

{{NoteTA
|G1=Communication
|G2=IT
}}
{{distinguish|可变宽度编码}}
{{Rough translation|time=2023-10-26T05:26:24+00:00}}
{{or1}}
[[编码理论]]中的'''可变长度编码'''（{{lang-en|variable-length code}}）指将源“符号”映射到可变[[位元]]的编码。[[计算机科学]]中的等效概念是[[位数组|位串]]。

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

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

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

使用[[形式语言|形式语言理论]]中的术语，精确的数学定义如下：令<math>S</math>和<math>T</math>是两个有限集，分别称为源字母表和目标[[字母表 (计算机科学)|字母表]]。一个'''代码'''<math>C: S \to T^*</math>表示一个全函数<ref name=":0">This code is based on an example found in Berstel et al. (2009), Example 2.3.1, p. 63.</ref>，将<math>S</math>中的每一个符号映射到<math>T</math>上的符号序列，并将<math>C</math>扩展到<math>S^*</math>和<math>T^*</math>的[[同态]] ，这自然地映射了每个源符号序列到目标序列，称为它的'''扩展'''。

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

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

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

=== 唯一可解码代码 ===
如果代码的扩展是非奇异的 ，则该代码是'''唯一可解码的'''。给定的代码是否是唯一可解码的可以使用{{Link-en|Sardinas-Patterson 算法|Sardinas–Patterson_algorithm}}来确定。

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

=== 前缀码 ===

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

* 上一段中的示例映射<math>M_3</math>'''不是'''前缀码，因为我们在读取位串“0”后不知道它是否编码“a”源符号，或者它是否是编码“b”或“c”的前缀符号。
* 前缀代码的示例如下所示。

{| class="wikitable" style="text-align:center; position: relative; left: 1in;"
!符号
!码字
|-
|a
| 0
|-
|b
|10
|-
|c
| 110
|-
| d
| 111
|}

:: 编码和解码示例：
::: {{Not a typo|aabacdab}} → 00100110111010 → |0|0|10|0|110|111|0|10| → {{Not a typo|aabacdab}}

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

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

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

:: <math>1\times\frac{1}{2}+2\times\frac{1}{4}+3\times\frac{1}{8}+3\times\frac{1}{8}=\frac{7}{4}</math> 

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

== 参见 ==
* [[格倫布編碼]]

== 参考 ==
{{Reflist}}
== 相关文献 ==

* {{Cite book|title=Variable-Length Codes for Data Compression|first=David|last=Salomon|publisher=[[Springer Verlag]]|date=September 2007|edition=1|isbn=978-1-84628-958-3}} (xii+191 pages) [https://web.archive.org/web/20230920174349/https://www.davidsalomon.name/VLCadvertis/VLCerrata.html Errata 1][https://web.archive.org/web/20230920175457/https://www.davidsalomon.name/VLCadvertis/phasedin.pdf Errata 2]
* {{Cite book|title=Codes and automata|last=Berstel|first=Jean|last2=Perrin|first2=Dominique|last3=Reutenauer|first3=Christophe|series=Encyclopedia of Mathematics and its Applications|volume=129|location=Cambridge, UK|publisher=[[Cambridge University Press]]|date=2010|isbn=978-0-521-88831-8|zbl=1187.94001}} [http://www-igm.univ-mlv.fr/~berstel/LivreCodes/Codes.html Draft available online] {{Wayback|url=http://www-igm.univ-mlv.fr/~berstel/LivreCodes/Codes.html |date=20231116201110 }}&nbsp;

{{Compression Methods}}
[[Category:编码理论]]