0

このソートされた整数シーケンスの数字があります。

それらの違いはランダムです。ただし、それぞれの差を計算すると、何らかの形で乱数/関数に関連付けられた対数関数 (差は対数的に増加) で少し見えることがわかります。

これは膨大な数ではないことはわかっていますが、このようなシリーズが何千もあります (同じアルゴリズムによって生成されます)。

このデータをできる限り圧縮しようとしています。私は主にデルタ圧縮で遊んでいましたが、データを元のサイズの 30% までしか圧縮できませんでした。

4

2 に答える 2

1

（同じアルゴリズムによって生成されます）

次に、そのアルゴリズム自体が最良の圧縮を提供する可能性があります。それは何ですか？

それを除けば、データを約10Kバイトまで下げるのは簡単です。差分を可変長整数でエンコードします。このような整数は、上位ビットが1に等しいバイトのシーケンス（noneを含む任意の数）と、それに続く上位ビットがゼロに等しい1バイトとして表されます。次に、各バイトの下位7ビットを連結して整数を取得します。最下位ビットが最初に来ました。

これには、128未満のすべての値を1バイトにコーディングできるという利点があります。差異の96％以上は128未満です。汎用コンプレッサーは、これらのバイトを効率的にハフマン符号化します。

それをあなたの違いに適用し、それから圧縮するとgzip -9、私は10626バイトを取得します。gzipアルゴリズムにハフマン圧縮のみを使用するように強制すると、10018バイトになります。1に等しい最初の上位ビットが発生する直前にファイルを切り取り、ハフマンのみを使用して2つの部分を別々に圧縮し、それらを組み合わせると、9701バイトになります。

アップデート：

可変長整数を生成およびデコードするためのコードは次のとおりです。

/* Write n as a variable-length integer to out. */
void var(unsigned long n, FILE *out)
{
    int ch;

    do {
        ch = (int)(n & 0x7f);
        n >>= 7;
        if (n)
            ch += 0x80;
        putc(ch, out);
    } while (n);
}

#define ULBITS 64   /* set to the number of bits in an unsigned long */

/* Read a variable-length integer from in, putting it in *n.  Return 0 on
   success, -1 on immediate end-of-file, -2 if end-of-file in the middle of an
   integer, or 1 on overflow of the unsigned long type. */
int unvar(unsigned long *n, FILE *in)
{
    int ch, b;
    unsigned long d;

    *n = 0;
    b = 0;
    do {
        ch = getc(in);
        if (ch == EOF)
            return b ? -2 : -1;
        if (b >= ULBITS)
            return 1;
        d = (unsigned long)(ch & 0x7f) << b;
        if ((d >> b) != (ch & 0x7f))
            return 1;
        *n += d;
        b += 7;
    } while (ch & 0x80);
    return 0;
}
于 2013-01-13T06:46:00.767 に答える
0

現在保存されているファイルは 101 KB です。

ファイルを 32 ビット整数のシーケンスとして (バイナリで -- はい、すべてこれを行うのに十分小さい) 保存すると、57 KB (14,345 整数 x 4 バイト) になります。21 KB のファイルを提供する gzipping。これはすでに 30% の境界を超えていますが、さらに改善することができます。

代わりに、連続する各差分を 32 ビット整数として保存すると、gzip で 15 KB になります。

gzip を回避したい場合は、いくつかの巧妙なトリックを引き出すことができます。各差分に対して単純なElias ガンマ コーディングを使用すると、14 KB のファイルが生成されます。ただし、これには煩わしいビットストリーム リーダー/ライターが必要であり、これはターンオフになる可能性があります。

適切に調整されたexp-Golomb コードを使用すると、さらにうまくいく可能性があります。私はそれを試していません。

于 2013-01-13T06:38:18.353 に答える