4

在 Java 中，在我的程序中的某个时刻，我必须int[]在内存中处理千兆字节的数组。它们经过排序并且仅包含代表文件行的自然数字（如1, 2, 3, 4, ..., up to ）。nNumbern是文件中的行数，可以是最大值100000。所以数组只是文件中一组所有行的子集。正如您可能计算的那样，有数百万个这样的子集，其中一些会很重要。至于这些子集中的数据分布（我们现在称它们为数组），它是完全随机的：即一个长数组可能是50000数字，而一个小数组可能只有1500数字；并且每个数组都包含不可预测的序列，因此它可以是[3, 10, 11, 12, 13, 14, 15, 135, 136, ...]或[2, 3, 746, 7889, 7892, 80000,...]。

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

你会推荐什么图书馆？

4

3 回答 3

3

您可以无损地预处理数据以提高压缩率。保持第一个值不变。使每个后续值与前一个值之间的差减一。您可以放心，这些差异是非负的。现在使用字节序列将每个整数编码为可变长度整数。例如，解码时，0..127 是一个字节。如果设置了第一个字节的高位（128..255），则将低七位作为整数的低七位，并获取下一个字节。如果高位为零，则使用整个字节作为接下来的八位更高的有效位，或者如果高位为 1，则仅使用低七位。继续直到你得到一个高位为零的字节，这表示整数的结尾。

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

为了在牺牲压缩程度的同时获得最大的压缩和解压缩速度，请查看lz4。如果您不需要那么快的东西，请查看zlib，您可以在其中选择压缩速度和压缩级别的有效性。

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

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

对于大约 12500 行号及以上，压缩位图较小，而对于少于约 12500 行号，压缩的差分变量整数较小。该截止点是两种方法具有大约相同的 12500 字节的未压缩大小的点。

于 2013-04-24T05:06:54.137 回答
1

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

于 2013-04-23T18:54:50.050 回答
0

也许这也可以帮助你： 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

于 2013-04-23T18:52:09.867 回答