シャノン-ファノ符号化の分割位置決定アルゴリズム
前に書いたアルゴリズムがちょっとわかりづらいので、考え直してみた。分割位置が上に移動する時、上下の和の差の"絶対値"が単調減少する境界を見つければいいんだから、負かどうかの判定は必ずしも必要ではないな。今の境界の値と次に移動した値の差が増加する点を探せばいい。ここで上と下の差は、今指してる分割位置の2倍を引けば次の分割位置での差になるはずなので、毎度上下の和を求める必要はない。つまり、差の情報を追っているだけで分割位置は見つかるはずだ。
startからend−1間の分割位置div、頻度freq[]、差をdiffとする。
- div:=end−1; diff:=∑(i = start, end−1)freq[i] − freq[end−1]
- div = start+1 なら終了
- |diff| < |diff − 2*freq[div−1]| なら終了
- divを1減らす。diff:=diff − 2*freq[div] として、2.へ
04/01/03 追記: diffの計算を比較を修正
