数学的な知識を高めるために、ちょっくらエントロピーについて学びますかね！！
エントロピーってそもそもなんだっけ？
情報量（じょうほうりょう）やエントロピー（英: entropy）は、情報理論の概念で、あるできごと（事象）が起きた際、それがどれほど起こりにくいかを表す尺度である。
つまり、あるデータを表現するのに必要最低限な情報量は何か、ということですね。AとBの２パターンしかないならば、A=0,B=1を割り当ててある事がわかっていればABABは0101(bit)で、0x5(hex)で表現できます、とか。
人はエントロピーに基づいて、より少ないデータ量で情報を表現しようといろいろ試行錯誤してきた。
シャノン符号化
一言でまとめると、累積出現確率がそのまま表現になると。
例えば、 以下テストデータで考える（スペースは見やすくするための区切り）。
- SRC = AABB ABAB ABAB CAAA
A=00,B=01,C=10(bin) とすると、2bit × 16 = 32bit
-
SRC = 00000101 00010001 00010001 10000000 (bin)
-
P(A) = 9/16 = 0.5625(dec)
-
P(B) = 6/16 = 0.375(dec)
-
P(C) = 1/16 = 0.0625(dec)
-
li(A) = ceil ( ln( 0.5625) ) = ceil(0.830075) = 1
-
li(B) = ceil ( ln( 0.375) ) = ceil(1.415037) = 2
-
li(C) = ceil ( ln( 0.0625) ) = ceil(4) = 4
-
累積P(A) = 0.0 (dec) = 0.0(hex)
-
累積P(B) = 累積P(A) + P(A) = 0.0 + 0.5625 = 0.5625 = 0.101(hex)
-
累積P(C) = 累積P(N) + P(B) = 0.5625 + 0.375 = 0.9375 = 0.111(hex)
-
a(A) = 0
-
a(B) = 10
-
a(C) = 1110
-
SRC = 00000101 00010001 00010001 10000000 (32bit)
-
DST = 001010 010010 010010 1110000 (25 bit)
ハフマン符号化
出現頻度の高いものには、短いbitを割り当てましょう、というアイデア。
- P(A) = 9/16 = 0.5625(dec)
- P(B) = 6/16 = 0.375(dec)
- P(C) = 1/16 = 0.0625(dec)
P(B)とP(C)が低い。そこで、ここにnode(B+C)を作る。
- P(A) = 0.5625
- P(B+C) = 0.4275
ここで、新しいnode(A+B+C)を作る。この時点で全部の要素を処理したので、結果としてはこのA+B+Cがrootになる。
で、符号化をしてみる。
- root(A+B+C) ⇒ A ： a(A) = "0"
- root(A+B+C) ⇒ node(B+C) ⇒ B : a(B) ⇒ "1"+"0" = "10"
- root(A+B+C) ⇒ node(B+C) ⇒ C : a(C) ⇒ "1"+"1" = "11"
これに基づくと、なんと23bitまで小さくなりますね！
- SRC = 00000101 00010001 00010001 10000000 (32bit)
- DST = 001010 010010 010010 11000 (23bit)
ここまでの手段の弱点は？
例えば、再頻度たるAを表現するだけでも、1bitを使ってしまう！ということはこれ以上情報量は少なくすることはできない……
そこで出てきたアイデアが「複数bitの記号でそれ以上の情報を表現してしまえ」と。
極端な言い方をすれば、「3.14」といったら「159265...」と続き、「1.732」といったら「0508...」と続く、とわかる。
こんな感じで「ある数列を表現する、もっとコンパクトな表現手段」という方向にストーリーは動いていきます。
算術符号化
0~1の間の区間を、データ出現頻度に応じて分割する。
次のデータがきたら、その小区間もまた分割する…を繰り返せば
複数のデータ列を１つの小数で表現できるよね、という手法。
レンジ符号化
「小数演算やだなあ」という人/システム向けに更に練りこまれた符号化手段。算術符号化では0~1の区間内の話だったが、これをdynamicに定数倍しながら処理する。バイト単位で入出力できるとか書いていたりするが、うーん・・・ とりあえず保留。
物語は Asymmetric numeral system へ続く
＜次回予告＞ https://arxiv.org/pdf/1311.2540.pdf を徐々に読み解いて、もう少し詳しくなるよ！