山農–菲諾–以利亞碼

在資訊理論中，山農–菲諾–以利亞碼是算術編碼的先導，其概率被用於決定碼字。

演算法描述

給定一離散隨機變量 X ，令 $p(x)$ 為 X=x 發生之概率。

定義

${\bar {F}}(x)=\sum _{x_{i}<x}p(x_{i})+{\frac {1}{2}}p(x)$

演算法如下：

對每個 X 中的 x，

令 Z 為 ${\bar {F}}(x)$ 之二次展開

令 x 之編碼長度 $L(x)=\left\lceil \log _{2}{\frac {1}{p(x)}}\right\rceil +1$

選定 x 之編碼， $code(x)$ 為 $L(x)$ 在 Z 之小數點後之第一個最高有效位。

舉例

令 X = {A, B, C, D} ，其發生概率分別為 p = {1/3, 1/4, 1/6, 1/4} 。

對於 A

${\bar {F}}(A)={\frac {1}{2}}p(A)={\frac {1}{2}}\cdot {\frac {1}{3}}=0.1666...$

在二進位中， Z(A) = 0.0010101010...

L(A) = $\left\lceil \log _{2}{\frac {1}{\frac {1}{3}}}\right\rceil +1$ = 3

code(A) 為 001

對於 B

${\bar {F}}(B)=p(A)+{\frac {1}{2}}p(B)={\frac {1}{3}}+{\frac {1}{2}}\cdot {\frac {1}{4}}=0.4583333...$

在二進位中， Z(B) = 0.01110101010101...

L(B) = $\left\lceil \log _{2}{\frac {1}{\frac {1}{4}}}\right\rceil +1$ = 3

code(B) 為 011

對於 C

${\bar {F}}(C)=p(A)+p(B)+{\frac {1}{2}}p(C)={\frac {1}{3}}+{\frac {1}{4}}+{\frac {1}{2}}\cdot {\frac {1}{6}}=0.66666...$

在二進位中， Z(C) = 0.101010101010...

L(C) = $\left\lceil \log _{2}{\frac {1}{\frac {1}{6}}}\right\rceil +1$ = 4

code(C) 為 1010

對於 D

${\bar {F}}(D)=p(A)+p(B)+p(C)+{\frac {1}{2}}p(D)={\frac {1}{3}}+{\frac {1}{4}}+{\frac {1}{6}}+{\frac {1}{2}}\cdot {\frac {1}{4}}=0.875$

在二進位中， Z(D) = 0.111

L(D) = $\left\lceil \log _{2}{\frac {1}{\frac {1}{4}}}\right\rceil +1$ = 3

code(D) 為 111

演算法分析

前綴碼

山農–菲諾–以利亞碼之輸出為二進位前綴碼，因此可被直接解碼。

令 bcode(x) 為二進位表示法最左側加入小數點而成之小數。舉例而言， code(C)=1010 ，則 bcode(C) = 0.1010 。 對所有 x ，如果沒有任何 y 存在使得

$bcode(x)\leq bcode(y)<bcode(x)+2^{-L(x)}$

則所有的碼可構成前綴碼。

此性質可透過比較 F 和 X 之累積分佈函數，以圖表示出：

由 L 之定義可得

$2^{-L(x)}\leq {\frac {1}{2}}p(x)$

並且由於 code(y) 是由 F(y) 從 L(y) 之後的位元截短而得，故

${\bar {F}}(y)-bcode(y)\leq 2^{-L(y)}$

因此 bcode(y) 必不比 CDF(x) 小。

上圖說明了 $bcode(y)-bcode(x)>p(x)\geq 2^{-L(x)}$ ，因此前綴碼定理成立。

編碼長度

此碼之平均長度為 $LC(X)=\sum _{x\epsilon X}p(x)L(x)=\sum _{x\epsilon X}p(x)(\left\lceil \log _{2}{\frac {1}{p(x)}}\right\rceil +1)$ 。
因隨機變量 X 之 熵 H(X) 滿足

$H(X)+1\leq LC(X)<H(X)+2$

山農–菲諾–以利亞碼之長度約比代編碼資料之熵長約一到二額外位元，故甚少被實用。

參考書目

T. M. Cover and Joy A. Thomas (2006). Elements of information theory (2nd ed.). John Wiley and Sons. pp. 127–128.