nopu@wiki
nopu@wiki

情報源符号化

情報源

情報源S
“情報の発生源”

情報源の統計的モデル化
情報源の確率的性質のみを考えること。
情報の全体（標本空間）Ω と，その上の確率測度Pと思えばよい。
  → 情報はΩを標本空間とする確率変数列 X1 X2 ... XL と考える。

無記憶離散的定常情報源S
無記憶：独立
離散的：有限標本空間
定常：同分布
  → Independent and identically-distributed random variables; i.i.d. (独立同分布)
特に，以下のように書くことができる。
\mathcal{S} = \begin{pmatrix} a_1 & a_2 & \cdots & a_M \\ p_1 & p_2 & \cdots & p_M\end{pmatrix}

Markov情報源（Марков）
生起確率が１個前の確率変数値の条件付確率で与えられるモデル。
p(X_{n+1}|X_n,\cdots,X_1) = p(X_{n+1}|X_n)
状態遷移図や遷移行列と一緒に考える。

※このように，有限個の記号で表される情報をデジタル情報という。

情報源符号化

情報源符号化
もとの情報を復元できるという条件の下で，情報を計算機に記憶させること。

符号語
シンボルの集合Kとして，
シンボルの列K*の元を符号語という。

符号化
写像 C:S→K* のこと。
像 C(S) を符号という。
※実際には，SではなくSから生成された列の方を“符号化”する！
  →Cが単射というだけでは一意復号できなくなる。

符号長
符号語に対し，その長さを割り当てる汎関数 L:C(S)→R のこと。
特に，その期待値である平均符号長が重要。

符号のクラス

復号
記号列の符号化C'：S*→C(S)*
C'に対する逆写像D:C(S)*→S*を復号という。
Dが存在するとき一意復号可能(uniquely decodable)という。
  ←Dが存在しないとき特異符号と呼ばれる。

注. 復号は符号化の逆写像ではない！
符号化の逆写像は単に符号が単射なら存在する。

Prop. 符号が単射かつ，符号語列の区切りが一意に定まれば一意復号可能
符号語列の区切りが定まれば，符号語に還元することができる。
Cが単射なら逆写像C(S)→Sが存在するので，これを逐次適用すればよい。
このアルゴリズムで復号Dを構成することができる。

Ex. 単射な固定長符号は一意復号可能
Cの像は常に固定長なので，符号語列から符号語の境界を一意に決めることができる。

Ex. 一意復号可能でない符号
S={a,b,c}, K={0,1}
C(a)=0, C(b)=1, C(c)=01
とする。このとき，以下の符号語列に対して復号は存在しない。
K*∋01
  ←D(01)= ab? c?

可変長符号（非等長符号）
符号長が一定でない符号。

Ex. コンマ符号
S={a,b,c}, K={0,1}
C(a)=1, C(b)=01, C(c)=001
  ←1をコンマと見立てて，符号語列を一意に区切ることができるので，一意復号可能。

瞬時符号
符号の木を描いたとき，
符号語が全て葉に割り当てられている符号

Th. 瞬時符号は一意復号可能
符号の木を根から辿ることで（復号木）必ず一意に復号していくことができる。

Kraft不等式

Lem. K分木の深さに関する等式
K分木（枝が常にK個に割れる木）の葉の深さをliとする。
このとき，以下の等式が成り立つ。
\sum_{l_i} K^{-l_i} = 1
証明は最深層の葉から順に足してゆけば明らか。
和を１に保ったまま一般の木構造に拡張することも容易。

Th. Kraftの不等式
正数列L={li}とする。
1. 長さLを持つ瞬時符号は，次のKraft不等式を満たす。
\sum_{l_i \in L} K^{-l_i} \leq 1
2. LがKraft不等式を満たせば，長さLを持つ瞬時符号が存在する。
注. 瞬時符号とは限らない符合を持ってきて，その長さがKraft不等式を満たしても，必ずしも瞬時符号ではないことに注意！

k次拡大情報源
情報源Sの元をちょうどk個並べた列の全体を，k次の拡大情報源Skという。
  ←例えば2次拡大情報源にはSの元は含まれないことに注意！
拡大情報源の符号化C'(Sk)をk次拡大符号という。

Th. Kraft-McMillan
3. （瞬時復号可能でなくても）一意復号可能ならば，Kraft不等式を満たす。
証明は，一意復号可能ならば任意のkに対するk次拡大符号が特異でないという性質を使う。

情報源符号化定理

エントロピー
情報源SのシンボルKによる符号化を考える。
Sのエントロピーを以下で定義する。
\mathcal{H}_K[S] := -\sum_{i=1}^M p_i \log_K p_i
  ←通常，シンボル数K=2なので，単位は[bit]

平均符号長
符号長{li}に対し，その期待値を平均符号長Lという。
L := \sum_{i=1}^M p_i l_i

Lem. 平均符号長の下限
一意復号可能ならば以下が成り立つ。
L \geq \mathcal{H}_K[S]
[略証]
対数不等式
  x \geq 0 \Rightarrow \ln x \leq x-1
各nに対し，x=\frac{K^{-l_n}}{p_n}とおけば，
  -l_n \ln K - \ln p_n \leq \frac{K^{-l_n}}{p_n} - 1
  -l_n p_n - p_n \log_K p_n \leq \left( K^{-l_n} - 1 \right) \log_K e
nについて和をとれば，右辺が非正になって与式を得る。
  -L + \mathcal{H}_K[S] \leq \left( \sum_{n=1}^M K^{-l_n} - 1 \right) \log_K e \leq 0

Lem. Shannon符号
次のような上限を持つ瞬時符号が存在する。
L < \mathcal{H}_K[S] + 1
[概略]
各pnに対し，正整数lnを次を満たすようにとる。
-\log_K p_n \leq l_n < - \log_K p_n + 1
（幅１の半開区間だからこのようなlnは唯一存在する。）
このとき，Kraft不等式が成り立つ。
 K^{-l_n} \leq p_n 
\therefore \sum_{n=1}^M K^{-l_n} \leq 1
従って，長さlnの瞬時符号が存在する。
作り方から，平均符号長は以下のように押さえ込まれる。
p_n l_n < -p_n \log_K p_n + p_n
\therefore L < \mathcal{H}_K[S] + 1

※頻出ワードほど短い符号語割り当てるという原理に基づいている。
※必ずしも最適とは限らない。

Cor. k次拡大情報源のShannon符号
k次拡大情報源Skに対してShannon符号を作ることにより
L_k \leq \mathcal{H}_K[S^k] + 1
とできる。
Skの元はSの元をk個並べた列だから，以下が示される。
L = \frac{L_k}{k}
\mathcal{H}_K[S^k] = k \mathcal{H}_K[S]
従って以下を得る。
 L \leq \mathcal{H}_K[S] + \frac{1}{k}

k→∞によって，平均符号長がエントロピーに限りなく近いShannon符号が作れることがわかる。

Th. 情報源符号化定理 (Shannon, 1948)
無記憶定常離散的情報源
\mathcal{S} = \begin{pmatrix} a_1 & a_2 & \cdots & a_M \\ p_1 & p_2 & \cdots & p_M\end{pmatrix}
SのシンボルKによる情報源符号化に対して，以下が成り立つ。
\mathcal{H}_K[S] = \inf L
しかも，下限に限りなく近いShannon符号が作れる。

種々の実用符号

Huffman符号(1962)
情報源を逐次縮退しながら符号化する方法。
Huffman符号はコンパクト符号（平均符号長を最小化する２元瞬時符号）である。

Markov情報源
Markov情報源の仮定の下でHuffman符号を作るとさらに短くできる。

run-length符号
繰り返し回数を書いていく方法

Lempel-Ziv符号
ShannonやHuffmanを実用するには，まず情報源の確率分布を推定する作業が必要である。
従って，文字列に対して少なくとも２回アプローチするので，２パスアルゴリズムという。
LZ符号は，確率分布の推定を経ないで符号化する方法である。
「情報源符号化」をウィキ内検索
最終更新：2009年07月11日 21:11
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。