Module me.lemire.integercompression
Package me.lemire.integercompression.differential

Class IntegratedBinaryPacking

java.lang.Object
me.lemire.integercompression.differential.IntegratedBinaryPacking
All Implemented Interfaces:
IntegratedIntegerCODEC, SkippableIntegratedIntegerCODEC, IntegerCODEC
public class IntegratedBinaryPacking extends Object implements IntegratedIntegerCODEC, SkippableIntegratedIntegerCODEC
Scheme based on a commonly used idea: can be extremely fast. You should only use this scheme on sorted arrays. Use BinaryPacking if you have unsorted arrays. It encodes integers in blocks of 32 integers. For arrays containing an arbitrary number of integers, you should use it in conjunction with another CODEC: 
 IntegratedIntegerCODEC is = 
 new IntegratedComposition(new IntegratedBinaryPacking(), 
 new IntegratedVariableByte())

For details, please see

Daniel Lemire and Leonid Boytsov, Decoding billions of integers per second through vectorization Software: Practice & Experience http://onlinelibrary.wiley.com/doi/10.1002/spe.2203/abstract http://arxiv.org/abs/1209.2137

Daniel Lemire, Leonid Boytsov, Nathan Kurz, SIMD Compression and the Intersection of Sorted Integers http://arxiv.org/abs/1401.6399

Author:
Daniel Lemire

  • Field Details

  • Constructor Details

    • IntegratedBinaryPacking

      public IntegratedBinaryPacking()

  • Method Details

    • compress

      public void compress(int[] in, IntWrapper inpos, int inlength, int[] out, IntWrapper outpos)
      Description copied from interface: IntegerCODEC
      Compress data from an array to another array. Both inpos and outpos are modified to represent how much data was read and written to. If 12 ints (inlength = 12) are compressed to 3 ints, then inpos will be incremented by 12 while outpos will be incremented by 3. We use IntWrapper to pass the values by reference.
      Specified by:
      compress in interface IntegerCODEC
      Parameters:
      in - input array
      inpos - where to start reading in the array
      inlength - how many integers to compress
      out - output array
      outpos - where to write in the output array

    • uncompress

      public void uncompress(int[] in, IntWrapper inpos, int inlength, int[] out, IntWrapper outpos)
      Description copied from interface: IntegerCODEC
      Uncompress data from an array to another array. Both inpos and outpos parameters are modified to indicate new positions after read/write.
      Specified by:
      uncompress in interface IntegerCODEC
      Parameters:
      in - array containing data in compressed form
      inpos - where to start reading in the array
      inlength - length of the compressed data (ignored by some schemes)
      out - array where to write the compressed output
      outpos - where to start writing the uncompressed output in out

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • headlessCompress

      public void headlessCompress(int[] in, IntWrapper inpos, int inlength, int[] out, IntWrapper outpos, IntWrapper initvalue)
      Description copied from interface: SkippableIntegratedIntegerCODEC
      Compress data from an array to another array. Both inpos and outpos are modified to represent how much data was read and written to if 12 ints (inlength = 12) are compressed to 3 ints, then inpos will be incremented by 12 while outpos will be incremented by 3 we use IntWrapper to pass the values by reference.
      Specified by:
      headlessCompress in interface SkippableIntegratedIntegerCODEC
      Parameters:
      in - input array
      inpos - location in the input array
      inlength - how many integers to compress
      out - output array
      outpos - where to write in the output array
      initvalue - initial value for the purpose of differential coding, the value is automatically updated

    • headlessUncompress

      public void headlessUncompress(int[] in, IntWrapper inpos, int inlength, int[] out, IntWrapper outpos, int num, IntWrapper initvalue)
      Description copied from interface: SkippableIntegratedIntegerCODEC
      Uncompress data from an array to another array. Both inpos and outpos parameters are modified to indicate new positions after read/write.
      Specified by:
      headlessUncompress in interface SkippableIntegratedIntegerCODEC
      Parameters:
      in - array containing data in compressed form
      inpos - where to start reading in the array
      inlength - length of the compressed data (ignored by some schemes)
      out - array where to write the compressed output
      outpos - where to write the compressed output in out
      num - number of integers we want to decode, the actual number of integers decoded can be less
      initvalue - initial value for the purpose of differential coding, the value is automatically updated

    • maxHeadlessCompressedLength

      public int maxHeadlessCompressedLength(IntWrapper compressedPositions, int inlength)
      Description copied from interface: SkippableIntegratedIntegerCODEC
      Compute the maximum number of integers that might be required to store the compressed form of a given input array segment, without headers.

      This is useful to pre-allocate the output buffer before calling SkippableIntegratedIntegerCODEC.headlessCompress(int[], IntWrapper, int, int[], IntWrapper, IntWrapper).

      Specified by:
      maxHeadlessCompressedLength in interface SkippableIntegratedIntegerCODEC
      Parameters:
      compressedPositions - since not all schemes compress every input integer, this parameter returns how many input integers will actually be compressed. This is useful when composing multiple schemes.
      inlength - number of integers to be compressed
      Returns:
      the maximum number of integers needed in the output array