符号理論
符号語の長さは以下で書き表される。
l ( C ( x ) ) {\displaystyle l(C(x))}
期待される符号の長さは以下で書き表される。
l ( C ) = ∑ x ∈ X l ( C ( x ) ) P [ X = x ] {\displaystyle l(C)=\sum _{x\in {\mathcal {X}}}l(C(x))\mathbb {P} [X=x]}
符号語の連結は C ( x 1 , . . . , x k ) = C ( x 1 ) C ( x 2 ) . . . C ( x k ) {\displaystyle C(x_{1},...,x_{k})=C(x_{1})C(x_{2})...C(x_{k})} である。
空文字列の符号語は、空文字列そのものである。
C ( ε ) = ε {\displaystyle C(\epsilon )=\epsilon }
データは確率変数 X : Ω → X {\displaystyle X:\Omega \rightarrow {\mathcal {X}}} として見ることができる。ここで、 x ∈ X {\displaystyle x\in {\mathcal {X}}} は確率 P [ X = x ] {\displaystyle \mathbb {P} [X=x]} で現れるものとする。
データはアルファベット Σ {\displaystyle \Sigma } からなる文字列(単語)で表されるものとする。
符号は以下の関数である。
C : X → Σ ∗ {\displaystyle C:{\mathcal {X}}\rightarrow \Sigma ^{*}} (空文字列がアルファベットの一部でない場合は Σ + {\displaystyle \Sigma ^{+}} )
C ( x ) {\displaystyle C(x)} は x {\displaystyle x} と関連する符号語である。