データ圧縮:平均情報量(エントロピー)を求める
可逆圧縮アルゴリズムのシャノン符号とハフマン符号関連で、平均情報量(エントロピー)を求めるスクリプトを書いてみました。Perlである必要性は全くありませんが、最近はJavaとPerl以外はご無沙汰でして、手っ取り早いPerlで書きました。
上のリンクのページにある数式のあたりを参考にさせていただきました。このページのシリーズはPythonを使った説明なのですが、Python抜きにしても、とてもわかりやすくまとめられています。
# 20081115修正版 use strict; use warnings; my $sample = shift or (print "usage: $0 sample-string\n" and exit(0)); my $size = length $sample; my @c = map { 0 } [0..255]; for (split //, $sample) { ++$c[ord($_)] } my $total = 0; for (0..255) { my $c = $c[$_]; next unless $c; my $p = $c / $size; my $e = - $p * log($p) / log(2); printf "%s : %3d/%3d : %1.6f\n", chr, $c, $size, $e; $total += $e; } printf "%3d * %1.6f = %1.6f\n", $size, $total, $size * $total; __END__ 以下は古いバージョン sub entropy { my $rate = shift; return -1 * $rate * log($rate) / log(2); } my $sample = shift or (print "usage: $0 sample-string\n" and exit(0)); my $length = length $sample; my %m = (); for (split //, $sample) { $m{$_} = 0 unless defined $m{$_}; ++$m{$_}; } my $sum = 0; while (my ($ch, $n) = each %m) { my $entropy = entropy($n / $length); printf "%s : %3d/%3d : %1.8f\n", $ch, $n, $length, $entropy; $sum += $entropy; } printf " %d * %1.8f = %1.8f\n", $length, $sum, ($length * $sum);