5: 2004-06-03 (木) 14:41:04 [6] | 現: 2024-01-08 (月) 12:59:03 ゲスト [7] | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | * [[tek1]]の続き | + | TITLE:x |
+ | * [[tek1]]の続き [#l23f9928] | ||
-ここでは全体像に影響しない、より些末なことを書く | -ここでは全体像に影響しない、より些末なことを書く | ||
- | * 符号寿命 | + | * 符号寿命 [#g7ccc83d] |
-まず最初は以下の符号寿命が初期値として設定されている。 | -まず最初は以下の符号寿命が初期値として設定されている。 | ||
--符号寿命A:2048 | --符号寿命A:2048 | ||
Line 30: | Line 31: | ||
1111101 : 直前の寿命の1/32倍(端数切捨て) | 1111101 : 直前の寿命の1/32倍(端数切捨て) | ||
- | * UC0符号パラメータの動的補正 | + | * UC0符号パラメータの動的補正 [#e1746eac] |
- | *** 概念 | + | *** 概念 [#a6735e9a] |
-UC0は0以上の整数をエンコードできる符号で、そのためにパラメータテーブルがある。このテーブルがたとえば [ 0, 4, 8, 10, 12 ] の場合、符号長は当然次のようになる。 | -UC0は0以上の整数をエンコードできる符号で、そのためにパラメータテーブルがある。このテーブルがたとえば [ 0, 4, 8, 10, 12 ] の場合、符号長は当然次のようになる。 | ||
--0:1bit (1+0) | --0:1bit (1+0) | ||
Line 41: | Line 42: | ||
-そうであれば、このテーブルを一時的にちょっと細工して、 [ 0, 4, 8 ] にしてしまおう、というのが動的補正である。これだと17-272で1bitの得がある。 | -そうであれば、このテーブルを一時的にちょっと細工して、 [ 0, 4, 8 ] にしてしまおう、というのが動的補正である。これだと17-272で1bitの得がある。 | ||
-そしてさらに、59までしかないのなら、ここに8bitを割り当てるのも合理的ではないだろう。ということで、さらに補正して [ 0, 4, 6 ] にしてしまう。17-80で2bit得する(さっきのを含めると3bitの得)。 | -そしてさらに、59までしかないのなら、ここに8bitを割り当てるのも合理的ではないだろう。ということで、さらに補正して [ 0, 4, 6 ] にしてしまう。17-80で2bit得する(さっきのを含めると3bitの得)。 | ||
- | *** 実装 | + | *** 実装 [#p740d5f8] |
-当然実装に際しては、エンコード側とデコード側とで同じ最大値を予測していないと、食い違いが生じてデコードできなくなる。ということでそれを説明する。 | -当然実装に際しては、エンコード側とデコード側とで同じ最大値を予測していないと、食い違いが生じてデコードできなくなる。ということでそれを説明する。 | ||
--byの値のときは、残りデコードバイト長-1が最大値(-1するのは、そもそもbyがUC0の値を+1して利用しているため) | --byの値のときは、残りデコードバイト長-1が最大値(-1するのは、そもそもbyがUC0の値を+1して利用しているため) | ||
Line 53: | Line 54: | ||
--dsでは、これとは逆にブロックのデコードとともに最大値が大きくなっていくという性質がある。したがって現在の修正UC0パラメータで表現可能な最大値を控えておき、これよりも予測最大値が大きくなったら再構成を行えばよい。 | --dsでは、これとは逆にブロックのデコードとともに最大値が大きくなっていくという性質がある。したがって現在の修正UC0パラメータで表現可能な最大値を控えておき、これよりも予測最大値が大きくなったら再構成を行えばよい。 | ||
- | * UC0符号パラメータのフォーマット | + | * UC0符号パラメータのフォーマット [#jec768c6] |
- | *** 基本 | + | *** 基本 [#s4c2098e] |
-ここは結構ややこしい。ブロックサイズが最大8MBなので、UC0でエンコードされる数字も最大で8M程度までありうるが、これはつまりパラメータテーブルの各要素を単純に並べて最後にターミネータをつけるような方法だと、1要素あたり5bitを要し、 [ 0, 4, 8, 10, 12 ] なら30bitも要してしまうことになる。これは4バイト近くであり、こんなものをそのまま使うわけにはいかない。 | -ここは結構ややこしい。ブロックサイズが最大8MBなので、UC0でエンコードされる数字も最大で8M程度までありうるが、これはつまりパラメータテーブルの各要素を単純に並べて最後にターミネータをつけるような方法だと、1要素あたり5bitを要し、 [ 0, 4, 8, 10, 12 ] なら30bitも要してしまうことになる。これは4バイト近くであり、こんなものをそのまま使うわけにはいかない。 | ||
--短くエンコードできれば、パラメータ切り替えのオーバヘッドが減り、寿命を短く設定できるようになり、つまりそのときそのときでの最適なパラメータを使う機会が増え、結果的に圧縮率が上がるというわけである。 | --短くエンコードできれば、パラメータ切り替えのオーバヘッドが減り、寿命を短く設定できるようになり、つまりそのときそのときでの最適なパラメータを使う機会が増え、結果的に圧縮率が上がるというわけである。 | ||
--またここが少々ややこしかったとしても頻度は低いので展開速度に影響しにくい。だから遠慮なく(?)短く表現することを心がけた。 | --またここが少々ややこしかったとしても頻度は低いので展開速度に影響しにくい。だから遠慮なく(?)短く表現することを心がけた。 | ||
- | --ここに示す方法では [ 0, 4, 8, 10, 12 ] を19bitで表現できる(0010101110111100001)。 | + | --ここに示す方法では [ 0, 4, 8, 10, 12 ] を19bitで表現できる(1101010001000010010)。 |
- | --30→19ではたいした事はないと思うかもしれないが、 [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ] も19bitになるので(0000000000000100001)、ここの複雑さに失望しないでほしい(まあtek1の中で一番複雑だというだけで、本質的にはそんなに複雑ではないのだが。Cのソースで50行ほど)。これは70→19に匹敵する。 | + | --30→19ではたいした事はないと思うかもしれないが、 [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ] も19bitになるので(1111111111111010010)、ここの複雑さに失望しないでほしい(まあtek1の中で一番複雑だというだけで、本質的にはそんなに複雑ではないのだが。Cのソースで50行ほど)。これは70→19に匹敵する。 |
- | *** モードヘッダ | + | *** モードヘッダ [#g6b770f7] |
- | -最初はモードヘッダである。上記の例だと最初の0001の4bitがこれに相当。 | + | -最初はモードヘッダである。上記の例だと最初の0010の4bitがこれに相当。 |
--(ここでも下位を右側に書くために、ストリームを右から左へ記述していることに注意) | --(ここでも下位を右側に書くために、ストリームを右から左へ記述していることに注意) | ||
--モード0とモード1 | --モード0とモード1 | ||
- | 000 : パラメータの最大値は 0- 4、モード0 | + | 001 : パラメータの最大値は 0- 4、モード0 |
- | 100 : パラメータの最大値は 0- 4、モード1 | + | 101 : パラメータの最大値は 0- 4、モード1 |
- | 010 : パラメータの最大値は 5- 8、モード0 | + | 011 : パラメータの最大値は 5- 8、モード0 |
- | 110 : パラメータの最大値は 5- 8、モード1 | + | 111 : パラメータの最大値は 5- 8、モード1 |
- | 0001 : パラメータの最大値は 9-12、モード0 | + | 0010 : パラメータの最大値は 9-12、モード0 |
- | 1001 : パラメータの最大値は 9-12、モード1 | + | 1010 : パラメータの最大値は 9-12、モード1 |
- | 0101 : パラメータの最大値は13-16、モード0 | + | 0110 : パラメータの最大値は13-16、モード0 |
- | 1101 : パラメータの最大値は13-16、モード1 | + | 1110 : パラメータの最大値は13-16、モード1 |
- | 00011 : パラメータの最大値は17-20、モード0 | + | 00100 : パラメータの最大値は17-20、モード0 |
- | 10011 : パラメータの最大値は17-20、モード1 | + | 10100 : パラメータの最大値は17-20、モード1 |
- | 01011 : パラメータの最大値は21-24、モード0 | + | 01100 : パラメータの最大値は21-24、モード0 |
- | 11011 : パラメータの最大値は21-24、モード1 | + | 11100 : パラメータの最大値は21-24、モード1 |
--ここまでのまとめ: | --ここまでのまとめ: | ||
---最後のビット(一番左のビット)がモードに対応している | ---最後のビット(一番左のビット)がモードに対応している | ||
Line 81: | Line 82: | ||
---残りの部分(最初の部分)については、1の数を数えて0がきたら終わりで、パラメータの最大値が8づつ増えている。 | ---残りの部分(最初の部分)については、1の数を数えて0がきたら終わりで、パラメータの最大値が8づつ増えている。 | ||
--モード2 | --モード2 | ||
- | 00111 : パラメータの最大値は 0- 4、モード2 | + | 01000 : パラメータの最大値は 0- 4、モード2 |
- | 10111 : パラメータの最大値は 5- 8、モード2 | + | 11000 : パラメータの最大値は 5- 8、モード2 |
- | 001111 : パラメータの最大値は 9-12、モード2 | + | 010000 : パラメータの最大値は 9-12、モード2 |
- | 101111 : パラメータの最大値は13-16、モード2 | + | 110000 : パラメータの最大値は13-16、モード2 |
- | 0011111 : パラメータの最大値は17-20、モード2 | + | 0100000 : パラメータの最大値は17-20、モード2 |
- | 1011111 : パラメータの最大値は21-24、モード2 | + | 1100000 : パラメータの最大値は21-24、モード2 |
--ここまでのまとめ: | --ここまでのまとめ: | ||
- | ---最初の3bitはすべて111 | + | ---最初の3bitはすべて000 |
---モードは2しかない | ---モードは2しかない | ||
- | ---ちょうど上記でモードビットを外して最初に111をつけた形式になっている | + | ---ちょうど上記でモードビットを外して最初に000をつけた形式になっている |
- | *** 本体 | + | *** 本体 [#d42de4c9] |
-基本的な考えとしては、パラメータ値そのものではなく、前の項から次の項を求めるための差分をエンコードしていく感じになる | -基本的な考えとしては、パラメータ値そのものではなく、前の項から次の項を求めるための差分をエンコードしていく感じになる | ||
--大雑把な傾向として、パラメータ列の値はその前後の値に近くなるため | --大雑把な傾向として、パラメータ列の値はその前後の値に近くなるため | ||
Line 102: | Line 103: | ||
-デコード方法0: | -デコード方法0: | ||
--モード0で、さらに直前の項が0でない場合はこれになる | --モード0で、さらに直前の項が0でない場合はこれになる | ||
- | --"0"がくるまでの"1"の数を数えて、それにさらに1を加えたものが差分値 | + | --"1"がくるまでの"0"の数を数えて、それにさらに1を加えたものが差分値 |
-デコード方法1: | -デコード方法1: | ||
--モード1か、もしくはモード0かつ直前の項が0の場合はこれになる | --モード1か、もしくはモード0かつ直前の項が0の場合はこれになる | ||
- | --"0"がくるまでの"1"の数を数えたものが差分値 | + | --"1"がくるまでの"0"の数を数えたものが差分値 |
-デコード方法2: | -デコード方法2: | ||
--モード2の場合はこれになる | --モード2の場合はこれになる | ||
--まず最初は符号ビット、これが0なら0以上、これが1なら-1以下 | --まず最初は符号ビット、これが0なら0以上、これが1なら-1以下 | ||
- | --"0"がくるまでの"1"の数を数えて、符号ビットが1だったらさらにそれに-1をXORしたものが差分値 | + | --"1"がくるまでの"0"の数を数えて、符号ビットが1だったらさらにそれに-1をXORしたものが差分値 |
-(註)モード0でも直前の項に限ってデコード方法1になるのは、パラメータの最初の項のほうに0をいくつか並べたいときがあるからである | -(註)モード0でも直前の項に限ってデコード方法1になるのは、パラメータの最初の項のほうに0をいくつか並べたいときがあるからである | ||
-ターミネーション(終端処理) | -ターミネーション(終端処理) | ||
Line 117: | Line 118: | ||
---この終端方法はモード0でしか使えないし、しかも最後のパラメータが4の倍数のときにしか使えない | ---この終端方法はモード0でしか使えないし、しかも最後のパラメータが4の倍数のときにしか使えない | ||
--これはどのモードでも使える方法だが、たとえばパラメータの最大値の範囲が9-12の場合、次の項が13となるようなそんな差分を受け取ったとしよう、これはもちろんありえないのでターミネーションする | --これはどのモードでも使える方法だが、たとえばパラメータの最大値の範囲が9-12の場合、次の項が13となるようなそんな差分を受け取ったとしよう、これはもちろんありえないのでターミネーションする | ||
- | ---この場合13になるのに必要なだけの"1"を数えたら、もう"0"を待たずに打ち切る | + | ---この場合13になるのに必要なだけの"0"を数えたら、もう"1"を待たずに打ち切る |
- | ---14などをエンコードする意味はないので、もはやターミネーションのための13しかありえず、最後の"0"が省略されているとみなすのである | + | ---14などをエンコードする意味はないので、もはやターミネーションのための13しかありえず、最後の"1"が省略されているとみなすのである |
--モード2で、次の項が-1となるようなそんな差分を受け取ったとしよう、これもありえないのでターミネーションする | --モード2で、次の項が-1となるようなそんな差分を受け取ったとしよう、これもありえないのでターミネーションする | ||
- | ---この場合も-1になるのに必要なだけの"1"を数えたら、もう"0"を待たずに打ち切る | + | ---この場合も-1になるのに必要なだけの"0"を数えたら、もう"1"を待たずに打ち切る |
---前の項が0だった場合、符号ビットが1だった時点でもう打ち切る | ---前の項が0だった場合、符号ビットが1だった時点でもう打ち切る | ||
- | *** フッタ | + | *** フッタ [#rb3607ca] |
-特定の条件でのみフッタが存在する | -特定の条件でのみフッタが存在する | ||
--モード0かモード1で、パラメータの数が2つ以上で、さらに最後のパラメータが0ではないとき | --モード0かモード1で、パラメータの数が2つ以上で、さらに最後のパラメータが0ではないとき | ||
- | -フォーマットは例によって"0"がくるまで"1"の数を数えるというものである | + | -フォーマットは例によって"1"がくるまで"0"の数を数えるというものである |
-この値を、最後のパラメータから差し引く | -この値を、最後のパラメータから差し引く | ||
--モード0やモード1ではパラメータが増える一方で最後を小さい値にすることができないため | --モード0やモード1ではパラメータが増える一方で最後を小さい値にすることができないため | ||
--最後だけ減少で、あとはパラメータを増加させたいという状況が結構あるのでこの仕組みがある | --最後だけ減少で、あとはパラメータを増加させたいという状況が結構あるのでこの仕組みがある | ||
- | --差し引く前の最後のパラメータが10だとしたら、当然"1"の数は10より多いことはありえないので、"1"が10個続いたら"0"は省略されているとみなして1ビット節約する | + | --差し引く前の最後のパラメータが10だとしたら、当然"0"の数は10より多いことはありえないので、"0"が10個続いたら"1"は省略されているとみなして1ビット節約する |
- | *** デフォルトパラメータ | + | *** デフォルトパラメータ [#v1d01645] |
-これだけの圧縮をしてパラメータを短くまとめても、それでも対tek0では小さいファイルで負ける | -これだけの圧縮をしてパラメータを短くまとめても、それでも対tek0では小さいファイルで負ける | ||
--なぜならtek0はパラメータが固定されており、圧縮ファイル内に書かなくていい分だけ有利だからである | --なぜならtek0はパラメータが固定されており、圧縮ファイル内に書かなくていい分だけ有利だからである | ||
Line 169: | Line 170: | ||
---つまり1~4 | ---つまり1~4 | ||
- | * tek1h | + | * 最低保証値 [#s3301330] |
+ | -tek1は非常にスケーラブルな形式であり、展開ルーチン側の負担は小さくないと思うので、ここで一つ基準を設ける。 | ||
+ | --これは汎用の場合の最低値規定であって、対象データが限定される場合はこの限りではない。 | ||
+ | -UC0のパラメータテーブルは最低でも32個(=0番から31番)は利用可能でなければいけない。それ以上は環境によってサポートがあったりなかったりしてよい。 | ||
+ | -スライド辞書のバッファサイズ(=MD値)は最低で32KBである。32bit環境であれば(かつメモリの制約が厳しくないなら)、1MBくらいまではサポートしてほしいところである。 | ||
+ | -対応可能ファイルサイズについては最低でも2GB、符号寿命の値、およびby、lz、cpの値は最低でも24bitは利用できることを保証すること。 | ||
+ | -tek1hについては、レベル0のみ(=tek1hのノンサポート)であってもよいが、できればレベル2くらいまでのサポートがあるほうが好ましい。 | ||
+ | * tek1h [#nbec98dc] | ||
- | * こめんと欄 | + | |
+ | * こめんと欄 [#lc851bdc] | ||
#comment | #comment |
(This host) = http://osask.net