0

我有这个排序的整数序列。

它们之间的差异是随机的。但是，如果您计算每个变量的差异，您会发现它看起来有点与随机数/函数相关的对数函数（差异以对数方式增加）。

我知道这不是一个庞大的数字，但我有成千上万个这样的系列（由相同的算法生成）。

我正在尝试尽可能多地压缩这些数据。我主要使用增量压缩，只能将数据压缩到其原始大小的 30%。

4

2 回答 2

1

（由相同的算法生成）

那么该算法本身可能会提供最佳压缩。它是什么？

除此之外，很容易将数据减少到大约 10K 字节。用可变长度整数编码差异。这样的整数表示为高位等于 1 的字节序列（任何数量的字节，包括无），后跟一个高位等于 0 的字节。然后连接每个字节的低七位得到整数。最低有效位首先出现。

这具有将小于 128 的所有值编码在单个字节中的优点。超过 96% 的差异小于 128。然后，通用压缩器将有效地对这些字节进行 Huffman 编码。

将其应用于您的差异，然后使用 压缩gzip -9，我得到 10626 字节。强制 gzip 算法仅使用 Huffman 压缩，我得到 10018 字节。如果我在第一个高位等于一个之前剪切文件，仅使用 Huffman 分别压缩这两个部分，然后将它们组合起来，我得到 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 字节）。gzipping 会为您提供 21 KB 的文件。这已经超过了 30% 的界限，但我们可以做得更好！

如果您将每个连续的差异存储为 32 位整数，则 gzip 压缩到 15 KB。

如果你想避免 gzip，我们可以拿出一些花哨的技巧。对每个差异使用简单的Elias 伽马编码会生成一个 14 KB 的文件。但是，这需要一个烦人的比特流读取器/写入器，这可能是一个关闭。

使用适当调整的 exp-Golomb 代码，您可能会做得更好；我没试过。

于 2013-01-13T06:38:18.353 回答