在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,… ].

由于我有很多阵列需要压缩/解压缩,所以我希望找到每个执行时间最快的解决方案.因此,开销应尽可能小.

你会推荐什么样的图书馆？

解决方法:

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

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

要在压缩和解压缩的同时牺牲压缩程度,请查看lz4.如果您不需要快速的东西,请查看zlib,您可以在其中选择压缩级别的压缩速度和效果.

对于您的示例,随机选择1500中的1500个导致大约1720个字节未压缩,1600个字节压缩.在100000中随机选择50000个结果,50000字节未压缩,压缩18600个字节.压缩采用最快的zlib压缩,1级.

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

压缩位图对于大约12500行数以及更高而言较小,而压缩的差异变量整数对于少于约12500行数而言较小.该截止点是两种方法具有大约12500字节的相同未压缩大小的点.