Loading AI tools
来自维基百科,自由的百科全书
编码理论中的可变长度编码(英语:variable-length code)指将源“符号”映射到可变位元的编码。计算机科学中的等效概念是位串。
此条目翻译品质不佳。 (2023年10月26日) |
![]() | 此条目可能包含原创研究。 |
可变长度编码允许源信息被以零误(无损数据压缩)的结果完成压缩和解压缩,且仍可读取每个符号。通过妥善的编码策略,能将独立同分布的源信息压缩到几乎任意接近其熵的程度。而固定长度编码方法只能对大数据块进行数据压缩,且任何超过可能性总数的对数的压缩都存在有限的失败概率,尽管这可能任意小。
知名的可变长度编码策略包括霍夫曼编码、Lempel-Ziv编码、算术编码和CAVLC(上下文自适应可变长度编码)。
对代码的扩展指通过将源序列的每个符号与原始码产生的相应码字连接而获得的有限长度源序列到有限长度比特串的映射。
使用形式语言理论中的术语,精确的数学定义如下:令和是两个有限集,分别称为源字母表和目标字母表。一个代码表示一个全函数[1],将中的每一个符号映射到上的符号序列,并将扩展到和的同态 ,这自然地映射了每个源符号序列到目标序列,称为它的扩展。
可变长度编码可以按照通用性递减的顺序严格嵌套,如非奇异码、唯一可解码代码和前缀代码。前缀码始终是唯一可解码的,后两者始终是非奇异的:
如果每个源符号映射到不同的非空比特串,则代码是非奇异的,即从源符号到比特串的映射是单射。
如果代码的扩展是非奇异的 ,则该代码是唯一可解码的。给定的代码是否是唯一可解码的可以使用Sardinas-Patterson 算法来确定。
如果映射中没有目标比特串是同一映射中不同源符号的目标比特串的前缀,则该代码是前缀码。这意味着符号可以在接收到整个码字后立即解码。此概念的其他常用名称包括无前缀代码、瞬时代码或上下文无关代码。
符号 | 码字 |
---|---|
a | 0 |
b | 10 |
c | 110 |
d | 111 |
前缀码的一个特例是块码。这里所有码字必须具有相同的长度。后者在信源编码中不是很有用,但通常在信道编码中用作前向纠错。
前缀码的另一个特殊情况是LEB128和可变长度数量(VLQ) 码,它们将任意大的整数编码为八位位组序列,即每个码字都是 8 位的倍数。
可变长度码的优点在于,不太可能出现的源符号会分配到较长的码字,而常出现的源符号会分配到较短的码字,从而给出较低的预期码字长度。对于上面的例子,如果 (a, b, c, d) 出现的概率为 ,使用上述编码表示源符号的预期位数为:
由于该源的熵为每个符号 1.7500 位,因此该编码能尽可能地压缩源,以便可以以零错误恢复源。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.