丁寧だけど雑

手持ちの参考書にはハフマン符号のみがピックアップされていたのでシャノン符号についてメモ (何してるか知りたいだけなら一番下の要約見て下さい)

そもそも

符号のもつ望ましい性質には、(1)一意復号可能(2)瞬時復号可能(3)平均符号長の最小化がある。

(3)を考える際に必要な処理が平均符号長Lを平均化して評価することである。

シャノン符号

生起確率の大きな記号には短い符号長の符号を、逆に生起確率の小さな記号には長い符号長の符号を割り当てる。

記号 $\displaystyle σ_i$ の生起確率を $\displaystyle P_(σ_i)=q_i$ とすると、直接計算によりその符号語の符号長 $\displaystyle n_i=-log_2 q_i$ となるように符号化するのがシャノン符号である。

実行には以下のステップを踏む。

定常無記憶情報源Uを考える(数式をうまく出力させられなかったのでまた書いておきます)。

次に、 $\displaystyle σ_1,σ_2…,σ_{||u||}$ を生起確率の大きい順に並べる。ここで、これらの生起確率は一般性を失うことなく

$\displaystyle q_1≧q_2≧…≧q_{||u||}$

と仮定する。

次に、累積確率

$Q_j = \sum_{i=1}^{j-1} q_i$

を求め、これを2進数に展開。例えば

$\displaystyle Q_j = 0.8 = \frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\frac{1}{2^4}+\frac{1}{2^5}+…=(0.\dot{1}10\dot{0})_2$ (*)

である。ただし、 $\displaystyle A=(B)_2$ は10進数Aを2進数で表したときの値がBであることを表す。これを次式を満足する $\displaystyle n_j$ 桁まで求める(0が続いたら $\displaystyle n_j$ 桁目まで0を付ける)。

$\displaystyle -log_2 q_j≦n_j＜−log_2 q_j+1$

すなわち

$\displaystyle n_j-1 ＜ -log_2 q_j ≦ n_j (2^{-n_j}≦q_j＜2^{-n_j+1})$ (**)

である。明らかに $\displaystyle q_j$ が大きくなれば $\displaystyle n_j$ は小さくなる。そして、記号 $\displaystyle σ_j$ に対する符号語は小数点以下の2進数で与える。

例えば、(*)(**)で $\displaystyle q_j=0.07$ ならば、 $\displaystyle -log_2 0.07 ≒ 3.84$ であるから $\displaystyle n_j=4$ (これが桁数)となり $\displaystyle σ_j→1100$ と符号化される(0.07の2進数変換 $\displaystyle (0.07)_2=0.1100…$ の小数部先頭4桁に対応)。

また、得られた符号語が全て異なるという保証については以下のように考えることが出来る。

$\displaystyle Q_j$ を2進数展開して求めた符号語は $\displaystyle Q_{j+1}$ から求めた符号語と $\displaystyle n$ 桁目において $\displaystyle 2^{-n_j}$ 以上の差を生じている。

なぜかというと、 $\displaystyle Q_{j+1}-Q_j=q_j$ であるから、 $\displaystyle Q_{j+1}$ は $\displaystyle Q_j$ より $\displaystyle q_j$ だけ大きく、これは(**)より $\displaystyle 2^{-n_j}$ 以上大きいからである(符号化の際、最低でも1箇所が異なるアルファベットをとる)。