Best Compression algorithm for a sequence of integ

Question

I have a large array with a range of integers that are mostly continuous, eg 1-100, 110-160, etc. All integers are positive. What would be the best algorithm to compress this?

I tried the deflate algorithm but that gives me only 50% compression. Note that the algorithm cannot be lossy.

All numbers are unique and progressively increasing.

Also if you can point me to the java implementation of such algorithm that would be great.

Answer 1

In addition to the other solutions:

You could find "dense" areas and use a bitmap to store them.

So for example:

If you have 1000 numbers in 400 ranges between 1000-3000, you could use a single bit to denote the existence of a number and two ints to denote the range. Total storage for this range is 2000 bits + 2 ints, so you can store that info in 254bytes, which is pretty awesome since even short integers will take up two bytes each, so for this example you get 7X savings.

The denser the areas the better this algorithm will do, but at some point just storing start and finish will be cheaper.

Answer 2

I'd suggest taking a look at Huffman Coding, a special case of Arithmetic Coding. In both cases you analyse your starting sequence to determine the relative frequencies of different values. More-frequently-occurring values are encoded with fewer bits than the less-frequently-occurring ones.

Answer 3

The basic idea you should probably use is, for each range of consecutive integers (I will call these ranges), to store the starting number and the size of the range. For example, if you have a list of 1000 integers, but there are only 10 separate ranges, you can store a mere 20 integers (1 start number and 1 size for each range) to represent this data which would be a compression rate of 98%. Fortunately, there are some more optimizations you can make which will help with cases where the number of ranges is larger.

1. Store the offset of the starting number relative to the previous starting number, rather than the starting number itself. The advantage here is that the numbers you store will generally require less bits (this may come in handy in later optimization suggestions). Additionally, if you only stored the starting numbers, these numbers would all be unique, while storing the offset gives a chance that the numbers are close or even repeat which may allow for even further compression with another method being applied after.

2. Use the minimum number of bits possible for both types of integers. You can iterate over the numbers to obtain the largest offset of a starting integer as well as the size of the largest range. You can then use a datatype that most efficiently stores these integers and simply specify the datatype or number of bits at the start of the compressed data. For example, if the largest offset of a starting integer is only 12,000, and the largest range is 9,000 long, then you can use a 2 byte unsigned integer for all of these. You could then cram the pair 2,2 at the start of the compressed data to show that 2 bytes is used for both integers. Of course you can fit this information into a single byte using a little bit of bit manipulation. If you are comfortable with doing a lot of heavy bit manipulation you could store each number as the minimum possible amount of bits rather than conforming to 1, 2, 4, or 8 byte representations.

With those two optimizations lets look at a couple of examples (each is 4,000 bytes):

1. 1,000 integers, biggest offset is 500, 10 ranges
2. 1,000 integers, biggest offset is 100, 50 ranges
3. 1,000 integers, biggest offset is 50, 100 ranges

WITHOUT OPTIMIZATIONS

1. 20 integers, 4 bytes each = 80 bytes. COMPRESSION = 98%
2. 100 integers, 4 bytes each = 400 bytes. COMPRESSION = 90%
3. 200 integers, 4 bytes each = 800 bytes. COMPRESSION = 80%

WITH OPTIMIZATIONS

1. 1 byte header + 20 numbers, 1 byte each = 21 bytes. COMPRESSION = 99.475%
2. 1 byte header + 100 numbers, 1 byte each = 101 bytes. COMPRESSION = 97.475%
3. 1 byte header + 200 numbers, 1 byte each = 201 bytes. COMPRESSION = 94.975%

Answer 4

If you have series of repeated values RLE is the easiest to implement and could give you a good result. Nontheless other more advanced algorithms that take into account the entrophy such as LZW, which is now patent-free, can usually achive a much better compression.

You can take a look at these and other lossless algorithms here.

Answer 5

I know this is an old message thread, but I am including my personal PHP test of the SKIP/TAKE idea I found here. I'm calling mine STEP(+)/SPAN(-). Perhaps someone might find it helpful.

NOTE: I implemented the ability to allow duplicate integers as well as negative integers even though the original question involved positive, non-duplicated integers. Feel free to tweak it if you want to try and shave a byte or two.

CODE:

  // $integers_array can contain any integers; no floating point, please. Duplicates okay.
  $integers_array = [118, 68, -9, 82, 67, -36, 15, 27, 26, 138, 45, 121, 72, 63, 73, -35,
                    68, 46, 37, -28, -12, 42, 101, 21, 35, 100, 44, 13, 125, 142, 36, 88,
                    113, -40, 40, -25, 116, -21, 123, -10, 43, 130, 7, 39, 69, 102, 24,
                    75, 64, 127, 109, 38, 41, -23, 21, -21, 101, 138, 51, 4, 93, -29, -13];

  // Order from least to greatest... This routine does NOT save original order of integers.
  sort($integers_array, SORT_NUMERIC); 

  // Start with the least value... NOTE: This removes the first value from the array.
  $start = $current = array_shift($integers_array);    

  // This caps the end of the array, so we can easily get the last step or span value.
  array_push($integers_array, $start - 1);

  // Create the compressed array...
  $compressed_array = [$start];
  foreach ($integers_array as $next_value) {
    // Range of $current to $next_value is our "skip" range. I call it a "step" instead.
    $step = $next_value - $current;
    if ($step == 1) {
        // Took a single step, wait to find the end of a series of seqential numbers.
        $current = $next_value;
    } else {
        // Range of $start to $current is our "take" range. I call it a "span" instead.
        $span = $current - $start;
        // If $span is positive, use "negative" to identify these as sequential numbers. 
        if ($span > 0) array_push($compressed_array, -$span);
        // If $step is positive, move forward. If $step is zero, the number is duplicate.
        if ($step >= 0) array_push($compressed_array, $step);
        // In any case, we are resetting our start of potentialy sequential numbers.
        $start = $current = $next_value;
    }
  }

  // OPTIONAL: The following code attempts to compress things further in a variety of ways.

  // A quick check to see what pack size we can use.
  $largest_integer = max(max($compressed_array),-min($compressed_array));
  if ($largest_integer < pow(2,7)) $pack_size = 'c';
  elseif ($largest_integer < pow(2,15)) $pack_size = 's';
  elseif ($largest_integer < pow(2,31)) $pack_size = 'l';
  elseif ($largest_integer < pow(2,63)) $pack_size = 'q';
  else die('Too freaking large, try something else!');

  // NOTE: I did not implement the MSB feature mentioned by Marc Gravell.
  // I'm just pre-pending the $pack_size as the first byte, so I know how to unpack it.
  $packed_string = $pack_size;

  // Save compressed array to compressed string and binary packed string.
  $compressed_string = '';
  foreach ($compressed_array as $value) {
      $compressed_string .= ($value < 0) ? $value : '+'.$value;
      $packed_string .= pack($pack_size, $value);
  }

  // We can possibly compress it more with gzip if there are lots of similar values.      
  $gz_string = gzcompress($packed_string);

  // These were all just size tests I left in for you.
  $base64_string = base64_encode($packed_string);
  $gz64_string = base64_encode($gz_string);
  $compressed_string = trim($compressed_string,'+');  // Don't need leading '+'.
  echo "<hr>\nOriginal Array has "
    .count($integers_array)
    .' elements: {not showing, since I modified the original array directly}';
  echo "<br>\nCompressed Array has "
    .count($compressed_array).' elements: '
    .implode(', ',$compressed_array);
  echo "<br>\nCompressed String has "
    .strlen($compressed_string).' characters: '
    .$compressed_string;
  echo "<br>\nPacked String has "
    .strlen($packed_string).' (some probably not printable) characters: '
    .$packed_string;
  echo "<br>\nBase64 String has "
    .strlen($base64_string).' (all printable) characters: '
    .$base64_string;
  echo "<br>\nGZipped String has "
    .strlen($gz_string).' (some probably not printable) characters: '
    .$gz_string;
  echo "<br>\nBase64 of GZipped String has "
    .strlen($gz64_string).' (all printable) characters: '
    .$gz64_string;

  // NOTICE: The following code reverses the process, starting form the $compressed_array.

  // The first value is always the starting value.
  $current_value = array_shift($compressed_array);
  $uncompressed_array = [$current_value];
  foreach ($compressed_array as $val) {
    if ($val < -1) {
      // For ranges that span more than two values, we have to fill in the values.
      $range = range($current_value + 1, $current_value - $val - 1);
      $uncompressed_array = array_merge($uncompressed_array, $range);
    }
    // Add the step value to the $current_value
    $current_value += abs($val); 
    // Add the newly-determined $current_value to our list. If $val==0, it is a repeat!
    array_push($uncompressed_array, $current_value);      
  }

  // Display the uncompressed array.
  echo "<hr>Reconstituted Array has "
    .count($uncompressed_array).' elements: '
    .implode(', ',$uncompressed_array).
    '<hr>';

OUTPUT:

--------------------------------------------------------------------------------
Original Array has 63 elements: {not showing, since I modified the original array directly}
Compressed Array has 53 elements: -40, 4, -1, 6, -1, 3, 2, 2, 0, 8, -1, 2, -1, 13, 3, 6, 2, 6, 0, 3, 2, -1, 8, -11, 5, 12, -1, 3, -1, 0, -1, 3, -1, 2, 7, 6, 5, 7, -1, 0, -1, 7, 4, 3, 2, 3, 2, 2, 2, 3, 8, 0, 4
Compressed String has 110 characters: -40+4-1+6-1+3+2+2+0+8-1+2-1+13+3+6+2+6+0+3+2-1+8-11+5+12-1+3-1+0-1+3-1+2+7+6+5+7-1+0-1+7+4+3+2+3+2+2+2+3+8+0+4
Packed String has 54 (some probably not printable) characters: cØÿÿÿÿ ÿõ ÿÿÿÿÿÿ
Base64 String has 72 (all printable) characters: Y9gE/wb/AwICAAj/Av8NAwYCBgADAv8I9QUM/wP/AP8D/wIHBgUH/wD/BwQDAgMCAgIDCAAE
GZipped String has 53 (some probably not printable) characters: xœ Ê» ÑÈί€)YšE¨MŠ“^qçºR¬m&Òõ‹%Ê&TFʉùÀ6ÿÁÁ Æ
Base64 of GZipped String has 72 (all printable) characters: eJwNyrsNACAMA9HIzq+AKVmaRahNipNecee6UgSsBW0m0gj1iyXKJlRGjcqJ+cA2/8HBDcY=
--------------------------------------------------------------------------------
Reconstituted Array has 63 elements: -40, -36, -35, -29, -28, -25, -23, -21, -21, -13, -12, -10, -9, 4, 7, 13, 15, 21, 21, 24, 26, 27, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 51, 63, 64, 67, 68, 68, 69, 72, 73, 75, 82, 88, 93, 100, 101, 101, 102, 109, 113, 116, 118, 121, 123, 125, 127, 130, 138, 138, 142
--------------------------------------------------------------------------------

Answer 6

Well, i'm voting for smarter way. All you have to store is [int:startnumber][int/byte/whatever:number of iterations] in this case, you'll turn your example array into 4xInt value. After it you can compress as you want :)