压缩具有特定顺序的正整数 (int32) 向量
Compressing a vector of positive integers (int32) that have a specific order
我正在尝试压缩长向量（它们的大小范围从 1 到 1 亿个元素）。向量具有正整数，值范围从 0 到 1 或 1 亿（取决于向量大小）。因此，我使用 32 位整数来包含大数，但这会占用太多存储空间。
这些向量具有以下特征：
- 所有的值都是正整数。它们的范围随着矢量大小的增长而增长。
- 值在增加，但较小的数字确实经常干预（见下图）。
- None 特定索引之前的值大于该索引（索引从零开始）。例如，索引 6 之前出现的值中有 none 大于 6。但是，较小的值可能会在该索引之后重复出现。这适用于整个数组。
- 我通常处理很长的数组。因此，当数组长度超过 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位整数？
我尝试过或考虑过的事情:
- Delta 编码：这在这里不起作用，因为矢量并不总是增加。
- 霍夫曼编码：这里似乎没有帮助，因为数组中唯一数字的范围非常大，因此，编码 table 将是一个很大的开销。
- 使用变量 Int 编码。即对较小的数字使用 8 位整数，对较大的数字使用 16 位整数......等等。这已将矢量大小减小到 size*0.7（不令人满意，因为它没有利用上述特定特征）
- 我不太确定下面link中描述的这种方法是否适用于我的数据：http://ygdes.com/ddj-3r/ddj-3r_compact.html
我不太了解该方法，但它鼓励我尝试类似的事情，因为我认为数据中存在一些可以利用的顺序。
例如，我尝试将任何大于 255 的数字 (n) 重新分配给 n-255，以便我可以将整数保留在 8 位域中，因为我知道在该索引之前没有数字大于 255。但是，我无法区分重新分配的数字和重复的数字......所以这个想法不起作用，除非采取更多技巧来扭转重新分配......
这里是 link 到第 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：
非常感谢所有给出的答案。我从他们身上学到了很多。对于那些有兴趣修改更大数据集的人，以下 link 具有类似数据集的 1100 万个元素（压缩 33MB）
https://drive.google.com/file/d/1Aohfu6II6OdN-CqnDll7DeHPgEDLMPjP/view
解压缩数据后，您可以使用以下 C++ 片段将数据读入向量
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 开始。只需使用 ceiling(log2(i)) 位来存储索引 处的数字i（其中 i 从 1 开始）。对于具有 24,977 个值的第一个示例，使用 32 位整数将其压缩为向量大小的 43%。
所需的位数仅取决于向量的长度，n。位数为：
1 - 2上限(log2(n)) + n 上限(log2(n))
正如 Falk Hüffner 所指出的，一种更简单的方法是为所有 ceiling(log2(n)).可变位数将始终小于该位数，但不会比大 n.
少很多
如果开头有一个 运行 个零是很常见的，那么用一个计数压缩它们。余数中只有少数两个或三个数字的 运行，因此 运行 长度编码将无济于事，除了最初的 运行 个零。
考虑到索引 k 处的每个值（从零开始的索引），可以使用算术编码方法削减另外 2% 左右（对于大集合）一个非常大的整数的基数 k+1。这将占用 ceiling(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;
}
正如我在评论中所建议的那样，您可以将数据表示为 8 位。有一些简单的方法可以有效地做到这一点，不需要模块化算法..
您可以为此使用联合或指针，例如在 C++ 中，如果您有：
unsigned int data32[]={0,0,0,...};
unsigned char *data08=data32;
或者您可以将其复制到 4 BYTE 数组，但那样会更慢。
如果您出于任何原因必须使用模运算，那么您可能希望这样做：
x &255
(x>> 8)&255
(x>>16)&255
(x>>24)&255
现在 I have tried LZW 在您的新数据上，没有任何数据重新排序（单个 LZW）的压缩比结果为 81-82%（取决于字典大小，我建议使用 10 位 LZW 字典）这不是正如预期的那样好。因此，我将数据重新排序为 4 个数组（就像您所做的那样），因此第一个数组的 8 位最低，最后一个最高。 12 位字典的结果，其中：
ratio08: 144%
ratio08: 132%
ratio08: 26%
ratio08: 0%
total: 75%
10 位字典的结果，其中：
ratio08: 123%
ratio08: 117%
ratio08: 28%
ratio08: 0%
total: 67%
表明 LZW 对最低字节不利（随着大小的增加，对更高字节的影响也会更差）因此仅将其用于更高的字节，这将进一步提高压缩率。
不过我希望霍夫曼会带来更好的结果，所以 对于您的数据：
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%
这与预期的香农熵估计非常匹配（不考虑解码 table）...
然而，对于非常大的数据集，我希望朴素的霍夫曼会开始变得比单独的 4x 霍夫曼稍微好一些...
另请注意，结果被截断，因此 0% 不是零，而是小于 1% ...
[Edit1] 300 000 000 个条目估计
所以为了模拟你的 300M 32 位数字的条件，我使用你的数据的 16 位数字子部分，具有类似的“空 space”属性。
log2(300 000 000) = ~28
28/32 * 16 = 14
所以我只使用 2^14 个 16 位数字，它们应该与您的 300M 32 位数字具有相似的属性 8 位霍夫曼编码导致：
ratio08 = 97.980%
ratio08 = 59.534%
total08 = 78.757%
所以我估计 encoded/decoded 大小减少 ~1.25 之间的比例为 80%。
（希望我的假设没有搞砸）。
解决每个压缩问题都应该从分析开始。
我查看了包含前 24976 个值的原始数据文件。最小值为 0，最大值为 24950。数据的“斜率”约为 1。但是，如果最大值如前所述仅为 33M@100M 值，则它应该随时间减少。 slope=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 位。前 6 个选择我们直接用 3 位编码。如果它是 7 或 8，我们会发送一个额外的位来指示我们是指 9 还是 10。
此外，我们可以从可能值列表中排除直接编码的任何值。否则我们有两种方法来编码相同的值，这是多余的。
您正在处理的数据“几乎”已排序，因此您可以将其用于 delta 编码以产生很好的效果。
简单的做法如下：
查找 运行s 数据，用 R_i = (v,l,N) 表示，其中 l 是 运行 的长度，N 是位深度需要对排序的 运行 进行增量编码，v 是（已排序的）运行 的第一个元素的值（增量编码需要）。 运行本身然后只需要为 运行 中的每个条目存储 2 条信息：运行 中每个排序元素的 idx 和增量。注意，要存储每个排序元素的 idx，每个 idx 只需要 log_2(l) 位，其中 l 是 运行.
的长度
与未压缩形式使用的字节数相比，编码的工作原理是尝试找到最少的位数来完全编码 运行。实际上，这可以通过找到最长的 运行 来实现，该 运行 编码为每个元素的固定字节数。
要解码，只需解码 运行-by-运行（按顺序）首先解码增量 coding/compression，然后取消排序。
下面是一些 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
其中 bit compression 是 Mark Adler 方法的压缩率。正如其他人所指出的，压缩每个条目的位对于大数据来说不会很好地扩展，我们应该期望 n.
的比率会变得更糟
同时，上述增量 + 排序压缩保持接近其理论最佳值 .5。
我正在尝试压缩长向量（它们的大小范围从 1 到 1 亿个元素）。向量具有正整数，值范围从 0 到 1 或 1 亿（取决于向量大小）。因此，我使用 32 位整数来包含大数，但这会占用太多存储空间。 这些向量具有以下特征：
- 所有的值都是正整数。它们的范围随着矢量大小的增长而增长。
- 值在增加，但较小的数字确实经常干预（见下图）。
- None 特定索引之前的值大于该索引（索引从零开始）。例如，索引 6 之前出现的值中有 none 大于 6。但是，较小的值可能会在该索引之后重复出现。这适用于整个数组。
- 我通常处理很长的数组。因此，当数组长度超过 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位整数？
我尝试过或考虑过的事情:
- Delta 编码：这在这里不起作用，因为矢量并不总是增加。
- 霍夫曼编码：这里似乎没有帮助，因为数组中唯一数字的范围非常大，因此，编码 table 将是一个很大的开销。
- 使用变量 Int 编码。即对较小的数字使用 8 位整数，对较大的数字使用 16 位整数......等等。这已将矢量大小减小到 size*0.7（不令人满意，因为它没有利用上述特定特征）
- 我不太确定下面link中描述的这种方法是否适用于我的数据：http://ygdes.com/ddj-3r/ddj-3r_compact.html 我不太了解该方法，但它鼓励我尝试类似的事情，因为我认为数据中存在一些可以利用的顺序。 例如，我尝试将任何大于 255 的数字 (n) 重新分配给 n-255，以便我可以将整数保留在 8 位域中，因为我知道在该索引之前没有数字大于 255。但是，我无法区分重新分配的数字和重复的数字......所以这个想法不起作用，除非采取更多技巧来扭转重新分配......
这里是 link 到第 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：
非常感谢所有给出的答案。我从他们身上学到了很多。对于那些有兴趣修改更大数据集的人，以下 link 具有类似数据集的 1100 万个元素（压缩 33MB）
https://drive.google.com/file/d/1Aohfu6II6OdN-CqnDll7DeHPgEDLMPjP/view
解压缩数据后，您可以使用以下 C++ 片段将数据读入向量
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 开始。只需使用 ceiling(log2(i)) 位来存储索引 处的数字i（其中 i 从 1 开始）。对于具有 24,977 个值的第一个示例，使用 32 位整数将其压缩为向量大小的 43%。
所需的位数仅取决于向量的长度，n。位数为：
1 - 2上限(log2(n)) + n 上限(log2(n))
正如 Falk Hüffner 所指出的，一种更简单的方法是为所有 ceiling(log2(n)).可变位数将始终小于该位数，但不会比大 n.
少很多如果开头有一个 运行 个零是很常见的，那么用一个计数压缩它们。余数中只有少数两个或三个数字的 运行，因此 运行 长度编码将无济于事，除了最初的 运行 个零。
考虑到索引 k 处的每个值（从零开始的索引），可以使用算术编码方法削减另外 2% 左右（对于大集合）一个非常大的整数的基数 k+1。这将占用 ceiling(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;
}
正如我在评论中所建议的那样，您可以将数据表示为 8 位。有一些简单的方法可以有效地做到这一点，不需要模块化算法..
您可以为此使用联合或指针，例如在 C++ 中，如果您有：
unsigned int data32[]={0,0,0,...};
unsigned char *data08=data32;
或者您可以将其复制到 4 BYTE 数组，但那样会更慢。
如果您出于任何原因必须使用模运算，那么您可能希望这样做：
x &255
(x>> 8)&255
(x>>16)&255
(x>>24)&255
现在 I have tried LZW 在您的新数据上，没有任何数据重新排序（单个 LZW）的压缩比结果为 81-82%（取决于字典大小，我建议使用 10 位 LZW 字典）这不是正如预期的那样好。因此，我将数据重新排序为 4 个数组（就像您所做的那样），因此第一个数组的 8 位最低，最后一个最高。 12 位字典的结果，其中：
ratio08: 144%
ratio08: 132%
ratio08: 26%
ratio08: 0%
total: 75%
10 位字典的结果，其中：
ratio08: 123%
ratio08: 117%
ratio08: 28%
ratio08: 0%
total: 67%
表明 LZW 对最低字节不利（随着大小的增加，对更高字节的影响也会更差）因此仅将其用于更高的字节，这将进一步提高压缩率。
不过我希望霍夫曼会带来更好的结果，所以
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%
这与预期的香农熵估计非常匹配（不考虑解码 table）...
然而，对于非常大的数据集，我希望朴素的霍夫曼会开始变得比单独的 4x 霍夫曼稍微好一些...
另请注意，结果被截断，因此 0% 不是零，而是小于 1% ...
[Edit1] 300 000 000 个条目估计
所以为了模拟你的 300M 32 位数字的条件，我使用你的数据的 16 位数字子部分，具有类似的“空 space”属性。
log2(300 000 000) = ~28
28/32 * 16 = 14
所以我只使用 2^14 个 16 位数字，它们应该与您的 300M 32 位数字具有相似的属性 8 位霍夫曼编码导致：
ratio08 = 97.980%
ratio08 = 59.534%
total08 = 78.757%
所以我估计 encoded/decoded 大小减少 ~1.25 之间的比例为 80%。 （希望我的假设没有搞砸）。
解决每个压缩问题都应该从分析开始。
我查看了包含前 24976 个值的原始数据文件。最小值为 0，最大值为 24950。数据的“斜率”约为 1。但是，如果最大值如前所述仅为 33M@100M 值，则它应该随时间减少。 slope=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 位。前 6 个选择我们直接用 3 位编码。如果它是 7 或 8，我们会发送一个额外的位来指示我们是指 9 还是 10。
此外，我们可以从可能值列表中排除直接编码的任何值。否则我们有两种方法来编码相同的值，这是多余的。
您正在处理的数据“几乎”已排序，因此您可以将其用于 delta 编码以产生很好的效果。
简单的做法如下：
查找 运行s 数据，用 R_i = (v,l,N) 表示，其中 l 是 运行 的长度，N 是位深度需要对排序的 运行 进行增量编码，v 是（已排序的）运行 的第一个元素的值（增量编码需要）。 运行本身然后只需要为 运行 中的每个条目存储 2 条信息：运行 中每个排序元素的 idx 和增量。注意，要存储每个排序元素的 idx，每个 idx 只需要 log_2(l) 位，其中 l 是 运行.
与未压缩形式使用的字节数相比，编码的工作原理是尝试找到最少的位数来完全编码 运行。实际上，这可以通过找到最长的 运行 来实现，该 运行 编码为每个元素的固定字节数。
要解码，只需解码 运行-by-运行（按顺序）首先解码增量 coding/compression，然后取消排序。
下面是一些 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
其中 bit compression 是 Mark Adler 方法的压缩率。正如其他人所指出的，压缩每个条目的位对于大数据来说不会很好地扩展，我们应该期望 n.
同时，上述增量 + 排序压缩保持接近其理论最佳值 .5。