tek2 :: OSASK計画

tek2の技術的情報 ^[1]

• (by K^[2], 2004.06.08)
• そのうち書くと思うドキュメントの下書き
• フォーマットに関する情報以外は、このページではなくimpressions^[3]などにお願いします。
• ここでは展開手順をベースに書きます。圧縮のほうは、この展開手順で展開できるようなファイルを作ればいいだけですので。

tek2圧縮 ^[4]

• 基本的にtek1^[5]とほとんど同じです。ということでここでは差異を中心に書きます。
• 最初に主な違いを要約すると次のとおりです。
  • OSACMPヘッダの1バイト目が83→85に。
  • 最初のヘッダでbit1を0にして、bit2以降からいきなりtek2sのビットストリームを開始できる（この場合ブロック数は1）。
  • tek1sでのバイトストリーム開始位置算出のためのフィールドがなくなった（ビットストリームしかないため）。
  • 無圧縮データはビットストリームに混ぜられている。
  • 無圧縮データはUC0を使って使用頻度に応じて短いビットや長いビットが割り当てられ、ハフマン符号ほどではないにしても、ちょっとは圧縮されている。
• ブロック数が2以上の場合は、tek1のときと同じくtek1hを利用します（つまりtek2hのようなものは存在しない）。

tek2s ^[6]

• ここでもtek1sとの違いを中心に書きます。
• まず前述の通りtek1sで真っ先にあったs7符号はありません。いきなりビットストリームで、符号寿命Aの記述から始まるわけです。
• また符号寿命Dなるものを定義して、これをやはり最初は寿命切れにしておきます。
• そしてbyのループで無圧縮バイトが1つ必要になったら、次の手順で無圧縮バイトを得ます（というかもはやtek2sでは無圧縮とはいいがたい気もしますが・・・まあ強いて言えばスライド辞書法的には無圧縮ということで）。
  • (1)もし符号寿命Eが寿命切れだったら、tek2s専用パラメータ群とこの寿命を読み込む。
    • フォーマット的には、寿命、パラメータ群の順番
  • (2)符号寿命Eを1カウント進めて年をとらせる。
  • (3)内部バイト番号をUC0で取得（常に0-255の範囲）。それを256バイトの「内部番号→無圧縮バイト」変換テーブルで変換。
• 符号寿命Eのデフォルトは8192です。
• さてtek2sパラメータについては次のような構成です。
  • ブロックの最初でなければ、更新ビットがある。
  • 次に3bitのビット長パラメータがある（0-6）。
    • 7はリザーブ
  • 以降は、このビット長パラメータによって場合わけされる。
  • ビット長パラメータが0の場合、今から準備する256バイトは全て0。さらに以降のフィールドはすべて存在しない。
  • ビット長パラメータが0でなければ、以降のフィールドが存在する。
  • 1ビットの未使用コード存在フラグ
  • そして展開サイズ256バイト分のtek1s圧縮コード
    • ただし以下の例外がある。
    • 無圧縮バイトの代わりに、ビット長パラメータで指定されたビット数だけ、ビットストリームから切り出す。
    • 最低一致長パラメータの意味が、1～4ではなく2～5になる。
    • 符号寿命A、Bに関する1bitの"0"が略されている。
• とにかくこうして無事に256バイトのデータを得ます。次はこの256バイトのデータからいかにしてUC0パラメータや「内部番号→無圧縮バイト」変換テーブルを作るかです。
• この256バイトのデータの意味は、256種類の無圧縮バイトのそれぞれについて、UC0の何番に所属していたかを示すものです。たとえば、この256バイトの中に0が4つあったとしましょう。これはその4つの無圧縮バイトの頻度が高かったことを意味していて、内部コード0～3に割り振り、UC0パラメータの0番目を2にしなさいという意味です。これによって、この4つのバイトはUC0により、8bitではなく3bitで表現できることになります。
• 同様に次は1のものが256個の中にいくつかあるかを数えます。それがUC0の1番に属するので、その個数をlog2した値をUC0の1番目のパラメータとします。先の続きで、たとえばこれが8個なら、UC0のパラメータは [ 2, 3 ] とここまで決まって、内部コード4～11がこの8個に割り当てられます。これらはUC0によって8bitではなく5bitで表現できるわけです。
• とまあそんな感じで全部割り当てます。それでもし、未使用コード存在フラグが1だったら、最後の内部コード群は一度も出現しないという意味なので、UC0のパラメータを一つ削ります。
• これでおしまいです。

このアルゴリズムについて ^[7]

• tek2sのアルゴリズムは、UC0が小さい数字には短い符号、大きい数字には大きな符号、を割り当てる傾向に着目して、無圧縮バイト部分を頻度順に適当にソートしてその順序を内部コードとして、その内部コードをUC0で符号化すれば無圧縮部分もそれなりに圧縮できるのではないかというものです。
• UC0はハフマン法に比べれば単純な符号なので圧縮率は劣りますが、それでも結構がんばっていて、tek2はLHAと結構いい勝負をします。スライド辞書法のバッファサイズを上げてやれば多くのケースで勝てるくらいの成績です。
• またtek2sでは、いかにtek1のルーチンを流用しつつそれなりの圧縮率を得るかに、心を砕きました。おかげで、tek1にわずかに追加するだけで、tek1/tek2の両対応展開ルーチンが作れます。

こめんと欄 ^[8]