5: 2004-06-03 (木) 14:41:04 |
6: 2004-06-07 (月) 23:14:33 |
| --短くエンコードできれば、パラメータ切り替えのオーバヘッドが減り、寿命を短く設定できるようになり、つまりそのときそのときでの最適なパラメータを使う機会が増え、結果的に圧縮率が上がるというわけである。 | | --短くエンコードできれば、パラメータ切り替えのオーバヘッドが減り、寿命を短く設定できるようになり、つまりそのときそのときでの最適なパラメータを使う機会が増え、結果的に圧縮率が上がるというわけである。 |
| --またここが少々ややこしかったとしても頻度は低いので展開速度に影響しにくい。だから遠慮なく(?)短く表現することを心がけた。 | | --またここが少々ややこしかったとしても頻度は低いので展開速度に影響しにくい。だから遠慮なく(?)短く表現することを心がけた。 |
- | --ここに示す方法では [ 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に匹敵する。 |
| *** モードヘッダ | | *** モードヘッダ |
- | -最初はモードヘッダである。上記の例だと最初の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 |
| --ここまでのまとめ: | | --ここまでのまとめ: |
| ---最後のビット(一番左のビット)がモードに対応している | | ---最後のビット(一番左のビット)がモードに対応している |
| ---残りの部分(最初の部分)については、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をつけた形式になっている |
| | | |
| *** 本体 | | *** 本体 |
| -デコード方法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をいくつか並べたいときがあるからである |
| -ターミネーション(終端処理) | | -ターミネーション(終端処理) |
| ---この終端方法はモード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だった時点でもう打ち切る |
| | | |
| -特定の条件でのみフッタが存在する | | -特定の条件でのみフッタが存在する |
| --モード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ビット節約する |
| | | |
| *** デフォルトパラメータ | | *** デフォルトパラメータ |