多Byte文字コードの圧縮(2)：エントロピーの比較
前回の多バイト文字コードの圧縮に続いて実験．こんなことをしている場合ではない日に限り，余計なことで手が動く．
# 以下，誤っている部分があるかもしれません．むしろ正しい部分の方が少ないかも．おや？と思う点があればご指摘お願いします．
実際に圧縮アルゴリズムを考える以前に，エントロピー（平均記述長）が短くなるようにすればいいのか，と思いつく．エントロピーは平均記述長とも呼ばれるように，ひとつの事象に割り当てる平均ビット長（ビット長の期待値）を表しており，圧縮の理論的限界を意味している．
ちなみにハフマン符号はエントロピー符号ではあるものの，各符号長が整数になるようにしているので，理論的限界まで圧縮することはできない．これを解決したパーフェクト超人が算術符号，僕が解説するよりWikipediaを見る方が早いと思うので割愛:)
細かい話をすると，k次エントロピーというものもあり，これはk個前までの情報が与えられた際のエントロピー．何もつけずにエントロピーと呼ぶ場合は無記憶情報源（情報源のない）0次エントロピーのことを指すことが多い．
ややこしいことにLZ法のような辞書式圧縮の場合はk次エントロピーを考慮しなければいけなさそう．問題を簡単にするために今回は圧縮はハフマン符号などのエントロピー符号化で行うことを想定し，0次エントロピーだけを考えることにする．
前置きが長くなってしまったけれど，エントロピーが小さい文字列はエントロピーが大きい文字列よりもより（ハフマン符号などにおいて）小さく圧縮できることを意味している．
前回の話題は，日本語だろうが多バイトだろうが，全てバイト単位で扱ってしまえゴルァ，という状況に対して疑問を投げかけた．
今日調べたことは，全てバイトで考えた際のエントロピー (entropy) と，日本語文字2Byteをひとつのシンボルとして扱った場合のエントロピー (entropy_jp) を比較するというもの．
1Byteの場合は，256個の事象が考えられ，2Byteも含める場合には256x256=65536個の事象が考えられる（実際には日本語文字はもっと少ない）．1Byteにばらしてしまうと偏りがなくなってしまうけれど，2Byteで扱えば偏りが大きくなるとエントロピーは小さくなる．
ここで，前回紹介した論文の「頻出の2バイト文字に1バイトを付与」という基本アイディアを少し借りて，ASCII部分である256個の箱はそのままで，頻度の上位k件の2バイト文字をひとつのシンボルとして考慮，それ以外の文字については2つの1バイトに分割した場合のエントロピー (entropy_jp_topk) を計算する．
うまく説明できていないけれど，実験結果を見せます．
今回は2Byte文字コード (euc-jpとShift-JIS) が主役なので，これらについて上記3手法を用いて日本語文書（こころ，舞姫，銀河鉄道の夜）のエントロピーを計算した結果が以下のとおり．それぞれ青空文庫から取得．舞姫と銀河鉄道の夜を選んだ理由は，森鷗外の作品は難しい漢字が多用され，宮沢賢治の作品はひらがなが多い，という偏見と先入観によるもの．
entropy_jp_topkの後ろにある()内の数字は，上位k件のkの値．(1)の場合，最上位の文字をシンボルとしてあつかって，それ以外はバイト単位にばらした場合のエントロピーのこと．
kokoro.txt === entropy kokoro.txt.euc 4.772600 entropy_jp kokoro.txt.euc 7.174739 entropy_jp_topk kokoro.txt.euc(1) 4.736404 entropy_jp_topk kokoro.txt.euc(2) 4.829122 entropy_jp_topk kokoro.txt.euc(3) 5.001506 entropy kokoro.txt.sjis 5.250653 entropy_jp kokoro.txt.sjis 7.174739 entropy_jp_topk kokoro.txt.sjis(1) 5.211651 entropy_jp_topk kokoro.txt.sjis(2) 5.296982 entropy_jp_topk kokoro.txt.sjis(3) 5.373697 entropy kokoro.txt.jis 4.813278 entropy kokoro.txt.utf8 4.639882 maihime.txt === entropy maihime.txt.euc 5.189587 entropy_jp maihime.txt.euc 7.702114 entropy_jp_topk maihime.txt.euc(1) 5.122600 entropy_jp_topk maihime.txt.euc(2) 5.204661 entropy_jp_topk maihime.txt.euc(3) 5.292564 entropy maihime.txt.sjis 5.600600 entropy_jp maihime.txt.sjis 7.702114 entropy_jp_topk maihime.txt.sjis(1) 5.525493 entropy_jp_topk maihime.txt.sjis(2) 5.602208 entropy_jp_topk maihime.txt.sjis(3) 5.680743 entropy maihime.txt.jis 5.190760 entropy maihime.txt.utf8 4.774288 gingatetsudono_yoru.txt === entropy gingatetsudono_yoru.txt.euc 4.744492 entropy_jp gingatetsudono_yoru.txt.euc 6.971019 entropy_jp_topk gingatetsudono_yoru.txt.euc(1) 4.708030 entropy_jp_topk gingatetsudono_yoru.txt.euc(2) 4.880076 entropy_jp_topk gingatetsudono_yoru.txt.euc(3) 4.958933 entropy gingatetsudono_yoru.txt.sjis 5.163408 entropy_jp gingatetsudono_yoru.txt.sjis 6.971019 entropy_jp_topk gingatetsudono_yoru.txt.sjis(1) 5.123109 entropy_jp_topk gingatetsudono_yoru.txt.sjis(2) 5.198795 entropy_jp_topk gingatetsudono_yoru.txt.sjis(3) 5.271911 entropy gingatetsudono_yoru.txt.jis 4.800623 entropy gingatetsudono_yoru.txt.utf8 4.369862
もうちょっと結果が出ると思っていたけれど，最頻出の文字をシンボルとして扱った場合のエントロピーが，全てバイト単位で扱うよりもエントロピーが小さくなっています！
最頻出の2バイト文字は，ひとつのシンボルとして扱ってあげることで，エントロピー符号において，より高い圧縮率が得られそうです．
と綺麗な話で終わりそうだったけれど，そうか日本語文字には元々2バイト割り振られていたから，それを考慮しなければいけなかったのか，ということに記事を書いている段階で気づきましした．でも，キリがいいから今日はここまででやめておきます．．．
上記課題と，k次エントロピーとLZ法の圧縮効率の関係がわかったらまた書くかもしれません．書かないかもしれません．
以上，日曜日の昼下がりの出来事でした．
エントロピーの計算方法と情報量の詳しい説明
(0次) エントロピーは以下の計算式で計算できる．
H(X) = -Σ p(X=x) log_2 p(X=x)
p(X=x)というのは確率変数Xがxとなる確率．たとえばp(X='a')は，ある文書においてaという文字が出現する確率を意味する．
少し詳しい説明をすると，- log_2 p(X=x) が確率p(X=x)で起こる事象xの持つ「情報量」の定義．なぜ，この定義になったかは情報理論の教科書の最初の方に書かれている．
- (1) xの情報量はp(X=x)の関数である
- (2) xの情報量はp(X=x)の減少関数
- 起こりづらい事象の方がたくさん情報を持っている
- (3) 情報の加法性
- p(X=x)p(Y=y) の情報量は，p(X=x)の情報量＋p(Y=y)の情報量
という条件を満たす関数が対数だった，という話．なので，情報量は- log_2 p(X=x)で表現される．
確率変数Xについて，起こりえる全て事象についてp(X=x)の情報量に確率p(X=x)をかけて足しているので，エントロピーはH(X)は，確率変数Xの情報量の期待値であることがわかる．
参考文献
- Thomas M. Cover and Joy A. Thomas (2003). Elements of Information Theory 2nd edition.
- 平田廣則 (2003). 情報理論のエッセンス. 昭晃堂.
