压缩具有特定顺序的正整数向量(int32)
我正在尝试压缩长向量（它们的大小范围从 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 个元素的链接：
数据
任何意见或建议深表感谢。非常感谢。
编辑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<int32_t>
const char* path = "path_tocompression_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));