Entropy lowerbounds the expected length
エントロピーとは
エントロピーとは情報のランダムさを表す数である。確率変数 X と確率関数 p に対して、X のエントロピーは以下で定義される。
H(X) = - \sum_{x \in X} p(x) \log p(x)
H(X) が大きいとは、情報のランダムさが大きいことを意味する。ランダムさが大きいとは、X の要素が 1 つ与えられたときにそれがどの要素であるのかを予想しにくいという意味である。X の要素が一様に分布していろときにランダムさが最大となる。言い換えると、p(x) = \frac{1}{|X|} のときに H(X) は最大化される。逆に X がある値しか取り得ないとき、H(X) = 0 となり、H(X) は最小化される。
TLDR
エントロピーの小難しい理論を脇におき、とりあえずエントロピーがデータベースと深く関わる例を示す。
データベースに1つのカラム (C) を持つテーブルがあるとする。そのテーブルをディスクに保存するのに必要なビット数の期待値の下限は、テーブルのレコード数を N とすると、N * H(C) とかける。
証明
証明の流れ
- カラム C の各レコードに必要なビット数の期待値の下限を求めると、 H(C) となる。全部で N レコードあるので、テーブルに必要なビット数の期待値の下限は N * H(C) となる。
- カラム C のレコードをビットで表現するためには Huffman-Encoding を用いる。各レコードの値の頻度分析をし、頻度が大きい値ほど短いビット列を割り当てるアルゴリズムである。Huffman-Encoding によって、Prefix-Tree と呼ばれる 2 分木が生成され、木の葉がカラムの値を表す。値を表現するのに必要なビット数は葉の深さ（根からの距離）である。
- これらを使って、カラム C のある行 x を表現するのに必要なビット数 l(x) の期待値 E[l] を評価していく。l は length の l である。
最初に 2 つの不等式を準備しておく。
任意の q: X \to [0, 1] に対して
H(X) = - \sum_{x \in X} p(x) \log p(x) \le -\sum_{x \in X} p(x) \log q(x)
が成り立つ。
任意の2分木において、
\sum_{x \in leaves} 2^{-depth(x)} \le 1
が成り立つ。
証明
H(C) = - \sum_{x \in C} p(x) \log p(x)
ここで、q(x) = \frac{2^{-l(x)}}{c}, c = \sum_{x \in C} 2^{-l(x)} とおき、 Gibbs' Inequality を適用すると、
H(C) = - \sum_{x \in C} p(x) \log (\frac{2^{-l(x)}}{c})
さらに Kraft's Inequality を適用すると、
H(C) \le - \sum_{x \in C} p(x) \log (2^{-l(x)})
log の底を 2 として
H(C) \le - \sum_{x \in C} p(x) \log_{2} (2^{-l(x)}) \\
\le - \sum_{x \in C} p(x) (- l(x)) \\
\le \sum_{x \in C} p(x) l(x) \\
\le E[l]
E[l] はカラムのある行を表現するのに必要なビット数の期待値（平均値）であるため、テーブルに必要なビット数の期待値に対しては以下の不等式が成り立つ。
つまり、エントロピーに N をかけたものがテーブルサイズの期待値の下限となっている。
Discussion