実験B#1

シャノン-ファノ符号化で、分割位置を求めるアルゴリズムを考える。関係ないが、この符号化の名前になってる2人は、ほぼ同時期に同じ符号化を思いついたらしい。エジソンとベルみたいなもんだな。
以下、考えたアルゴリズム。

• すでに出現頻度順にソートされたデータのstart番目からend−1番目までの間で分割位置を求める再帰関数divide(start, end)を考える
• 下の方から区切り位置divをだんだん上昇させていくと、上の和−下の和は単調減少していくので、それが負になる場所をもとめ、その前後の絶対値の比較で分割位置を決定する

1. [初期化]分割の上の和と、下の和の差を保持するdiffを適当に大きな値で初期化する
2. 分割位置divを最後に設定する。div:=end−1
3. [ループ]startからdiv−1までの和をu_sumに代入
4. divからend−1までの和をl_sumに代入
5. もしu_sum−l_sumが負なら8.へ
6. u_sum−l_sumをdiffに代入
7. div = start+1でなければdivを1減らして3.へ
8. [終了処理]もしu_sum−l_sumが負で、かつその絶対値がdiffより大きければdivを1増やす[この時点でdivが分割位置として確定]
9. [前半の処理]startからdiv−1までのデータに対して前半の分割としての処理を行う(符号語"0"の付加)
10. div−start = 1 でなければ(さらに分割が必要)、divide(start, div)を再帰呼び出し
11. [後半の処理]divからend−1までのデータに対して処理をする(符号語"1"の付加)
12. end−div = 1 でなければ、divide(div, end)を再帰呼び出し