こんばんは、川合です。
tek4の仕様がだいたい固まってきたところで、まだ肝心の圧縮ルーチ
ンを書いていないのですが、とりあえずお知らせというか、中間報告で
す。
http://k.hideyosi.com/bim2bi4l.lzh (109KB)
改善点は少ないですが、以下のとおりです。
・dtk1s.cとdtk2s.cをちょっとだけ改良
・dtk3s.cとdstk4s.cをとりあえず追加
・bim2binがtek2の展開に失敗するバグを修正
・tek3のフォーマットを微妙に変更（またかよ）
あっきぃさんの報告によると、BSオプションを指定するとうまく圧縮
できない場合があるらしいですが、そのバグはまだ直していません。
tek4ができてから直します。
---
tek1〜tek4について一言で説明すると、大体こういう感じになりそう
です。
tek1 : s7s符号を使ったLZ圧縮
tek2 : s7s符号+s7符号+簡単なビット列符号を使ったLZ圧縮
tek3 : UC0符号を使ったLZ圧縮
tek4 : UC1符号を使ったLZ圧縮
UC0符号というのは、小さい数字は少ないビット数で、大きい数字は
多いビット数で表現する、そういう符号です。暗黙の了解として、小さ
い数字の出現頻度は高くて、大きい数字の出現頻度は低い、ということ
を仮定しています。
LZ圧縮の場合、たとえば「10バイト前から4文字コピー」みたいなデ
ータがたくさん出てくるわけですが、この10や4という数字について、
大きい数字はあまり出てこない、と決め付けているわけです。つまり、
バイト列の一致は近い手前でよく見つかるだろうとか、一致長はそんな
に長くはならないだろう、というわけです。・・・まあ一致長がすごく
長くなる場合もありますが、そんな場合は、猛烈に圧縮率が稼げるとき
でもあり、そこで10ビットや20ビット損してもそれほど問題はないだろ
うと考えるわけです。
現実的なデータを眺めてみると、確かに大きい数字の頻度は小さい数
字よりも少ないものがほとんどで、この仮定はそれなりに成立していま
す。だからこそtek3はそれなりに圧縮が効いているわけです。・・・そ
の一方で、たとえば一致長の数字を眺めていると、3バイト一致と4バイ
ト一致の回数を比べると、4バイト一致のほうが頻繁に出現している場
合があります。また、5バイト一致が一度も出現しないのに、6バイト一
致がたくさん出現しているときもあります。
UC0では、このような逆転現象にうまく対処できません。3に短い符号
を割り当てて4にはそれと同じかそれより長い符号を割り振ってしまい
ます。また使われることのない5にも符号を割り当てますし、6はその5
と同じかそれより長い符号を割り当てます。
これを克服するのがUC1です。UC1では、数字を一度変換表で内部変換
し、頻度が一番高い数字を0にして、その次を1、その次を2にします。
そしてこの変換した数字をビット列に変換するわけです。頻度順に番号
を並べ替えるので、一度も出現しない数字は後ろのほうに固まります。
そして出現しないと分かっているので、これらには内部番号や対応する
ビット列を割り当てません。これにより圧縮率を上げてやろうというわ
けです。
この手法は旧tek2が無圧縮バイト列にのみ適用していたものでしたが
今回は一致長や参照距離などの全ての数値にこれを適用します。これに
よりさらなる圧縮率向上を狙います。ただ、UC1を符号化する際にはUC0
と同等の情報に加えて内部変換表に相当する情報をエンコードする必要
があり、これがややつらいところです。ここが長くなると、結局全体と
しては逆効果になりかねません。単純にどの数字を使うか使わないか記
述するだけでも、0-999をカバーするなら1000ビット必要です。さらに
順番に関する情報をつけるとなるとさらに長くなるでしょう。
変換して効果がありそうなのは値の小さい範囲だけなので（大きいと
ころでは変換してもしなくてもあまり変わらない・・・どうしてかとい
うと結局全体としては大きい数字は相変わらず出現頻度が低めだから）
、ある値の範囲だけを変換の対象にして（たとえは0-255）、その他は
「数字＝内部番号＋定数」として小さな変換表で十分な効果を出せるよ
うにしています。これにより、無事に期待通りの圧縮率を達成できるだ
ろうと考えています。
そういう動作をする展開ルーチンを適当に作ってみました。500行に
満たないようなので、とりあえず悪くなさそうです。たぶん展開速度も
tek3の1〜2割増しで済むでしょう。
それでは。
--
川合 秀実(KAWAI Hidemi)
OSASK計画代表 / システム設計開発担当
E-mail:kawai !Atmark! osask.jp
Homepage http://osask.jp/