ファイルのエントロピーを求める

仕事の合間にちょっと時間が空いたらいろいろ勉強することにしているのですが、昨日はこのページを読むことにした。

• ホームページ移転のお知らせ - Yahoo!ジオシティーズ

圧縮アルゴリズムの基礎、みたいな感じのページです。
その中に、ファイルの平均情報量（エントロピー）を計算するpythonコードがあったので、それをrubyで書き直してみた。

#! ruby -Ku

#---------- 関数定義 ----------#

# 任意の底 a を持つ x の対数を計算.
def logA( x, a )
  return (Math.log(x)/Math.log(a))
end

# ファイルの内容を読んでエントロピーを計算します.
def entropy( name )
  p "check entropy [#{name}]"
  
  aCount = Array.new
  f = File.open( name, "rb" )
  loop{
    c = f.getc
    break if c == nil
    aCount[ c ] = 0 if aCount[ c ] == nil
    aCount[ c ] = aCount[ c ] + 1
  }
  f.close
  
  # 1st path.
  total = 0
  aCount.each{ |c|
    total = total + c if c != nil
  }
  
  # 2nd path.
  e = 0.0
  ap = 0
  total = total.to_f
  aCount.each{ |c|
    next if c == 0 || c == nil
    ap = c.to_f / total
    e += -ap * logA(ap, 2)
  }
  p " .. entropy  : #{e}"
  p " .. min size : #{e*total/8}(bytes)"
end


#---------- 実行 ----------#
entropy( "cantrbry/alice29.txt" )

同じファイルを処理してみたらほぼ同じ結果になったので、とりあえず間違っていないみたい。

C:\study-comp>ruby comp.rb
"check entropy [cantrbry/alice29.txt]"
" .. entropy  : 4.56768021217727"
" .. min size : 86836.7394737285(bytes)"

このアルゴリズムは、1文字ずつのエントロピーを計算しているわけで、そういう意味での平均情報量。