压缩具有特定顺序的正整数向量（int32）

Question

我正在尝试压缩长向量（其大小从1到1亿个元素不等）。向量中的正整数值范围为0到1亿（取决于向量大小），因此我使用32位整数来包含大数，但这会消耗过多的存储空间。向量具有以下特征：

1. 所有值都是正整数。随着向量大小的增加，它们的范围也会增加。
2. 值递增，但较小的数字经常出现（请参见下图）。
3. 特定索引之前的所有值都不大于该索引（索引从零开始）。例如，在索引6之前发生的任何值都不大于6。但是，在该索引之后，较小的值可能会重复。对于整个数组，这仍然成立。
4. 通常处理非常长的数组。因此，随着数组长度超过100万个元素，即将出现的数字大多是与先前重复出现的数字混合的大数字。较短的数字通常比较大的数字更容易重复出现。通过遍历数组，可以将新的较大数字添加到数组中。

以下是数组中值的示例：{初始填充..., 0, 1, 2, 3, 4, 5, 6, 4, 7, 4, 8, 9, 1, 10, ...稍后..., 1110, 11, 1597, 1545, 1392, 326, 1371, 1788, 541,...}

以下是向量的一部分的绘图： 我想要什么？ 因为我使用32位整数，这浪费了很多内存，因为可以用少于32位表示的较小数字也会重复出现。我希望最大限度地压缩此向量以节省内存（理想情况下，压缩因子应达到3，因为只有降低这个量或更多才能满足我们的需求！）。哪种最佳压缩算法可实现此目的？或者是否有方法利用上述数组的特征将该数组中的数字可逆转换为8位整数？

我尝试过或考虑过的事情：

1. Delta编码：由于向量不总是单调递增，因此此方法在此处无法使用。
2. Huffman编码：由于数组中唯一数字的范围相当大，因此似乎在这里不起作用，因为编码表将是一个很大的开销。
3. 使用可变Int编码。即对较小的数字使用8位整数，对较大的数字使用16位...等。这已经将向量大小减小到size*0.7（不令人满意，因为它没有利用上述特定特性）。
4. 我不确定下面链接中描述的方法是否适用于我的数据：http://ygdes.com/ddj-3r/ddj-3r_compact.html 我不太理解这种方法，但它鼓励我尝试类似的事情，因为我认为数据中有一些可以利用的顺序。 例如，我尝试重新分配任何大于255的数字(n)到n-255，以便我可以保持整数在8位领域内，因为我知道在该索引之前没有数字大于255。然而，我无法区分重新分配的数字和重复的数字...所以除非进行一些更多的技巧来反转重新分配，否则这个想法行不通...

这是前24000个元素的数据链接，供感兴趣的人使用： data

非常感谢任何建议或建议。提前致谢。

编辑1：

这是Delta编码后数据的图。如您所见，它并没有减少范围！

编辑2：

我希望能在数据中找到一种模式，使我可以将32位向量可逆地转换为单个8位向量，但这似乎非常不可能。 我尝试将32位向量分解为4个8位向量，希望分解向量更容易压缩。 下面是4个向量的图。现在它们的范围是0-255。 我所做的是将向量中的每个元素递归地除以255，并将余数存储到另一个向量中。要重构原始数组，我需要做的就是：(((vec4*255)+vec3)*255+vec2)*255+vec1...

如您所见，当前显示的数据长度中最后一个向量全为零。事实上，这应该一直保持到第2^24个元素。如果我的总向量长度小于1600万个元素，则这将减少25％，但由于我处理的向量要长得多，因此影响较小。 更重要的是，第三个向量似乎也具有可压缩特征，因为其值在每65,535步之后增加1。 现在看来，我可以从霍夫曼编码或可变位编码中受益。如果有任何建议可以让我最大程度地压缩这些数据，那将不胜感激。 这里附上一个更大的数据样本，如果有人感兴趣：

https://drive.google.com/file/d/10wO3-1j3NkQbaKTcr0nl55bOH9P-G1Uu/view?usp=sharing

编辑3：

非常感谢所有提供答案的人。我从中学到了很多。如果您有兴趣玩弄更大的数据集，以下链接有1100万个类似数据集的元素（压缩后33MB）。

https://drive.google.com/file/d/1Aohfu6II6OdN-CqnDll7DeHPgEDLMPjP/view

一旦解压数据，您可以使用以下C++代码片段将数据读入vector<int32_t>中。

    const char* path = "path_to\compression_int32.txt";
    std::vector<int32_t> newVector{};
    std::ifstream ifs(path, std::ios::in | std::ifstream::binary);
    std::istream_iterator<int32_t> iter{ ifs };
    std::istream_iterator<int32_t> end{};
    std::copy(iter, end, std::back_inserter(newVector));

- Hunar

---

真是太遗憾了。我知道的其他技巧都更加复杂，需要显式建模概率分布。除了位切片之外，但我在你的数据上尝试过，效果不是很好（它确实利用了有限范围，但几乎任何其他方法也都是如此，并且它对顺序也有一定的利用）。 - harold

你的数据样本以0, 1, 2, 3, 4, 5, 6, 4, 7, 4, 8, 9, 1, 10, 11, 12, 13, 14, 15, 16, 16, 17, 18, 19, 19, 6, 6, 6, 20, 160开头。在索引30处出现的160与特征三不太匹配。 - user58697

将您的数据解释为字节，然后应用Huffman或LZW算法，或者使用可变位编码流（例如GIF中的方式），就像Mark Adler在他的回答中建议的那样。 - Spektre

使用变长方法，我的答案可以将300,000个32位值压缩到原始大小的0.539。我没有看到你的四个字节的图表有任何希望能做得比这更好。0.539几乎消除了vec3和vec4。 - Mark Adler

@MarkAdler 您是正确的，这不是一个三角形，并且随着大小的增加，情况变得越来越糟糕。100,000,000个32位被编码为原始大小的77.056％。2 ^ 29 x 32位被编码为84.375％的大小。 - Spektre

Answer 1

使用第三个属性可以轻松地将示例数据的压缩率提高到两倍以上，其中我将第三个属性解释为每个值必须小于其索引，索引从1开始。只需使用ceiling(log₂(i))位来存储索引为 i （其中 i 从1开始）的数字即可。对于您的第一个示例，使用32位整数将其压缩为向量大小的43％。

所需位数仅取决于向量长度。所需位数为：

1-2^{ceiling(log₂(n))}+ n ceiling(log₂(n))

如Falk Hüffner所述，更简单的方法是对所有值使用固定数量的ceiling(log₂(n))位数。变量位数始终少于固定位数，但对于大的而言差别不大。

如果通常在开头有一串零，则使用计数来压缩它们。剩余部分中只有少数运行的两个或三个数字，因此除初始的零运行外，运行长度编码没有帮助。

对于大型集合，还可以使用算术编码方法将另外2％左右的数据压缩，将索引k 处的每个值（索引从零开始）视为非常大整数的基础k + 1 数字。这需要ceiling(log₂(n!))位。

下面是算术编码、变量样本编码和固定比特率样本编码的压缩比的绘图，所有比率均与每个样本使用32比特表示的比率相对应（序列长度为对数尺度）：

算术方法需要在压缩数据的长度上进行整数乘法和除法，这对于大向量来说非常慢。下面的代码将整数大小限制为64位，以某种代价换取了较快的压缩比。该代码将给出比上述图表中算术法多0.2％至0.7％的压缩比，远低于变量位数。数据向量必须具有每个值都是非负数且每个值都小于其位置（位置从1开始）的属性。压缩效果仅取决于该属性，加上如果有一串初始零的话将略微减少。提供的示例中似乎存在更多冗余，此压缩方法没有利用该冗余。

#include <vector>
#include <cmath>

// Append val, as a variable-length integer, to comp. val must be non-negative.
template <typename T>
void write_varint(T val, std::vector<uint8_t>& comp) {
    while (val > 0x7f) {
        comp.push_back(val & 0x7f);
        val >>= 7;
    }
    comp.push_back(val | 0x80);
}

// Return the variable-length integer at offset off in comp, updating off to
// point after the integer.
template <typename T>
T read_varint(std::vector<uint8_t> const& comp, size_t& off) {
    T val = 0, next;
    int shift = 0;
    for (;;) {
        next = comp.at(off++);
        if (next > 0x7f)
            break;
        val |= next << shift;
        shift += 7;
    }
    val |= (next & 0x7f) << shift;
    return val;
}

// Given the starting index i >= 1, find the optimal number of values to code
// into 64 bits or less, or up through index n-1, whichever comes first.
// Optimal is defined as the least amount of entropy lost by representing the
// group in an integral number of bits, divided by the number of bits. Return
// the optimal number of values in num, and the number of bits needed to hold
// an integer representing that group in len.
static void group_ar64(size_t i, size_t n, size_t& num, int& len) {
    // Analyze all of the permitted groups, starting at index i.
    double min = 1.;
    uint64_t k = 1;                 // integer range is 0..k-1
    auto j = i + 1;
    do {
        k *= j;
        auto e = log2(k);           // entropy of k possible integers
        int b = ceil(e);            // number of bits to hold 0..k-1
        auto loss = (b - e) / b;    // unused entropy per bit
        if (loss < min) {
            num = j - i;            // best number of values so far
            len = b;                // bit length for that number
            if (loss == 0.)
                break;              // not going to get any better
            min = loss;
        }
    } while (j < n && k <= (uint64_t)-1 / ++j);
}

// Compress the data arithmetically coded as an incrementing base integer, but
// with a 64-bit limit on each integer. This puts values into groups that each
// fit in 64 bits, with the least amount of wasted entropy. Also compress the
// initial run of zeros into a count.
template <typename T>
std::vector<uint8_t> compress_ar64(std::vector<T> const& data) {
    // Resulting compressed data vector.
    std::vector<uint8_t> comp;

    // Start with number of values to make the stream self-terminating.
    write_varint(data.size(), comp);
    if (data.size() == 0)
        return comp;

    // Run-length code the initial run of zeros. Write the number of contiguous
    // zeros after the first one.
    size_t i = 1;
    while (i < data.size() && data[i] == 0)
        i++;
    write_varint(i - 1, comp);

    // Compress the data into variable-base integers starting at index i, where
    // each integer fits into 64 bits.
    unsigned buf = 0;       // output bit buffer
    int bits = 0;           // number of bits in buf (0..7)
    while (i < data.size()) {
        // Find the optimal number of values to code, starting at index i.
        size_t num;  int len;
        group_ar64(i, data.size(), num, len);

        // Code num values.
        uint64_t code = 0;
        size_t k = 1;
        do {
            code += k * data[i++];
            k *= i;
        } while (--num);

        // Write code using len bits.
        if (bits) {
            comp.push_back(buf | (code << bits));
            code >>= 8 - bits;
            len -= 8 - bits;
        }
        while (len > 7) {
            comp.push_back(code);
            code >>= 8;
            len -= 8;
        }
        buf = code;
        bits = len;
    }
    if (bits)
        comp.push_back(buf);
    return comp;
}

// Decompress the result of compress_ar64(), returning the original values.
// Start decompression at offset off in comp. When done, off is updated to
// point just after the compressed data.
template <typename T>
std::vector<T> expand_ar64(std::vector<uint8_t> const& comp, size_t& off) {
    // Will contain the uncompressed data to return.
    std::vector<T> data;

    // Get the number of values.
    auto vals = read_varint<size_t>(comp, off);
    if (vals == 0)
        return data;

    // Get the number of zeros after the first one, and write all of them.
    auto run = read_varint<size_t>(comp, off) + 1;
    auto i = run;
    do {
        data.push_back(0);
    } while (--run);

    // Extract the values from the compressed data starting at index i.
    unsigned buf = 0;       // input bit buffer
    int bits = 0;           // number of bits in buf (0..7)
    while (i < vals) {
        // Find the optimal number of values to code, starting at index i. This
        // simply repeats the same calculation that was done when compressing.
        size_t num;  int len;
        group_ar64(i, vals, num, len);

        // Read len bits into code.
        uint64_t code = buf;
        while (bits + 8 < len) {
            code |= (uint64_t)comp.at(off++) << bits;
            bits += 8;
        }
        len -= bits;                    // bits to pull from last byte (1..8)
        uint64_t last = comp.at(off++); // last byte
        code |= (last & ((1 << len) - 1)) << bits;
        buf = last >> len;              // save remaining bits in buffer
        bits = 8 - len;

        // Extract num values from code.
        do {
            i++;
            data.push_back(code % i);
            code /= i;
        } while (--num);
    }

    // Return the uncompressed data.
    return data;
}

- Mark Adler

---

我不认为利用属性3会节省多少空间；例如，在数据的后半部分，与使用固定位数相比，每个值最多只能节省一个比特位。如果将这个想法与仅使用固定的32位（sum(ceil(log2(i)) for i in range(1, 100_000_000)) / sum(32 for i in range(1, 100_000_000))）进行比较，确实只有20%更小，而其中大部分来自于这些数字都可以适应少于32位；从观察到最大值为33,000,000并使用固定的25位可以缩小数据。 - Falk Hüffner

@FalkHüffner 因为提问者表示他们正在使用32位整数来存储每个值，并且提问者提供的示例数据有24,977个值。将日志的天花板相加，得到的总位数为341,888位，或10,684个32位字。与24,977个32位字相比，是更小的。是的，提问者本可以将该数据存储在16位字中，这种情况下，此方法只能将其压缩到原始大小的86％。 - Mark Adler

@FalkHüffner 不，固定位数的数据不可能缩小更多。使用可变长度方法，3300万个值需要791,445,569位，而每个值25位时需要825,000,000位。大约多出4%。 - Mark Adler

Mark Adler，感谢您的解释。正如@FalkHüffner所指出的，并且正如您在图中展示的那样，如果我的向量长度较小，则这将产生良好的效果。然而，由于我处理的向量长度高达1亿个元素，因此对于我的数据来说，这似乎不太有效。我现在正在尝试将32位向量分解为4x8位向量，以查看较小值向量是否更易压缩。有关更多详细信息，请参见我的编辑。 - Hunar

谢谢新的绘图！这看起来比以前那个更有前途，因为很难从它推断出压缩比。通常我处理的是大小可变的向量，从这张图中可以看出，对于少于一百万个元素的向量，压缩比看起来不错。此外，我以前没有实现过可变位数，如果你能指导我一个可行的C++实现或一个免费库，那将非常有帮助，让我可以使用该方法处理较小的向量。非常感激您的帮助。 - Hunar

Answer 2

如我在评论中所建议的那样，您可以将数据表示为8位。有简单有效的方法来实现它，不需要模算术。

您可以使用union或指针来实现这一点，例如在C ++中，如果您有：

unsigned int data32[]={0,0,0,...};
unsigned char *data08=data32;

或者你可以将其复制到4字节数组中，但这会更慢。

如果你必须出于任何原因使用模算术，那么你可能想这样做：

 x     &255
(x>> 8)&255
(x>>16)&255
(x>>24)&255

现在我已经尝试过了LZW，对你的新数据进行了压缩比率测试，没有任何数据重新排序（单个LZW）的结果为81-82%（取决于字典大小，建议使用10位LZW字典），这并不如预期。因此，我将数据重新排序为4个数组（就像你所做的一样），使得第一个数组包含最低的8位，最后一个数组包含最高的8位。使用12位字典的结果如下：

ratio08: 144%
ratio08: 132%
ratio08:  26%
ratio08:   0%
total:    75%

使用10位字典的结果如下：

ratio08: 123%
ratio08: 117%
ratio08:  28%
ratio08:   0%
total:    67%

展示LZW在最低字节方面的不足（随着大小的增加，对于更高的字节也会变得更糟），因此仅将其用于更高的BYTEs，这将提高压缩比。

然而，我预计哈夫曼应该能够带来更好的结果，因此我计算了您数据的熵：

H32 = 5.371071 , H/8 = 0.671384
H08 = 7.983666 , H/8 = 0.997958
H08 = 7.602564 , H/8 = 0.950321
H08 = 1.902525 , H/8 = 0.237816
H08 = 0.000000 , H/8 = 0.000000
total: 54%

意味着天真的单一哈夫曼编码将具有67％的压缩比，而分开的4个数组将导致54％，这是更好的选择，因此在您的情况下，我会选择哈夫曼编码。 在此实施后的结果如下：

[Huffman]
ratio08 =  99.992%
ratio08 =  95.400%
ratio08 =  24.706%
ratio08 =   0.000%
total08 =  55.025%
ratio32 =  67.592%

这与Shannon熵的估计相当接近（未考虑解码表）...

然而，对于非常大的数据集，我预计朴素的哈夫曼编码将开始比分离的4倍哈夫曼编码略微优越...

还要注意，结果被截断，因此那些0％不是零，而是小于1％的数值...

[编辑1] 300,000,000个条目的估计

因此，为了模拟您的300M个32位数字的条件，我使用具有类似“空白空间”属性的16位数字子部分。

log2(300 000 000) = ~28
28/32 * 16 = 14

因此，我只使用了2^14个16位数字，这些数字应该具有与您的300M 32位数字类似的属性。8位Huffman编码导致：

ratio08 =  97.980%
ratio08 =  59.534%
total08 =  78.757%

我估计编码/解码大小之间的比例为80％，大小缩小约1.25倍。 （希望我的假设没有出错）。

- Spektre

Answer 3

解决每个压缩问题都应该从分析开始。

我查看了包含前24976个值的原始数据文件。最小值为0，最大值为24950。数据的“斜率”约为1。然而，如果最大值仅为33M @ 100M值，则随着时间的推移，它应该会下降。假设斜率=1有点悲观。

至于分布情况，

tr '[,]' '[\n]' <compression.txt | sort -n | uniq -c | sort -nr | head -n256

生产

164  0
131  8
111  1648
108  1342
104  725
103  11
 91  1475
 90  1446
 82  21
 82  1355
 78  69
 76  2
 75  12
 72  328
 71  24
 70  614
 70  416
 70  1608
 70  1266
 69  22
 67  356
 67  3
 66  1444
 65  19
 65  1498
 65  10
 64  2056
 64  16
 64  1322
 64  1182
 63  249
 63  1335
 61  43
 60  17
 60  1469
 59  33
 59  3116
 58  20
 58  1201
 57  303
 55  5
 55  4
 55  2559
 55  1324
 54  1110
 53  1984
 53  1357
 52  807
 52  56
 52  4321
 52  2892
 52  1
 50  39
 50  2475
 49  1580
 48  664
 48  266
 47  317
 47  1255
 46  981
 46  37
 46  3531
 46  23
 43  1923
 43  1248
 41  396
 41  2349
 40  7
 39  6
 39  54
 39  4699
 39  32
 38  815
 38  2006
 38  194
 38  1298
 38  1284
 37  44
 37  1550
 37  1369
 37  1273
 36  1343
 35  61
 35  3991
 35  3606
 35  1818
 35  1701
 34  836
 34  27
 34  264
 34  241
 34  1306
 33  821
 33  28
 33  248
 33  18
 33  15
 33  1017
 32  9
 32  68
 32  53
 32  240
 32  1516
 32  1474
 32  1390
 32  1312
 32  1269
 31  667
 31  326
 31  263
 31  25
 31  160
 31  1253
 30  3365
 30  2082
 30  18550
 30  1185
 30  1049
 30  1018
 29  73
 29  487
 29  48
 29  4283
 29  34
 29  243
 29  1605
 29  1515
 29  1470
 29  1297
 29  1183
 28  980
 28  60
 28  302
 28  242
 28  1959
 28  1779
 28  161
 27  811
 27  51
 27  36
 27  201
 27  1270
 27  1267
 26  979
 26  50
 26  40
 26  3111
 26  26
 26  2425
 26  1807
 25  825
 25  823
 25  812
 25  77
 25  46
 25  217
 25  1842
 25  1831
 25  1534
 25  1464
 25  1321
 24  730
 24  66
 24  59
 24  427
 24  355
 24  1465
 24  1299
 24  1164
 24  1111
 23  941
 23  892
 23  7896
 23  663
 23  607
 23  556
 23  47
 23  2887
 23  251
 23  1776
 23  1583
 23  1488
 23  1349
 23  1244
 22  82
 22  818
 22  661
 22  42
 22  411
 22  3337
 22  3190
 22  3028
 22  30
 22  2226
 22  1861
 22  1363
 22  1301
 22  1262
 22  1158
 21  74
 21  49
 21  41
 21  376
 21  354
 21  2156
 21  1688
 21  162
 21  1453
 21  1067
 21  1053
 20  711
 20  413
 20  412
 20  38
 20  337
 20  2020
 20  1897
 20  1814
 20  17342
 20  173
 20  1256
 20  1160
 19  9169
 19  83
 19  679
 19  4120
 19  399
 19  2306
 19  2042
 19  1885
 19  163
 19  1623
 19  1380
 18  805
 18  79
 18  70
 18  6320
 18  616
 18  455
 18  4381
 18  4165
 18  3761
 18  35
 18  2560
 18  2004
 18  1900
 18  1670
 18  1546
 18  1291
 18  1264
 18  1181
 17  824
 17  8129
 17  63
 17  52
 17  5138

作为最常见的256个值。

似乎有些值本质上更常见。经过检查，这些常见的值也似乎分布在数据的各个角落。

我提出以下建议：

将数据分成块。对于每个块，发送斜率的实际值，以便在编码每个符号时知道其最大值。

对一个块中的常见值进行统计编码（如哈夫曼编码等）。在这种情况下，使用256个符号表，截断值为约17次。

对于不太常见的值，我们保留符号表的一小部分来发送值中的位数。

当我们遇到罕见的值时，它的位将不使用统计模型进行编码。可以省略最高位，因为我们知道它始终为1（除非值为“0”）。

通常要编码的值的范围不是2的幂。例如，如果我们有10个选择，这需要4位进行编码，但是有6个未使用的位模式 - 有时我们只需要3位。我们用3位直接编码前6个选择。如果是7或8，我们发送额外的一位来表示我们是否指的是9或10。

此外，我们可以从可能值的列表中排除任何直接编码的值。否则，我们有两种编码相同值的方式，这是多余的。

- The Hard Way

Answer 4

您正在处理的数据是“几乎”排序的，因此您可以使用增量编码来极大地提高效率。

一个简单的方法如下：

查找数据运行，用R_i = (v, l, N)表示，其中l是运行的长度，N是需要在排序的运行上执行增量编码所需的位深度，v是（排序）运行的第一个元素的值（增量编码所需）。然后，运行本身只需要为运行中每个条目存储2个信息：运行中每个排序元素的索引和增量。请注意，要存储每个排序元素的索引，每个索引仅需要log_2(l)位，其中l是运行的长度。

编码的工作是尝试找到完全编码运行所需的最少位数，与其未压缩形式所使用的字节数进行比较。实际上，这可以通过找到以固定字节每个元素编码的最长运行来实现。

要解码，只需按顺序逐个解码运行，首先解码增量编码/压缩，然后撤消排序。

这里是一些C++代码，用于计算在你发布的数据样本上使用此方案可以获得的压缩比。实现采用贪心方法选择运行，如果使用更智能的方法可能会得到稍微更好的结果。

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <queue>

#include "data.h"

template <int _N, int _M> struct T {
  constexpr static int N = _N;
  constexpr static int M = _M;
  uint16_t idx : N;
  uint16_t delta : M;
};

template <int _N, int _M>
std::pair<int32_t, int32_t> best_packed_run_stats(size_t idx) {
  const int N = 1 << _N;
  const int M = 1 << _M;
  static std::vector<int32_t> buffer(N);
  if (idx + N >= data.size())
    return {-1, 0};
  std::copy(&data[idx], &data[idx + N], buffer.data());
  std::sort(buffer.begin(), buffer.end());
  int32_t run_len = 0;
  for (size_t i = 1; i < N; ++i, ++run_len) {
    auto delta = buffer[i] - buffer[i - 1];
    assert(delta >= 0);
    if (delta >= M) {
      break;
    }
  }
  int32_t savings = run_len * (sizeof(int32_t) - sizeof(T<_N, _M>)) -
                    1    // 1 byte to store bit-depth
                    - 2; // 2 bytes to store run length
  return {savings, run_len};
}

template <class... Args>
std::vector<std::pair<int32_t, int32_t>> all_runs_stats(size_t idx) {
  return {best_packed_run_stats<Args::N, Args::M>(idx)...};
}

int main() {

  size_t total_savings = 0;
  for (size_t i = 0; i < data.size(); ++i) {
    auto runs =
        all_runs_stats<T<2, 14>, T<4, 12>, T<8, 8>, T<12, 4>, T<14, 2>>(i);
    auto best_value = *std::max_element(runs.begin(), runs.end());
    total_savings += best_value.first;
    i += best_value.second;
  }
  size_t uncomp_size = data.size() * sizeof(int32_t);
  double comp_ratio =
      (uncomp_size - (double)total_savings) / (double)uncomp_size;
  printf("uncomp_size: %lu\n", uncomp_size);
  printf("compression: %lf\n", comp_ratio);
  printf("size: %lu\n", data.size());
}

注意，只尝试了16位表示中元素的某些固定配置。因此，我们应该期望我们能够实现的最佳压缩率为50％（即4字节-> 2字节）。实际上，存在开销。

在提供的数据样本上运行此代码时，报告了此压缩比率：

uncomp_size: 99908
compression: 0.505785
size: 24977

这个压缩算法的实际压缩率非常接近理论极限.5。

另外需要注意的是，这比另一个答案中报告的香农熵估计略高一些。

---

根据Mark Adler在下面的评论中提出的问题进行编辑。

重新对提供的较大数据集（compression2.txt）运行此压缩，并与Mark Adler在这里的方法进行比较，以下是结果：

uncomp_size: 2602628
compression: 0.507544
size: 650657
bit compression: 0.574639

其中 位压缩 是Mark Adler方法的压缩比。正如其他人所指出的，对于大数据，压缩每个条目的位不会很好地扩展，我们应该预计随着 n 的增加，比率会变得更糟。

与此同时，上述描述的 delta + 排序压缩保持接近其理论最佳值 0.5。

- ldog

---

我通过在数字索引位数中存储每个值并对零序列进行运行长度编码，获得了 0.426522 的结果。或者，将其作为单个大的可变基数整数存储，可以获得 0.411469 的结果。 - Mark Adler

你的积分位数计算方法有误且过于乐观，正确值应为0.574639。如果我加上零的初期连续零值的游程编码，则得到0.573940。算术编码得到0.558403。 - Mark Adler

根据要求，我现在提供了大约1100万个类似数据的元素（我的帖子末尾有链接-Edit3）。该数据与之前的模式相同，只是这次有一个初始填充为-1而不是0（初始填充与向量的大小相比太小，因此不重要，将被丢弃。所有其他值都是正数）。 - Hunar

看起来ldog的方案在1100万个值中，比每个值的可变积分位数（0.7048）表现更好，比算术方法的0.6882稍微好一点，达到了0.6846的比率。 - Mark Adler

我将1100万个值写成了四个字节流，每个四字节值一个字节流。（我本可以只用三个字节流，但结果差不多。）然后我用xz进行了压缩。结果的压缩比为0.644778。因此，仅使用属性#3可能会获得一些压缩以外的收益。 - Mark Adler