可變長度編碼

編碼理論中的可變長度編碼（英語：variable-length code）指將源「符號」映射到可變位元的編碼。計算機科學中的等效概念是位串。

可變長度編碼允許源信息被以零誤（無損數據壓縮）的結果完成壓縮和解壓縮，且仍可讀取每個符號。通過妥善的編碼策略，能將獨立同分布的源信息壓縮到幾乎任意接近其熵的程度。而固定長度編碼方法只能對大數據塊進行數據壓縮，且任何超過可能性總數的對數的壓縮都存在有限的失敗概率，儘管這可能任意小。

知名的可變長度編碼策略包括霍夫曼編碼、Lempel-Ziv編碼、算術編碼和CAVLC（上下文自適應可變長度編碼）。

代碼與其擴展

對代碼的擴展指通過將源序列的每個符號與原始碼產生的相應碼字連接而獲得的有限長度源序列到有限長度比特串的映射。

使用形式語言理論中的術語，精確的數學定義如下：令 $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 算法（英語：Sardinas–Patterson_algorithm）來確定。

映射 $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.

可變長度編碼

目次

代碼與其擴展

可變長度編碼的類別

非奇異碼

唯一可解碼代碼

前綴碼

優點

參見

參考

相關文獻