データ圧縮：平均情報量(エントロピー）を求める

可逆圧縮アルゴリズムのシャノン符号とハフマン符号関連で、平均情報量(エントロピー）を求めるスクリプトを書いてみました。Perlである必要性は全くありませんが、最近はJavaとPerl以外はご無沙汰でして、手っ取り早いPerlで書きました。

• Algorithms with Python / シャノン・ファノ符号とハフマン符号

上のリンクのページにある数式のあたりを参考にさせていただきました。このページのシリーズは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);