Compressing an unsorted list of integers

You see a lot on offer for compressing sorted lists of integers, but not so much on the rather uncomfortable question of how to compress a list of unsorted numbers. So why would you want to do that? Surely all one needs to do is sort the list then compress it? The problem is that in many cases the order of the integers represents information that sorting would destroy. Here is my case in point.

Actual hit-positions in a search engine

In a search-engine you have to make a list of documents in which a term is found. Each document is assigned an identifier. So say we had a list of documents in which the word 'dog' occurs. It might be found in 7 documents: 0,1,1,2,2,3,4,6,11,21,21. We can use an algorithm like FastPFOR because the sorted list can be converted into a list of deltas, or the differences between successive entries. These will typically be much shorter numbers than the actual values. In my case an array of 100 document identifiers compressed down to just 13 integers. Cool. But what if you wanted to store the locations in those documents where the word 'dog' occurred as well? This would bloat the index considerably, since 'dog' might occur 100 times in a single document. I could sort and compress it the same way, but quite often it would be really short, maybe only one entry. Then the compression algorithm would actually increase the list size by three or four-fold, since the overhead for a compressed list adds a number of ints to the start, and – this is the real killer – one compressed list would be needed for each document the word was found in. So trying to compress it the conventional way would first, probably increase the overall index size, and second, you would need to maintain a lot of compressed lists.

The solution

Ideally, we would like just one list of word-positions for each word, just as we had one list of document identifiers for each word. But such a list would have to be unsorted, because if we sort it we would lose the information about which documents those positions refer to. Fortunately, most positions are quite small. They can't be greater then the length of the longest document the word is found in. Or if it was found in only a few documents, or always at the start, the values would be even smaller. Lets say that all the values are less than some amount like 127. (Convenient, huh?) Then the list could be stored in 8-bit integers with one 32-bit integer at the start to say how many bytes there were per integer. Or if 16 bits were needed, then we could use 2-byte ints, or 3 bytes for 24 bits etc. Worst case is when the documents are bigger than 4MB or so, when we will need 32-bit integers. But that's rare.

So the strategy is pretty simple. Scan all the numbers first to see what is the biggest (or smallest negative number) and work out how many bits we will need. I kind of cheat by rounding this up to the nearest 8 bits, but if you're interested you can refine it to have an arbitrary number of bits. But you won't gain much in compression and you will lose something in speed. Here's my Java code. It just uses ByteBuffer to build arbitrary-sized ints up to 32 bits, in 8-bit hops, and then stores the list as an array of 32-bit ints – compressed, of course. So typically what you'd expect is a 25%-50% reduction in the array size and in some cases 75%. Compressing it further by any significant amount seems to be impossible, given the near-random nature of the data.

I offer no guarantees that this works for all cases etc. But it is freeware. Do what you like with it.

/** * Compress/decompress an array of one to four-byte ints * @author desmond */ public class UnsortedIntCompressor { /** * Find out how many bits we'll need to represent this array of ints * @param maxValue the maximum positive value * @param minValue the minimum negative value or 0 * @return the number of bits needed, rounded to nearest 8, max 32 */ private static int bitsNeeded( int maxValue, int minValue ) { int minBits = 0; int maxBits = 32; if ( minValue == 0 ) minBits = 0; else if ( minValue >= -128 ) minBits = 8; else if ( minValue >= -32768 ) minBits = 16; else if ( minValue >= -8388608 ) minBits = 24; else minBits = 32; if ( maxValue <= 127 ) maxBits = 8; else if ( maxValue < 32767 ) maxBits = 16; else if ( maxValue < 8388607 ) maxBits = 24; else maxBits = 32; return (maxBits>=minBits)?maxBits:minBits; } /** * Compress an array of ints * @param array an array of unsorted ints to compress * @return the compressed array */ public static int[] compress( int[] array ) { int maxValue = 0; int minValue = 0; for ( int i=0;i<array.length;i++ ) { int value = array[i]; if ( value > maxValue ) maxValue = array[i]; else if ( value < minValue ) minValue = value; } int numBits = bitsNeeded( maxValue, minValue ); // the first entry will store the number of bits/8 int numBytes = numBits/8; // plus first entry int len = array.length*numBytes + 4; // 3 is the maximum overrun ByteBuffer buf = ByteBuffer.allocate(len+3); buf.putInt(numBytes); for ( int i=0,j=0;i<array.length;i++ ) { int value = array[i]; if ( numBits>24 ) buf.put((byte)(value>>>24)); if ( numBits > 16 ) buf.put((byte)(value>>>16)); if ( numBits > 8 ) buf.put((byte)(value>>>8)); buf.put((byte)value); } int resLen = (array.length*numBytes)/4 + 1; if ( (array.length*numBytes)%4 != 0 ) resLen++; int[] res = new int[resLen]; res[0] = numBytes; for ( int i=1;i<resLen;i++ ) { res[i]= buf.getInt(i*4); } return res; } /** * Turn a reduced-byte integer array into a 4-byte integer array * @param array the reduced-byte int array previously compressed * @return an array of ints the same size as before it was compressed */ public static int[] decompress( int[] array ) throws NumberFormatException { int numBytes = array[0]; if ( numBytes < 1 || numBytes > 4 ) throw new NumberFormatException("numBytes must be between 1 and 4"); int len = ((array.length-1)*4)/numBytes; int rem = ((array.length-1)*4)%numBytes; if ( rem == 0 ) { int mask = 0xFF<<((numBytes-1)*8); if ( (array[array.length-1]&mask) == 0 ) len--; } ByteBuffer buf = ByteBuffer.allocate((array.length+1)*4); for ( int i=1;i<array.length;i++ ) buf.putInt(array[i]); int[] res = new int[len]; for ( int i=0;i<len;i++ ) { res[i]= buf.getInt(i*numBytes); res[i] = res[i] >> 8*(4-numBytes); } return res; } public static void main( String[] args ) { Random r = new Random(); int[] uncompressed = new int[100]; // adjust the "23" here to 7 or 31 for testing other int sizes int limit = (int)Math.pow(2,23); for ( int i=0;i<100;i++ ) { uncompressed[i] = r.nextInt(limit); } int[] compressed = null; try { compressed = UnsortedIntCompressor.compress(uncompressed); System.out.println("Length of compressed="+compressed.length); int[] decompressed = UnsortedIntCompressor.decompress(compressed); if ( decompressed.length != 100 ) System.out.println("decompression failed. length="+decompressed.length); for ( int i=0;i<100;i++ ) { if ( decompressed[i] != uncompressed[i] ) System.out.println("uncompressed ("+uncompressed[i] +") not equal to decompressed ("+decompressed[i]+")"); } } catch ( NumberFormatException nfe ) { nfe.printStackTrace(System.out); } } }