Repository files navigation

ncrlite is a simple and fast compression format specifically designed to compress an unorderedset of positive integers (below 2⁶⁴).This repository contains aGo packagethat implements it and a commandline tool.

Warning. The file format is not yet final.

ncrlite achieves smaller compressed sizes than general-purpose compressors.

Compared to more specialized compressors,ncrlite outperformsElias–Fano.nrclite performs slightly worse thanRice coding on random sets,but is still close to the theoretical limit oflg N choose k.ncrlite does perform better than Rice coding on skewed sets like {9900, ..., 10000}.

There areN choose k subsets ofk positive integers belowN.Thus there is a hard limit: no compression method can encodeeverysuch set in less thanlg N choose k bits.

Of course a compression method can beat the limit for specific sets,but it will have to compensate by using more bits for others.

InstallGo and run

$ go install github.com/bwesterb/go-ncrlite/cmd/ncrlite@latest

Now you can usencrlite.

ncrlite takes as input a textfile with a positive number on each line.

$ cat dunbar515351505001500

To compress simply run:

$ ncrlite dunbar

This will createdunbar.ncrlite and removedunbar.

The input file does not have to be sorted (numerically). If it is not,ncrlite will sort the input first, which is slower.

To decompress, run:

$ ncrlite -d dunbar.ncrlite

This will createdunbar and removedunbar.ncrlite. The output file is always sorted.

At the moment, thencrlite commandline tool only supports the simple text format.Reach out if another is useful.

ncrlite supports several familiar flags.

  -f, --force    overwrite output  -k, --keep    keep (don't delete) input file  -c, --stdout    write to stdout; implies -k

Without specifying a filename (or using-),ncrlite will read fromstdin and write tostdout.

With-i we can inspect a compressed file:

$ ncrlite -i le.csv.ncrlite max bitlength        14codelength h[0]      9dictionary size      56bCodebook bitlengths: 0 111111110 1 11111110 2 1111100 3 1111101 4 11110 5 1100 6 1101 7 100 8 00 9 0110 10111 111012 111111013 111111111014 1111111111Maximum value    (N)  382584265Number of values (k)  512652Theoretical best avg  703953.8BOverhead              0.4%

In short: we store the deltas (differences) which are each prefixed by a Huffmancode for their bitlength. The Huffman code is stored using bzip2's method.

Now, in detail. The file starts with thesize of the set as an unsigned varint.

There are two special cases.

1. If the size of the set is zero, the file ends immediately after the size(without endmarker.)

2. If the size of the set is one, then the value of that element is encodedas an unsigned varint after it and the file ends (without endmarker.)

The values of the set are not encoded directly, but instead theirdeltasare encoded. Thenth delta is the difference between thenthand then-1th value, considering the set as a sorted list.

The first delta is special: it's the minimum value of the set plus oneso that a delta is never zero.

For each deltad, we consider itsbitlength. That is the leastlsuch that2^(l+1) > d. Note that this is different from the typicaldefinition of bitlength being one smaller: the length of 1 is 0 and of 4 is 2.

The six least significant bits of the next byte encode the largest bitlengthof any delta that occurs. We assign to that bitlength, and each smallerbitlength, a canonical Huffman code by encoding the length of each of theircodewords.

The next six bits (that is: the two most significantbits of the byte used for the largest bitlength, and the four least significantbits of the byte afterward) encode the length of the codeword for thezero bitlength.

We continue with the remaining bitlengths in order. If the next bitlengthhas a codeword of the same length as the previous codeword, we encode thiswith a single bit 1.

Instead, if the codeword is one larger we encode this as first a single bit 0to say we're not done; then a single bit 1 to say the next is larger;and finally a 1 to say we're done. Together:0b101.If it's two larger we repeat twice:0b10101. And so on. If the codewordis one smaller we use0b001, and repeat00 if the difference is larger.

After having encoded the Huffman code for the bitlengths, we encodethe deltas themselves. First we write the Huffman code for the bitlength.Then we write the delta with that many bits, without its most significant bitas it's implied.

Finally, we write the endmarker0xaa =0b10101010. This allows for simplerdecompression using prefix tables. The remaining high bits in the final byteare set to zero.