可變長度編碼

編碼理論中的可變長度編碼（英語：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 （頁面存檔備份，存於網際網路檔案館）