符号
#情報理学I
情報源アルファベット：$ A
情報源から出力される記号の集合
符号アルファベット：$ B
符号化された記号列の集合
例：2元アルファベット： {0, 1}
このとき、$ A上の記号列から$ B上の記号列への関数（写像）を符号（code）という。
$ C: A^* \rightarrow B^*
符号化された記号列を符号語という
ここで、
$ A^* = A \cup A^2 \cup ...
$ B^* = B \cup B^2 \cup ...
$ X^nは$ Xのn次拡大アルファベット
情報理学I では、$ A^nの要素$ x_1x_2...x_nについて、記号列を
$ C(x_1x_2...x_n) = C(x_1)C(x_2)...C(x_n)
と表すことができる場合のみを考える。
すべての$ x\in Aに対して$ C(x)の長さが等しいとき$ Cは固定長な符号であるという。$ \leftrightarrow可変長
符号化の条件
非瞬時符号：受け取った符号語だけでは復号できない
https://gyazo.com/2b75f64a7d76e72239d360a48678d523
例： 0001 を受け取ったとき、 「あう」「あえ」のどちらか判断できない。00011 も「あうい」「あえ」が区別できない。
瞬時符号：ある符号語が別の符号語の頭部に一致しない
https://gyazo.com/3c9b48cb5858fd8b66a8c5733b2e40f1
符号の木