快速高效的Java整型数组压缩工具

Question

在Java中，我的程序有一部分需要在内存中处理吉格字节的int[]数组。它们已经排序，并且只包含自然数（例如1、2、3、4 ...直到n），它们代表文件行。数字n是文件中行数的数量，最大可以为100000。因此，这些数组仅仅是文件中所有行的子集。如您所预料的那样，有成千上万种这样的子集，其中一些可能很重要。对于这些子集中的数据分布（我们现在称之为数组），它完全是随机的：长数组可能有50000个数字，而小数组则可能只有1500个数字；每个数组都包含不可预测的序列，比如[3, 10, 11, 12, 13, 14, 15, 135, 136,...]或者[2, 3, 746, 7889, 7892, 80000,...]。

由于我有很多数组需要压缩/解压缩，因此我希望找到执行时间最快的解决方案。因此，开销应尽可能小。您会推荐哪个库？

- Sophie Sperner

---

从您的描述中，似乎有很多数字出现了多次。在这种情况下，运行长度编码（非常容易实现）可能会非常有效。 - user395760

不，数字不会重复出现，它们只会在数组中出现一次。 - Sophie Sperner

它们总是排序的吗？听起来似乎使用BitSet最简单。 - Louis Wasserman

Answer 1

您可以对数据进行无损预处理以提高压缩率。将第一个值保持不变。使每个后续值成为它与前一个值之间的差减1。您可以确保这些差异是非负的。现在，使用字节序列将每个整数编码为可变长度整数。例如，在解码时，0..127是一个字节。如果该第一个字节的高位设置了（128..255），则将低7位作为整数的低7位，并获取下一个字节。如果高位为零，则使用整个字节作为下一个更重要的8位，或者如果高位为1，则仅使用低7位。继续，直到得到高位等于零的字节，这表示整数的结束。

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

为了在牺牲压缩程度的情况下获得最快的压缩和解压缩速度，请查看lz4。如果您不需要如此快的速度，请查看zlib，其中您可以通过压缩级别选择压缩速度和效果。

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

请注意，在后一种情况中，即使用一半行号时，使用位数组将更有效，未压缩为12500字节。在这种情况下，数据无法压缩，因为位图似乎是随机的（一半位设置，一半未设置）。更多或更少，例如25000或75000，都会产生可压缩的位图，大小约为10500字节。

压缩位图对于大约12500行及以上的内容更小，而差分可变整数压缩对于少于12500行的内容更小。这个截断点是两种方法具有大约12500字节未压缩大小的点。

- Mark Adler

Answer 2

我建议使用 snappy-java，它是Google的 snappy的一个移植版本。

- Anujan

Answer 3

也许这个也能帮到你： 在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

- Kuchi