algorithm - 压缩具有特定顺序的正整数向量 (int32)

Question

我正在尝试压缩长向量(它们的大小范围从 1 到 1 亿个元素)。向量具有正整数，其值范围从 0 到 1 或 1 亿(取决于向量大小)。因此，我使用 32 位整数来包含大数字，但这会消耗太多存储空间。
这些向量具有以下特征:

所有值都是正整数。它们的范围随着向量大小的增长而增长。

值在增加，但较小的数字确实经常干预(见下图)。

特定索引之前的值都不大于该索引(索引从零开始)。例如，索引 6 之前出现的值都不大于 6。但是，较小的值可能会在该索引之后重复。这适用于整个阵列。

我通常处理很长的数组。因此，当数组长度超过 100 万个元素时，即将出现的数字大多是与先前重复出现的数字混合的大数字。较短的数字通常比较大的数字更频繁地重新出现。当您通过数组时，新的更大的数字会添加到数组中。

以下是数组中的值示例:{initial padding..., 0, 1, 2, 3, 4, 5, 6, 4, 7, 4, 8, 9, 1, 10, ... later ..., 1110, 11, 1597, 1545, 1392, 326, 1371, 1788, 541,...}
这是向量的一部分的图:

我想要什么？ :
因为我使用的是 32 位整数，这浪费了大量内存，因为可以用小于 32 位表示的较小数字也会重复。我想最大限度地压缩这个向量以节省内存(理想情况下，减少 3 倍，因为只有减少这个数量或更多才能满足我们的需求!)。实现这一目标的最佳压缩算法是什么？或者是否可以利用上述数组的特征将该数组中的数字可逆地转换为 8 位整数？
我尝试过或考虑过的事情 :

Delta 编码:这在这里不起作用，因为矢量并不总是增加。

霍夫曼编码:这里似乎没有帮助，因为数组中唯一数字的范围非常大，因此，编码表将是一个很大的开销。

使用变量 Int 编码。即对较小的数字使用 8 位整数，对较大的数字使用 16 位......等等。这将向量大小减小到 size*0.7(不令人满意，因为它没有利用上述特定特性)

我不太确定以下链接中描述的这种方法是否适用于我的数据:http://ygdes.com/ddj-3r/ddj-3r_compact.html
我不太了解该方法，但它鼓励我尝试类似的事情，因为我认为数据中有一些顺序可以发挥其优势。
例如，我尝试将任何大于 255 的数字(n)重新分配给 n-255，以便我可以将整数保留在 8 位领域中，因为我知道在该索引之前没有任何数字大于 255。但是，我无法区分重新分配的数字和重复的数字......所以这个想法不起作用，除非做一些更多的技巧来逆转重新分配......

以下是感兴趣的人的数据的前 24000 个元素的链接:
data
任何意见或建议深表感谢。非常感谢。
编辑 1:
这是增量编码后的数据图。如您所见，它不会减少范围!

编辑 2:
我希望我能在数据中找到一种模式，允许我可逆地将 32 位向量更改为单个 8 位向量，但这似乎不太可能。
我尝试将 32 位向量分解为 4 x 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

    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));

Answer 1

通过使用属性 3，很容易在示例数据上获得比两倍压缩更好的效果，其中我采用属性 3 表示每个值都必须小于其索引，索引从 1 开始。只需使用天花板(log2 (i)) 位来存储索引 i 处的数字(其中 i 从 1 开始)。对于具有 24,977 个值的第一个示例，使用 32 位整数将其压缩为向量大小的 43%。
所需的位数仅取决于向量的长度 n。位数为:
1 - 2ceiling(log2(n)) + n 天花板(log2(n))
正如 Falk Hüffner 所指出的，一种更简单的方法是为所有的天花板值(log2(n))使用固定数量的比特。可变位数将始终小于该数值，但不会比大 n 的位数少多少。
如果在开始时经常出现一串零，那么用计数压缩它们。余数中只有少数两个或三个数字的运行，因此除了最初的零运行之外，运行长度编码将无济于事。
使用算术编码方法可以减少另外 2% 左右(对于大型集合)，将索引 k 处的每个值(从零开始的索引)视为非常大整数的基数 k+1 位。这将需要天花板(log2(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;
}