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

データ系列

$$\begin{array}{rl}y\in \chi & \dots y\mathrm{は}\mathrm{集}\mathrm{合}\chi \mathrm{の}\mathrm{要}\mathrm{素}\\ x^n(=y_1{y}_2\dots y_n)\in {\chi }^n& \dots \mathrm{集}\mathrm{合}\chi \mathrm{の}\mathrm{要}\mathrm{素}\mathrm{を}\mathrm{並}\mathrm{べ}\mathrm{た}\mathrm{長}\mathrm{さ}n\mathrm{の}\mathrm{デ}\mathrm{ー}\mathrm{タ}\mathrm{系}\mathrm{列}{x}^n\\ P(x^n)& \dots {\chi }^n\mathrm{上}\mathrm{の}\mathrm{確}\mathrm{率}\mathrm{質}\mathrm{量}\mathrm{凾}\mathrm{数}(probabilitymassfunction)\\ -{\log }_{2}P(x^n)& \dots Shannon\mathrm{情}\mathrm{報}\mathrm{量}(Shannoninformation)\end{array}$$

符号化・符号長

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