ideas/tek5

tek5に関するアイデア

ある単語（＝バイト列）を単語登録し、それを1バイトであるかのようにする。これにより、頻出単語はLZ形式で参照する必要がなくなり、圧縮率が改善する。
1バイトのものを単語登録することもできて、デフォルトでは00=00、01=01、・・・のようになっている。これをいじれば、00=41、01=42、・・・のようなこともできるだろう。これによりlcの予測力を大幅に改善することも可能であろうと思われる（再定義のためのコストとのトレードオフであるが）。
またこれだと1バイト=8bitということではコードが不足するかもしれないので、1～10bitまでのコード長を選べるようにする。

圧縮対象がある程度のデータ構造をもっている場合に非常に有効。
たとえば、1万バイトのデータに500バイト周期があり、その中でも最初の100バイトは数字だけで構成され、のこりの400バイトはアルファベットだけで構成されているとする。そんなとき、
```
[ 00 00 ... 00 （合計100個）] [ 01 01 ... 01 （合計400個）] [ 00 00 ... 00 （合計100個）] [ 01 01 ... 01 （合計400個）] ...
```
という1万バイトのフォーマットコードを生成し、まずこれをtek5圧縮する。これは非常に圧縮しやすい内容であり、おそらく10バイト程度にしかならない（ヘッダを除く）。
次に00に分類された2000バイトの、数字ばかりのデータが圧縮される。最後に8000バイトの、アルファベットのデータが圧縮される。・・・このように似たようなものが集中して集まることにより、文字出現予測のヒット率はよくなるし、スライド辞書のdis予測、len予測のヒット率も改善する。

応用として次のようなものがある。たとえば、

0001 0002 0003 0004 0005 0006 0007 0008 0009 0010 0011 0012 0013 0014 ...

というテキストデータがあったとしよう（9999まであるとする）。これを
```
abcd abcd abcd abcd ...
```
とフォーマット区分したとする（スペース部分はそのままスペースとしてフォーマットに組み込むか、もしくは、eに分類してあとでスペースだけの9999バイトを作るか、そのどちらかにする）。ここで、a=00、b=01、c=02、d=03、e=04というフォーマットナンバーである。
こうすると、dは次のようになる（9999バイト）。
```
123456789012345678901234567890 ...
```
これがLZ圧縮によって途方もなく小さくなることは自明である。

次にcを見てみるとこうなる（9999バイト）。

000000000111111111122222222223333333333 ... 9999999999000000000011111111112222222222 ...

これも100バイト周期になって、やはりかなり小さくなる。aやbについても同様である。
こういうデータは差分モードでのサポートももちろんできるが、このフォーマットフィールドでもできるというのはよい傾向である。
ここではフォーマットフィールドの1バイトはデコード後の1バイトになっていたが、そうではない形式も記述できる。
たとえば「行番号(4桁) : うんたらかんたら CRLF」という繰り返しのテキストがあったとする。これを、"abcd : e\r\n"というフォーマットの繰り返しにまず当てはめることにする。ここで、a～dは、1バイト＝1バイトの形式だが、eは可変長型である。
可変長型ではその長さ情報をフォーマットフィールドには含めない。なぜならフォーマットフィールドの圧縮率が極めて悪くなるからである。
長さ情報はeブロックのヘッダに、3,5,10,2,10,...のようにおいておくか、もしくはeのコードの中にターミネータ文字コードを定義してそれを使う。

コメント	お名前	NameLink