例題集

冗長度

知識・記憶レベル   難易度: ★★
271語からなる言語系がある.そのうちの15語が1/16,残りは1/4096の頻度で使用されているという.また,すべての単語の長さは等しいものとする.この言語のエントロピー,冗長度を求めなさい. また,この言語での長さ1000単語の文章は,うまく符号化すると,どれだけ短い文章で(何単語)で表現できるか答えなさい.
まず,この言語のエントロピーを$H_{real}$と表すとすると,次のように求められる. \begin{eqnarray} H_{real}&=&15\times \frac{1}{16}\times \log_2 16+(271-15)\times \frac{1}{4096}\times \log_2 4096 \\ &=&\frac{9}{2}\\ &=&4.5 \ \mathrm{[bit/word]} \end{eqnarray} もし,すべてが同じ頻度で使用される場合のエントロピーを$H_{max}$とすると, \begin{equation} H_{max}=\log_2 271 \approx 8.082 \ \mathrm{[bit/word]} \end{equation} となる.従って,相対エントロピー$h$は次のようになり, \begin{equation} h=\frac{H_{real}}{H_{max}}=\frac{4.5}{8.082}\approx 0.557 \end{equation} 冗長度は次のように求められる. \begin{equation} 1-h \approx 0.443 \end{equation} また,1000単語の文章は,相対エントロピー$h$より, \[1000\times h = 1000 \times 0.557 = 557 \mathrm{[words]} \] つまり,557単語で表現できることになる.