bzip2
Wikipediaみたらbzip2はブロックソート→MFT→ハフマンって書いてあるじゃない
これはうちでもできる!?と思ってVB.NETで実装したら普通にtarでbzip2したのより大きくなる・・・
なんでだろー悔しくてソースは読んでない
久しぶりだけどこの程度のアルゴリズムは間違ってないはず・・・
MFTした時点でハフマンは単に出現率の単純なのでいいはず、適応型ハフマンにする意味はたぶんない
ブロックソートで4バイト増えるのはどうしようもない
ハフマン木構築のために出現率を4バイト×256個(1バイトの各値)ヘッダーにつけたけど1KB負けてるどころじゃない
その他のヘッダーを全く付けてないので負けるわけないとおもってたら・・・なんや、圧縮率でLZ77に負ける始末
くやしいけどここまできたらbzip2読むか
ちなみにブロックソートとMFTを繰り返したらどうなるのかと思って試してみたら
大体のファイルで30〜40回繰り返すことで0の出現確率が0.3に近づく
そんで0.3前後をピークにわずか1、2回で平滑化される
なにこれ、ちょっと面白い