最悪ケースエントロピー、またの名を情報論的下限、およびシャノンエントロピーと経験エントロピーとの関係

はじめに

本ブログでは現在、圧縮文字列索引に関する連載を書いているが、そこのpart3で「経験エントロピー」なる概念が登場した。そこではさらっと流してしまったので、改めて丁寧に解説する記事も別に書こう、ということで本エントリに独立させることにした。

詳細な議論に入る前にざっくりと概観を述べておく。

最悪ケースエントロピーとは、情報源を符号化する際、すべての要素に等しい長さで符号を割り当てた場合の最短符号長であり、全ての要素の発生確率が均一な場合のシャノンエントロピーに一致する。これは、情報源に仮定を置かない場合、簡潔データ構造の目標サイズの目安であることから情報論的下限とも呼ばれることがある。一方、経験エントロピーとは、観測されているデータの経験分布を情報源の確率分布と仮定したときのシャノンエントロピーの値であり、情報源ではなく観測されたデータから個別に求まる。発生に偏り・傾向があることが期待される情報源には、こちらの値が簡潔データ構造が目指す圧縮の目安となる。