JavaFastPFOR：一个简单的Java整数压缩库

许可证

该代码根据Apache许可证2.0版发布 http://www.apache.org/licenses/。

这个库的功能是什么？

它是一个用于非常快速地压缩和解压缩整数数组的库。假设您数组中的大多数（但不是全部）值使用的位数远少于32位，或者整数之间的差值使用的位数远少于32位。这种类型的数组在数据库和信息检索中使用差分编码时经常出现（例如，在倒排索引或列式存储中）。

请注意，随机整数是无法通过这个库或任何其他方法压缩的。如果您有系统地压缩随机整数的方法，那么通过递归应用您的技术，您就可以将任何数据源压缩为零。

该库可以以每秒超过12亿个整数（4.5 GB/s）的速度解压缩整数。在压缩整数数组时，它比通用编解码器（如Snappy、LZ4等）要快得多。

该库被用于LinkedIn Pinot，一个实时分布式OLAP数据存储。部分库已集成到Parquet（http://parquet.io/）中。该库的修改版本包含在搜索引擎Terrier（http://terrier.org/）中。ClueWeb Tools（https://github.com/lintool/clueweb）也使用了这个库。它还被Apache NiFi（https://nifi.apache.org）使用。

这个库启发了Apache Lucene和Apache Lucene.NET使用的一种压缩方案（例如，参见http://lucene.apache.org/core/4_6_1/core/org/apache/lucene/util/PForDeltaDocIdSet.html）。

它是fastpfor C++库（https://github.com/lemire/FastPFor）的Java移植版本。还有一个Go移植版（https://github.com/reducedb/encoding）。C++库被zsearch引擎（http://victorparmar.github.com/zsearch/）以及GMAP和GSNAP（http://research-pub.gene.com/gmap/）使用。

使用方法

非常简单的用法：

        IntegratedIntCompressor iic = new IntegratedIntCompressor();
        int[] data = ... ; // 待压缩的数据
        int[] compressed = iic.compress(data); // 压缩后的数组
        int[] recov = iic.uncompress(compressed); // 等同于data

更多示例，请参见example.java或examples文件夹。

JavaFastPFOR支持分块压缩和解压缩数据（例如，参见https://github.com/lemire/JavaFastPFOR/blob/master/example.java中的advancedExample）。

一些编解码器（"集成编解码器"）假设整数是有序的，并使用差分编码（它们压缩差值）。它们可以在me.lemire.integercompression.differential包中找到。大多数其他编解码器则不是这样。

英特尔(R)的Java团队引入了基于Java Vector API的FastPFOR向量实现，相比非向量化实现显示出显著的性能提升。使用示例请参见examples/vector/Example.java。该功能需要JDK 19+，目前面向高级用户。

Maven中央仓库

在您自己的项目中使用这段代码很简单，只需在pom.xml文件中添加以下代码：

    <dependencies>
         <dependency>
	     <groupId>me.lemire.integercompression</groupId>
	     <artifactId>JavaFastPFOR</artifactId>
	     <version>[0.2,)</version>
         </dependency>
     </dependencies>

当然，您应该将"version"替换为您想要的版本。

您也可以从Maven中央仓库下载JavaFastPFOR： http://repo1.maven.org/maven2/me/lemire/integercompression/JavaFastPFOR/

为什么要开发这个库？

我们没有找到任何实现最先进的整数编码技术（如Binary Packing、NewPFD、OptPFD、Variable Byte、Simple 9等）的Java库。所以我们自己写了一个。

线程安全

一些编解码器是线程安全的，而其他则不是。因此，最好每个线程使用一个编解码器。无论如何，一个编解码器实例的内存使用量很小。

尽管如此，如果您想重用编解码器实例，请注意，按照惯例，除非编解码器的文档指明它不是线程安全的，否则可以假定它是线程安全的。

作者

主要贡献者

Daniel Lemire，http://lemire.me/en/
Muraoka Taro，https://github.com/koron

其他贡献者包括

Terrier团队（Matteo Catena、Craig Macdonald、Saúl Vargas和Iadh Ounis）
Di Wu，http://www.facebook.com/diwu1989
Stefan Ackermann，https://github.com/Stivo
Samit Roy，https://github.com/roysamit
Mulugeta Mammo，https://github.com/mulugetam（VectorFastPFOR的贡献者）与Kamikaze PForDelta库相比如何?

在我们的测试中,Kamikaze PForDelta比我们的实现要慢。请查看benchmarkresults目录了解一些结果。

https://github.com/lemire/JavaFastPFOR/blob/master/benchmarkresults/benchmarkresults_icore7_10may2013.txt

参考: http://sna-projects.com/kamikaze/

要求

0.1.12版本及之前的版本需要Java 7或更高版本。

当前的开发版本假定使用JDK 11或更高版本。

速度如何?

编译代码并执行me.lemire.integercompression.benchmarktools.Benchmark。

速度始终以每秒百万整数为单位报告。

对于Maven用户

mvn compile
mvn exec:java

你可以按以下方式运行我们的示例:

mvn package
javac -cp target/classes/:. example.java
java -cp target/classes/:. example

对于ant用户(遗留,目前未经测试)

如果你使用Apache ant,请尝试以下操作:

$ ant Benchmark

或:

$ ant Benchmark -Dbenchmark.target=BenchmarkBitPacking

API文档

http://www.javadoc.io/doc/me.lemire.integercompression/JavaFastPFOR/

想了解更多?

这个库是ECIR 2014最佳论文的一个关键组成部分:

Matteo Catena, Craig Macdonald, Iadh Ounis, 《关于搜索引擎效率的倒排索引压缩》, 计算机科学讲义 8416 (ECIR 2014), 2014年。 http://dx.doi.org/10.1007/978-3-319-06028-6_30

我们撰写了几篇研究论文,记录了这里实现的许多CODEC:

Daniel Lemire, Nathan Kurz, Christoph Rupp, 《Stream VByte: 更快的面向字节的整数压缩》, 信息处理快报 (即将发表) https://arxiv.org/abs/1709.08990
Daniel Lemire, Leonid Boytsov, Nathan Kurz, 《SIMD压缩和排序整数的交集》, 软件实践与经验第46卷, 第6期, 第723-749页, 2016年6月 http://arxiv.org/abs/1401.6399
Daniel Lemire 和 Leonid Boytsov, 《通过矢量化每秒解码数十亿个整数》, 软件实践与经验 45 (1), 2015年。 http://arxiv.org/abs/1209.2137 http://onlinelibrary.wiley.com/doi/10.1002/spe.2203/abstract
Jeff Plaisance, Nathan Kurz, Daniel Lemire, 《矢量化VByte解码》, 国际网络算法研讨会 2015, 2015年。 http://arxiv.org/abs/1503.07387
Wayne Xin Zhao, Xudong Zhang, Daniel Lemire, Dongdong Shan, Jian-Yun Nie, Hongfei Yan, Ji-Rong Wen, 《加速压缩算法的一般SIMD方法》, ACM信息系统交易 33 (3), 2015年。 http://arxiv.org/abs/1502.01916

Ikhtear Sharif以这个库为主题写了他的硕士论文:

Ikhtear Sharif, 《表格上快速整数压缩技术的性能评估》, 硕士论文, UNB 2013年。 https://unbscholar.lib.unb.ca/islandora/object/unbscholar%3A9399/datastream/PDF/view

他还在网上发布了他的幻灯片: http://www.slideshare.net/ikhtearSharif/ikhtear-defense

其他推荐的库

Go语言的快速整数压缩: https://github.com/ronanh/intcomp
Encoding: Go语言的整数压缩库 https://github.com/zhenjl/encoding
CSharpFastPFOR: C#整数压缩库 https://github.com/Genbox/CSharpFastPFOR
TurboPFor是一个C语言库,提供了许多有趣的优化和Java包装器。值得一看!(使用GPL许可证。) https://github.com/powturbo/TurboPFor