lemire/fastintegercompression.js

Fast integer compression library in JavaScript

FastIntegerCompression

This is an integer compression library in JavaScript, useful for work on indexes. Given an array of small integers, it produces an ArrayBuffer that uses far fewer bytes than the original (using VByte compression). It assumes a modern JavaScript engine with typed arrays.

From the compressed data, you can later recover the original array quickly (at a rate of millions of integers per second).

   // var FastIntegerCompression = require("fastintcompression");// if you use node
   var array = [10,100000,65999,10,10,0,1,1,2000,0xFFFFFFFF];
   var buf = FastIntegerCompression.compress(array);
   var back = FastIntegerCompression.uncompress(buf); // gets back [10,100000,65999,10,10,0,1,1,2000]

By default, non-negative 32-bit integers are expected. If you have signed (negative and positive) 32-bit integers, then you must use distinct functions since we need to code the sign bit:

   // var FastIntegerCompression = require("fastintcompression");// if you use node
   var array = [10,100000,65999,10,10,0,-1,-1,-2000];
   var buf = FastIntegerCompression.compressSigned(array);
   var back = FastIntegerCompression.uncompressSigned(buf); // gets back [10,100000,65999,10,10,0,-1,-1,-2000]

You can install the library under node with the command line

   npm install fastintcompression

This code is made available under the Apache License 2.0.

Suitability

This library is meant to compress arrays of small integers. It is not meant to compress text documents or arrays of large (or random) integers.

Performance numbers

Go to benchmark repository (check the README.md file) and run the benchmark:

$ node test.js
Platform: linux 3.13.0-91-generic x64
Intel(R) Core(TM) i7-4770 CPU @ 3.40GHz
Node version 4.5.0, v8 version 4.5.103.37

input size: 7.813K compressed size: 1000B
FastIntegerCompression.compress x 337,845 ops/sec ±0.93% (92 runs sampled)
Fastest is FastIntegerCompression.compress
FastIntegerCompression.uncompress x 187,694 ops/sec ±0.72% (93 runs sampled)
Fastest is FastIntegerCompression.uncompress

These numbers means that we can uncompress 187,694 1000-integer arrays per second. That's 187 millions of integers per second.

You might also like...

If you like this library, you might also like

• https://github.com/lemire/FastPriorityQueue.js
• https://github.com/lemire/StablePriorityQueue.js
• https://github.com/lemire/FastBitSet.js

fastintegercompression.js's Issues

uncompress(compress([4111338728])) output -183628568 on node 14

why uncompress return signed int ?

How to work with 2 dimensional integer array?

Hello.

Is there any way to compress array such this?

var arr = [
    [8,100000,65978,10,10,0,-1,-1,-2000],
    [9,100000,65979,10,10,0,-1,-1,-2000],
    [10,100000,65999,10,10,0,-1,-1,-3000]
]

Same as code points?

I'm surprised that the output buffer of a compressed code-point array has the same byte size as the uncompressed string. I assume that means that if I encode an array of integers as a UTF-8 string it would result in the same size.

function lengthInUtf8Bytes(str) {
  var m = encodeURIComponent(str).match(/%[89ABab]/g);
  return str.length + (m ? m.length : 0);
}
FastIntCompression.compress(str.split("").map(_ => _.codePointAt(0))).byteLength == lengthInUtf8Bytes(str)

computeHowManyIntegers returns unexpected result

hi, first off, thanks for sharing this!
for me the computeHowManyIntegers doesn't seem to work:
if you change this line
testline
to
if(FastIntegerCompression.computeHowManyIntegers(buf) !== array.length) throw "bad count";
it will show

Compatibility with JavaFastPFOR

One common "rich client" usecase is for a server to do expensive compression, pass the shrunk result along the network, and then the client does relatively cheap decompression. Is FastIntegerCompression.uncompress compatible with the output of any of the algorithms in your other excellent integer compression libraries? That might be something worth advertising at both ends.

Handle negative/floating point

What would be the best way to compress negative and floating point numbers?