我正在尝试压缩长向量(它们的大小范围从 1 到 1 亿个元素)。向量具有正整数，其值范围从 0 到 1 或 1 亿(取决于向量大小)。因此，我使用 32 位整数来包含大数字，但这会消耗太多存储空间。
这些向量具有以下特征:
以下是数组中的值示例:{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 位整数？
我尝试过或考虑过的事情 :
我不太了解该方法，但它鼓励我尝试类似的事情，因为我认为数据中有一些顺序可以发挥其优势。
例如，我尝试将任何大于 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));
最佳答案
通过使用属性 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;
}
关于algorithm - 压缩具有特定顺序的正整数向量 (int32)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/67943077/