データ系列・符号化・符号長(語頭属性, 語頭符号, 語頭符号化)

データ系列

$$\begin{array}{rl} y \in \chi &\quad\dotso yは集合\chiの要素\\ x^n(=y_1y_2 \dotso y_n) \in \chi^n &\quad\dotso 集合\chiの要素を並べた長さnのデータ系列x^n\\ P(x^n)&\quad\dotso\chi^n上の確率質量凾数(probability\;mass\;function)\\ -\log_2{P(x^n)} &\quad\dotso Shannon情報量(Shannon\;information)\\ \end{array}$$

符号化・符号長

$$\begin{array}{rl} \{0,1\}* &\quad\dotso 0と1の任意長さの系列集合\\ \pi:\chi^n \rightarrow \{0,1\}* &\quad\dotso 符号化(coding)\\ \pi(x^n) &\quad\dotso 符号・符号語(codeword)\\ |\pi(x^n)| &\quad\dotso 符号・符号語(\pi(x^n))の長さ,\,符号長(codeword\;length)\\ \mathcal{l}(x^n)=|\pi(x^n)| &\quad\dotso \mathcal{l}:\chi^n \rightarrow \mathbb{R}^{+}(\mathbb{R}^{+}は正の実数)\\ \end{array}$$ 任意の\(x_1,x_2\in\chi^n\)に対して\(\pi(x_1),\pi(x_2)\)の一方が他方の先頭部分に一致しない性質(語頭属性(prefix property))を持つ符号を語頭符号(prefix code)，語頭符号へ変換する\(\pi\)を語頭符号化(prefix coding)と呼ぶ．