資訊理論抄書筆記 - 從零開始的理想信源編碼與數據壓縮之旅

07-07

用盡量短的編碼，去表達盡量多的數據，是貪心的科學家們所一直追求的。偉大的人們一直在嘗試通過合適的編碼方案，把數據壓得儘可能小。但是憑藉直覺，我們知道，通過編碼是不能將很大的數據僅用很短的碼字來表示的。畢竟如果那樣，會很難區分不同數據之間的差異。而也就是這，我們才會在心裡犯嘀咕：數據壓縮有沒有極限？怎麼壓縮？理想編碼方案存在嗎？

想要正面硬剛這樣的問題，需要把其背後的數學原理給抽象出來，嚴謹的數學推導會幫助我們揭開事實的真相。

為了方便表述，一般用 $C$ 表示一個信源編碼方案，用 $l(x)$ 表示 $x$ 的碼長， $C(x_1 x_2 x_3)$ 表示數據 $x_1x_2x_3$ 對應的編碼

那麼編碼方案怎麼才叫理想呢？我們基於這個問題要定義一些東西：

Definition 1 : 期望長度(expected length)

對於隨機變數 $X$ 概率密度函數 $p(x)$ ，編碼方案為 $C$ ，則碼長的數學期望 $L(C) = sum_x p(x)l(x)$ 稱作期望長度

數據與編碼方案肯定是要一一對應的，單個碼對應單個的數據，單個的數據對應單個的碼，這樣的編碼性質我們一般稱之為非奇異（nonsingular）。

非奇異碼會遇到一個問題，比如：紅球的編碼為10，黑球的編碼為0，白球為01，那麼010 究竟是 $C( 黑紅)$ 還是 $C( 紅白 )$ 呢？

解碼時如果不唯一，只會讓原本慌張的我們更凌亂。唯一可譯這個性質，該怎麼定義？

Definition 2 : 唯一可譯（uniquely decodable）
一個碼字，如果任意擴展後是非奇異的，則稱這個碼唯一可譯

這個定義看起來好像和「人被殺，就會死」一樣比較滑稽.....

既然這樣，不如先看下唯一可解碼的一些實踐效果把：

對於紅（10）黃（00）白（11）黑（110），這樣的編碼方案，我們通過分類討論得出這是唯一可譯的，比如開始兩位為00，就是黃，是10就是紅，但如果開始的兩位是11呢？

我們需要再參考一下後面的碼是什麼樣子，事實上，只有確認當11後面的0接了奇數個的時候，才能確認前三位110是黑。那如果是偶數呢？前兩位11是白，後面的偶數個0都是黃。

隱約能夠感覺出來，這樣的解碼效率並不高，時不時參考後面的碼長什麼樣子著實有點惱火，而我們希望這個碼能避免這個缺點。正是因此有了我們最終的定義--及時可解碼。

Definition 3: 及時可解碼（instantaneous code / prefix code）

沒有任何一個碼，是另一個碼的前綴，則稱之為及時可解碼，或者為前綴碼。

舉個栗子：紅（0）,黃（10）,白（110）,黑（111）這是一組編碼，顯然是前綴碼，那麼 $C^{-1}(11110010)$ 只能為黑黃紅黃。

那麼如何構造前綴碼呢？其實前綴碼可以和一個模型聯繫在一起 - 二叉樹

剛剛的栗子就是下面這個模型

從頂點出發，往左走一步就記為0，往右走就記為1。而互為前綴碼的關係，就是互為孩子節點的關係。

什麼條件下能構造前綴碼呢？前綴碼有怎麼樣的性質呢？關於這，有一個有名的不等式，叫Kraft不等式：

Theorem 1：Kraft不等式（Kraft inequlity）
D進位的前綴碼，碼字長度為 $l_1,l_2,...,l_n$ ，則滿足不等式
$sum_{i=0}^n D^{-l_i} leq 1$ ,反過來，若該不等式成立，則一定存在相應的一組前綴碼。

這裡給出該定理的三種證明的方法，：

證法①：

為了方便理解，我們直接證明D=2的時候，即二進位的情況。

找到這棵樹最底端的葉子，該葉子碼長一定最長，記為 $l_{max}$ 。如果把二叉樹按照如圖方式補齊成一個完整二叉樹，則對於任何一個碼長為 $l_i$ 的葉子節點來說， $2^{l_{max}-l_{i}}$ 表示 $l_i$ 的節點生長到最底端的孩子節點數量。

那麼 $sum_{i=1}^n2^{l_{max}-l_i}$ 表示所有節點延伸到最底端的孩子節點數量，二叉樹最底端最多也不過 $2^{l_{max}}$ 個孩子，因此 $sum_{i=1}^n2^{l_{max}-l_i} leq 2^{l_{max}} Leftrightarrowsum_{i=1}^n2^{-l_i} leq 1$

而已知這個不等式，我們顯然也可以按照二叉樹如圖的形式，把這個編碼方案給湊出來，所以Kraft不等式成立。

而關於更一般的D進位問題，也不過就是把二叉樹換成D叉樹而已，證明過程幾乎一樣。我們也可以管窺一下，發現取等的條件就是每個葉子節點必須都要對應一個編碼，不能有空白的葉子節點。

證法②：

$D$ 進位的碼字集合為 ${0,1,...,D-1}$ ，因此對於第 $i$ 個碼字記為 $y_{_1}y_{_2}...y_{l_i}$ ，如果建立一個一一映射， $y_{_1}y_{_2}...y_{l_i} ightarrow [0.y_{_1}y_{_2}...y_{l_i}+D^{-{l_i}})$ 我們很容易發現，前綴碼中不同的節點對應的這些區間是不相交的（因為如果區間相交，則一定有一個碼是 $0.y_{_1}y_{_2}...y_{l_i}$ ,另一個是 $0.y_{_1}y_{_2}...y_{l_i}....$ ，與前綴碼定義矛盾了)。

取這些區間的並集，顯然是 $igcup_{i=1}^{n}[0.y_{_1}y_{_2}...y_{l_i},0.y_{_1}y_{_2}...y_{l_i}+D^{-{l_i}}) subseteq [0,1]$

因此這些區間長度加起來不超過1，即 $sum_{i=0}^n D^{-l_i} leq 1$ 。

而滿足這個不等式的話，把邏輯順序倒過來構造區間，即可構造出前綴碼。

這個證明方法可以推廣至下無窮的情況，即：

當編碼集合是可數集合時，則滿足Kraft不等式： $sum_{i=0}^infty D^{-l_i} leq 1$

證明思路和這個證法也幾乎一樣，不過就是有限到無窮的情況而已。

證法③：

記 ${l(x_1x_2...x_k)} = l(x_{1})+l(x_2)+...+l(x_n)$ 即一串字元的編碼長度。

則

$egin{align} ( sum_x D^{-l(x)} )^k&=sum_{x_1in chi}sum_{x_2in chi}...sum_{x_kin chi}D^{-l(x_1x_2...x_k)} \&=sum_{x^kinchi^k}D^{-l(x^k)} \ end{align}$

合併同類項得到 $=sum_{i=0}^{kl_{max}}N(m)D^{-i}$ 其中 $N(m)$ 表示長度 $i$ 的碼字數量，

由D進位和前綴碼的唯一可譯性質容易有 $leqsum_{i=0}^{kl_{max}}D^{i}D^{-i}=kl_{max}$

即 $sum_{x}D^{-l(x)} leq (kl_{max})^{frac{1}{k}}$ 此時令 $k ightarrowinfty$ 即可得到Kraft不等式

由於這種證明方法只用到了唯一可譯性，故可以把結論推廣，所以題目條件可以減弱：

唯一可解碼滿足Kraft不等式

是否感覺信息量有點大？errr....那麼稍微整理下：

我們證明了前綴碼滿足Kraft不等式，而根據不等式又可以構造相應的前綴碼，於是某種程度上，Kraft不等式 $Leftrightarrow$ 一組前綴碼，兩者等價。所以，如果要尋找最優前綴碼（編碼長度平均最短），相當於一個條件極值問題

$sum_{i=1}^nD^{-l_i}leq1,min{sum_{i=1}^np(x_i)l_i}=?$ 其中X的分布是已知的( $p_i$ 已知)。

但就算求出來最優了，也不能說明唯一可解碼中沒有比前綴碼更短的呀！！

別急....剛剛第3個proof中，證出來了唯一可解碼滿足Kraft不等式，這說明了什麼？

說明，這個條件極值的求解並不會影響我們的結論，不管最後求解出來 $l_i(i=1,...,n)$ 是多少，對應構造的前綴碼和唯一可解碼期望長度是一樣的。既然如此，為何不考慮隨收隨譯的前綴碼呢？

（恭喜前綴碼上位）

那麼開始我們的求解吧！

條件極值怎麼求？自然是高數中的拉格朗日乘數法出場了（KKT條件？抱歉...不太懂）。

構造運算元 $f(l_1,...,l_n)=sum_{i=1}^n p_il_i - lambda(sum_{i=1}^nD^{-l_i}-1)$

然後暴力求偏導 $frac{partial f}{partial l_i}=0 Rightarrow p_i-lambda D^{-l_i}ln{D}=0 quad (i=1,...,n) \ frac{partial f}{ partiallambda}=0$

解上面的方程組即可得到極值條件 $l_i=-log_{D}{p_i}quad(i=1,...,n)$

於是，期望長度的最小值是 $sum_{i=1}^np_il_i=-sum_{i=1}^np_ilog_D{p_i}=H(X)$

....一個驚人的事實就這樣展現在我們面前，信息熵原來是期望長度的下確界。

換句話說，數據無損壓縮的期望長度不能 $leq H(X)$ ，數據的壓縮是具有臨界值的！

為了把這個事實銘記於心，乾脆寫成定理的形式：

Theorem 2：

信源 $X$ 的碼字的期望長度滿足不等式
$L geq H(X)$
等號成立條件為 $l_i=-log_{D}{p_i}quad(i=1,...,n)$ 其中 $D$ 代表D進位編碼

然而求解並沒有結束，因為 $l_i$ 必須是整數，而 $-log_D{p_i}$ 卻不一定是。因此想求解並不容易。當然，我們完全可以取 $l_i=[-log_Dp_i]$ （而這就是傳說中的Shannon碼）這樣肯定是滿足Kraft不等式的，而且確保了是整數，儘管這不一定是理想的方案（畢竟對於一個伯努利分布的X，參數 $p ightarrow0$ 時，對應的Shannon碼長 $[-log_2p]$ 會長破天際....）。

不過嘗試計算下誤差我們會發現 $sum_{i=1}^n p_il_i=sum_{i=1}^n p_i[-log_Dp_i] leq sum_{i=1}^n (-p_ilog_Dp_i+p_i)=H(X)+1$ 因而Shannon碼的期望長度 $L in[H(X),H(X)+1]$ ，自然的，最優編碼方案的 $L_{min}in[H(X),H(X)+1]$ 也成立。

至此，我們發現了：最優編碼方案肯定存在，其期望長度在 $[H(X),H(X)+1]$ 之中，但是到底怎麼構造的呢？Shannon碼不夠優秀，之後的Fano碼也拆強人意，恐怕.....（並不）

這時候Huffman站了出來，Huffman在博士期間的一次作業中巧妙的發現了一種構造碼字的方法，並且證明了其最優性，後人尊稱Huffman編碼。

輔助具體栗子的說明，先來說構造方法。前綴碼對應的模型是二叉樹，核心是如何構建出來二叉樹，Shannon碼和Fano碼的構造方法都是由樹根開始往葉子構造，為了保證期望長度短，給大概率事件短碼，給小概率事件長碼，這是對的。但是Huffman從葉子開始往樹根構建二叉樹的作法，卻帶來了不一樣的效果。

信源 $X$ 的概率密度函數 $overrightarrow{p}=(frac{1}{21},frac{2}{21},frac{3}{21},frac{4}{21},frac{5}{21},frac{6}{21})$ 根據這個概率分布來構建碼字。

把概率低的 $frac{1}{21}$ 和 $frac{2}{21}$ 拼在一起

此時分居兩邊，兩個節點合為一個，於是他們合起來的權重記為3/21，標記在最上面

把原來的 $frac{1}{21}$ 和 $frac{2}{21}$ 替換成一個 $frac{3}{21}$ ，重新挑選最小的兩個，分別是 $frac{3}{21}$ 和 $frac{3}{21}$ ，拼一起

為了便於看，被編碼的葉子，概率在中間，不編碼的的就在節點上方

替換完後的 $overrightarrow{p}=(frac{4}{21},frac{5}{21},frac{6}{21},frac{6}{21})$ ，繼續挑選概率最小的兩個 $frac{4}{21}$ 和 $frac{5}{21}$ 拼在一起，後面過程和上述過程完全一樣，（此處省略233個字....）

最後得到了如圖所示的二叉樹，尊稱為Huffman樹

圖片做的很醜見諒...latex用的不熟，要是有dalao推薦什麼作圖的軟體之類的就好了

於是構建好樹後開始編碼，從樹根往下走，往左走就添一個0，往右走添一個1，最後直到葉子為止。至此，我們得到了每個葉子節點的編碼： $overrightarrow{C(X)} = (0000,0001,001,01,10,11)$ 順序是從左往右。

Huffman樹的構建比較簡單，每次挑兩個概率最小的拼在一起就行，如果事後諸葛亮的話，非覺得這也是非常自然的構造（並不）。而一般的構造，也就是遞歸的進行上述步驟即可。

那麼最關鍵的問題來了，憑什麼說它是最優的呢？下面給出定理表述及證明過程：

（待續，可能再續就是幾個月之後了...）