一组整数的最佳压缩算法

Question

一组整数的最佳压缩算法

algorithmcompression

79

我有一个大的数组，其中包含一系列整数，这些整数大多数是连续的，例如1-100、110-160等。所有整数都是正数。哪种算法最适合压缩这个数组？

我尝试了deflate算法，但只能让我压缩50％。请注意，该算法不能有损。

所有数字都是唯一的且逐步增加。

另外，如果您可以为我指出这种算法的java实现，那就太好了。

- pdeva

如果您提供一个真实/更大的样本数据集，也许您会得到更好的答案？ - conny

好的，这里有一个关于数据的例子 -int[] data; for (int i =0;i < SIZE; i++) { data[i] = i; }但是，在某些情况下，分布可能不完全连续，例如我们可能有从1-100的值，然后是从122-230的值。但是，所有的值都是唯一且始终递增的。 - pdeva

9

你已经通过描述你的序列的方式提供了很好的压缩。 - sbeliakov

15个回答

40

首先，预处理您的值列表，通过每个值与前一个值（对于第一个值，请假设前一个值为零）之间的差异来获得。在您的情况下，这应该主要给出一系列数字1，这可以更容易地通过大多数压缩算法压缩。

这是PNG格式使用的改进压缩方法（它执行几种差异方法之一，然后使用gzip使用的相同压缩算法）。

- CesarB

补充@CesarB的回答，我们可以将重复数字序列（例如1,1,1,1）压缩成1X4或114。在后者中，前几个数字表示实际数字的长度，后面是重复的次数。这种形式很有用，因为大多数编程语言处理数字比字符串更快。然后，您可以使用deflat、gzip、lz4等进行压缩。 - nir

这个实现是否适用于一系列不完全递增的整数？ - Randoms

18

虽然你可以为你的数据流设计一种定制的算法，但使用现成的编码算法可能更容易。我对Java中可用的压缩算法进行了一些测试，并针对一百万个连续整数的序列发现了以下压缩率：

None        1.0
Deflate     0.50
Filtered    0.34
BZip2       0.11
Lzma        0.06

- brianegge

18

我赞成更智能的方法。你只需要存储[int:起始数字][int/byte/无论什么类型:迭代次数]，在这种情况下，你将把你的示例数组转换为4个整数值。之后，您可以按照所需进行压缩：)

- Tamir

然后再使用压缩算法deflate来再次压缩50%。 - peterchen

4

请问需要翻译的内容是：“...并不存储起始数字，而是存储上一个整数后的差值。” - Dénes Tarján

14

数字的尺寸是多少？除了其他答案外，您可以考虑使用基于128变长编码的方式，这样可以在单个字节中存储较小的数字，同时仍允许更大的数字。 MSB表示“还有另一个字节”-在此处描述。

将其与其他技术结合使用，因此您正在存储“跳过大小”，“采取大小”，“跳过大小”，“采取大小”-但请注意，“跳过”和“采取”都不会为零，因此我们将从每个值中减去一（这样可以为一些值节省一个额外的字节）

所以：

1-100, 110-160

是“跳过1”（假设从零开始以使事情更容易），“取100”，“跳过9”，“取51”的操作；从每个值中减去1，得到以下结果（以小数表示）

0,99,8,50

它的十六进制编码为：

00 63 08 32

如果我们想要跳过/取一个更大的数字，例如300；我们需要减去1得到299 - 但这超过了7位；从低位开始，我们编码7位块和一个MSB来指示继续：

299 = 100101100 = (in blocks of 7): 0000010 0101100

因此，从小的一端开始：

1 0101100 (leading one since continuation)
0 0000010 (leading zero as no more)

提供：

AC 02

我们可以轻松编码大数字，但是小数字（在跳过/获取中很常见）需要更少的空间。

你可以尝试通过 "deflate" 运行此操作，但可能不会有太多帮助...

如果您不想自己处理所有这些混乱的编码内容... 如果您可以创建值的整数数组（0、99、8、60） - 您可以使用协议缓冲区与打包的重复 uint32/uint64 - 它将为您完成所有工作 ;-p

我不“做”Java，但这里有一个完整的C#实现（从我的protobuf-net项目借用了一些编码位）：

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
static class Program
{
    static void Main()
    {
        var data = new List<int>();
        data.AddRange(Enumerable.Range(1, 100));
        data.AddRange(Enumerable.Range(110, 51));
        int[] arr = data.ToArray(), arr2;

        using (MemoryStream ms = new MemoryStream())
        {
            Encode(ms, arr);
            ShowRaw(ms.GetBuffer(), (int)ms.Length);
            ms.Position = 0; // rewind to read it...
            arr2 = Decode(ms);
        }
    }
    static void ShowRaw(byte[] buffer, int len)
    {
        for (int i = 0; i < len; i++)
        {
            Console.Write(buffer[i].ToString("X2"));
        }
        Console.WriteLine();
    }
    static int[] Decode(Stream stream)
    {
        var list = new List<int>();
        uint skip, take;
        int last = 0;
        while (TryDecodeUInt32(stream, out skip)
            && TryDecodeUInt32(stream, out take))
        {
            last += (int)skip+1;
            for(uint i = 0 ; i <= take ; i++) {
                list.Add(last++);
            }
        }
        return list.ToArray();
    }
    static int Encode(Stream stream, int[] data)
    {
        if (data.Length == 0) return 0;
        byte[] buffer = new byte[10];
        int last = -1, len = 0;
        for (int i = 0; i < data.Length; )
        {
            int gap = data[i] - 2 - last, size = 0;
            while (++i < data.Length && data[i] == data[i - 1] + 1) size++;
            last = data[i - 1];
            len += EncodeUInt32((uint)gap, buffer, stream)
                + EncodeUInt32((uint)size, buffer, stream);
        }
        return len;
    }
    public static int EncodeUInt32(uint value, byte[] buffer, Stream stream)
    {
        int count = 0, index = 0;
        do
        {
            buffer[index++] = (byte)((value & 0x7F) | 0x80);
            value >>= 7;
            count++;
        } while (value != 0);
        buffer[index - 1] &= 0x7F;
        stream.Write(buffer, 0, count);
        return count;
    }
    public static bool TryDecodeUInt32(Stream source, out uint value)
    {
        int b = source.ReadByte();
        if (b < 0)
        {
            value = 0;
            return false;
        }

        if ((b & 0x80) == 0)
        {
            // single-byte
            value = (uint)b;
            return true;
        }

        int shift = 7;

        value = (uint)(b & 0x7F);
        bool keepGoing;
        int i = 0;
        do
        {
            b = source.ReadByte();
            if (b < 0) throw new EndOfStreamException();
            i++;
            keepGoing = (b & 0x80) != 0;
            value |= ((uint)(b & 0x7F)) << shift;
            shift += 7;
        } while (keepGoing && i < 4);
        if (keepGoing && i == 4)
        {
            throw new OverflowException();
        }
        return true;
    }
}

- Marc Gravell

@marc “大部分连续”可以理解为连续程度达到 51％，这种情况下位图非常适合... :p - Sam Saffron

5

TurboPFor：最快的整数压缩

C/C++及Java关键原生代码/JNI接口
SIMD加速整数压缩
针对有序/无序整数列表的标量+集成(SIMD)差分/脊编码/解码
全范围8/16/32/64位整数列表
直接访问
基准测试应用程序

- powturbo

这是最好的整数压缩。 - Kai Wang

3

除了其他解决方案之外：

您可以找到“密集”区域并使用位图来存储它们。

例如：

如果您在1000-3000之间有400个范围中的1000个数字，则可以使用单个位表示数字的存在，并使用两个int表示范围。该范围的总存储空间为2000位+ 2个int，因此您可以将该信息存储在254字节中，这非常棒，因为即使短整数每个都需要占用两个字节，所以对于此示例，您可以获得7倍的节省。

密集区域越多，此算法的效果就越好，但是在某些时候，仅存储起始和结束将更加便宜。

- Sam Saffron

如果它们“大多连续”，那么起始/结束（或类似）可能从一开始就是最佳选择；位图对于更随机的数据块非常适用。 - Marc Gravell

我同意，在这里编写最优算法的唯一方法是拥有一些样本数据。 - Sam Saffron

完全同意需要示例数据...但是既然我们已经迟到了6个月，我不抱太大希望 ;-p - Marc Gravell

3

我知道这是一个旧的消息线程，但是我在此处找到了SKIP/TAKE理念，并包含了我的个人PHP测试。我将其称为STEP (+)/SPAN(-)。也许有人会发现它有用。

注意：尽管原问题涉及正数且不重复的整数，但我实现了允许重复整数以及负整数的功能。如果您想尝试删除一两个字节，请随意调整它。

代码：

  // $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>';

输出：

--------------------------------------------------------------------------------
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
--------------------------------------------------------------------------------

- Deen Foxx

侧记...如果您不想要重复项，请在压缩循环中将“if ($step >= 0)”更改为“if ($step > 0)”。此外，如果客户端可能会操纵数据，请在解压缩部分的“array_push($uncompressed_array, $current_value)”中添加“if ($val)”以防止重复项。我正在使用它通过 cookie 将本地客户端 DB ID 的“快照”发送到服务器，以与服务器的 DB 进行比较，以便服务器可以在初始页面加载时发送插入、更新或删除以进行同步（而不需要 AJAX）... 在这种情况下，重复的 ID 和负数都是不受欢迎的。 - Deen Foxx

3

压缩字符串 "1-100, 110-160" 或将字符串存储为二进制表示形式并解析以恢复数组。

- Ray Tayek

3

我会结合CesarB和Fernando Miguélez的答案。

首先，存储每个值与前一个值之间的差异。正如CesarB所指出的那样，这将为您提供大多数为1的序列。

然后，对此序列使用Run Length Encoding压缩算法。由于重复值的数量很大，它将被压缩得非常好。

- Michael Dorfman

1

然后在其上应用另一层压缩，以获得更大的收益。（如果您在之前的步骤中有一个二进制表示“100:1;1:10;50:1”，则另一种压缩方法可以处理剩余的冗余部分。） - CesarB

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel Lemire · Accepted Answer

我们撰写了最近的研究论文，针对此问题调查了最佳方案。请参见以下内容：

Daniel Lemire和Leonid Boytsov，《Decoding billions of integers per second through vectorization》,Software: Practice & Experience 45 (1), 2015. http://arxiv.org/abs/1209.2137 Daniel Lemire、Nathan Kurz和Leonid Boytsov，《SIMD Compression and the Intersection of Sorted Integers》, Software：Practice and Experience (即将发表) 。http://arxiv.org/abs/1401.6399 它们包括广泛的实验评估。

您可以在线找到C++11中所有技术的完整实现：https://github.com/lemire/FastPFor 和 https://github.com/lemire/SIMDCompressionAndIntersection 还有C库：https://github.com/lemire/simdcomp 和 https://github.com/lemire/MaskedVByte 如果您喜欢Java，请参见https://github.com/lemire/JavaFastPFOR。