快速的Java int[]压缩工具

Question

在Java语言中，在我的程序中的某个时刻，我必须在内存中处理千兆字节的int[]数组。它们是经过排序的，并且只包含代表文件行的自然数字(如1, 2, 3, 4，...，直到n)。Number n是文件中的行数，它可以是最大的100000。因此，数组只是文件中所有行的集合的子集。正如你可能计算的那样，有数百万个这样的子集，其中一些可能会有很大的权重。至于那些子集内的数据分布(现在我们称它们为数组)，它是完全随机的:也就是说，可能会出现一个由50000数组成的长数组和一个只有1500数的小数组；并且每个数组都包含不可预测的序列，因此它可以是[3, 10, 11, 12, 13, 14, 15, 135, 136, ...]或[2, 3, 746, 7889, 7892, 80000,...]。

因为我有很多数组要压缩/解压缩，所以我想找到每次执行所花费的时间最快的解决方案。因此，开销应该尽可能地最小化。

你会推荐哪种库？

Answer 1

您可以无损地对数据进行预处理，以提高压缩效果。保留第一个值不变。使每个后续值与前一个值之差减1。您可以放心，这样的差异是非负面的。现在，使用字节序列将每个整数编码为可变长度的整数。例如，解码时，0..127是一个字节。如果设置了第一个字节的高位(128..255)，则将低七位作为整数的低七位，并获取下一个字节。如果高位为0，则使用整个字节作为接下来的8个有效位；如果高位为1，则仅使用低7位。继续，直到到达高位等于零的字节，这表示整数的结束。

现在，您已经将整数编码为一个字节序列，这可能比将每个原始整数编码为四个或八个字节要短得多。此外，您现在可以应用任何处理字节序列的标准压缩技术，并可能从中获得一些收益。例如，如果一系列连续的行号很常见，那么你得到的是一个零字节的字符串，它是高度可压缩的。

要在牺牲压缩程度的情况下获得最快的压缩和解压缩速度，请查看lz4。如果你不需要更快的东西，看看zlib，在那里你可以根据压缩级别选择压缩速度和效果。

对于您的示例，随机选择10000个中的1500个将导致大约1720字节的未压缩，1600字节的压缩。随机选择100000个中的50000个会导致50000个字节未压缩，18600个字节压缩。压缩是用最快的zlib压缩完成的，级别1。

请注意，在后一种情况下，使用一半的行号，使用位数组会更有效，它将是未压缩的12500字节。在这种情况下，数据不能被压缩，因为位图看起来是随机的(设置了一半的位，另一半没有设置)。或多或少，例如25000或75000，两者都产生可压缩的位图，两者都约为10500字节。

压缩的位图对于大约12500个或更多的行号是较小的，而对于少于12500个行号的压缩的差分变量整数是较小的。这一临界点是两种方法的未压缩大小大致相同的12500字节。

Answer 2

我推荐snappy-java，它是谷歌的snappy端口

Answer 3

也许这也能帮到你：Compressing array of integers in java

您是否必须对数组进行大量计算，或者它是只读的？

编辑：

//If the space is more important than performance this might work:
//Not this might be totally stupid for some cases
// First element should be false since its the 0 ;)
boolean[] numbers = { false, true, true, true, false, false, true };

for (int i = 0; i <= numbers.length - 1; i++) {
    if (numbers[i]) {
    // or do some calculations on/with a copy of i
    System.out.println(i);
    }
}

由于布尔数组使用1个字节来存储每个信息(+开销)，这意味着最多有100'000个条目:每个数组100'000个字节= ~97kb