整数序列的最佳压缩算法

我有一个大数组,其中包含大多数连续的整数,例如1-100,110-160等.所有整数都是正数.压缩它的最佳算法是什么？

我尝试了deflate算法,但这只给我50%的压缩.请注意,算法不能有损.

所有数字都是独一无二的并逐渐增加.

另外,如果你能指出我的这种算法的java实现会很棒.

1> Daniel Lemir..：

---

我们写了最近的研究论文,调查了这个问题的最佳方案.请参阅:

Daniel Lemire和Leonid Boytsov,通过矢量化解码每秒数十亿的整数,软件:实践和经验45(1),2015.http ://arxiv.org/abs/1209.2137

Daniel Lemire,Nathan Kurz,Leonid Boytsov,SIMD压缩和排序整数的交集,软件:实践和经验(出现)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

---

详细说明@DanielLemire的评论:每个无损压缩都可以生成一个可以解码为原始流的流,但_no无损方法_将长度为_l_的任何(子)字符串编码为更短的内容,可以避免为至少一个字符串生成更长的内容长度_l_.

---

@ChrisMarisic无论你如何尝试,都无法可靠地压缩随机位流.

2> CesarB..：

---

首先,通过获取每个值与前一个值之间的差值来预处理您的值列表(对于第一个值,假设前一个值为零).在您的情况下,这应该主要提供一系列的,可以通过大多数压缩算法更容易地压缩.

这就是PNG格式如何改进其压缩(它采用了几种差异方法之一,后跟gzip使用的相同压缩算法).

3> Tamir..：

---

好吧,我投票支持更聪明的方式.所有你必须存储的是[int:startnumber] [int/byte/whatever:迭代次数]在这种情况下,你将把你的示例数组转换为4xInt值.在它之后你可以按你想要压缩:)

---

...并且不存储起始编号,而是存储最后一个整数之后的差异.

4> brianegge..：

---

虽然您可以设计特定于您的数据流的自定义算法,但使用现成的编码算法可能更容易.我运行了一些Java中可用的压缩算法测试,并发现了一百万个连续整数序列的以下压缩率:

None        1.0
Deflate     0.50
Filtered    0.34
BZip2       0.11
Lzma        0.06

5> Marc Gravell..：

---

数字的大小是多少？除了其他答案之外,您还可以考虑base-128变长编码,它允许您在单个字节中存储较小的数字,同时仍然允许更大的数字.MSB表示"还有另一个字节" - 这里描述.

将此与其他技术相结合,以便存储"跳过大小","占用大小","跳过大小","占用大小" - 但注意"跳过"或"接受"都不会为零,所以我们将从每个中减去一个(这可以为少量值保存一个额外的字节)

所以:

1-100, 110-160

是"跳过1"(假设从零开始,因为它使事情变得更容易),"取100","跳过9","取51"; 从每个中减去1,给出(以小数表示)

0,99,8,50

编码为(hex):

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

因此,我们可以轻松地对大数字进行编码,但是较小的数字(对于skip/take来说是典型的声音)占用的空间更少

你可以尝试通过"deflate"来运行它,但它可能没有多大帮助......

---

如果你不想处理所有那些混乱的编码cruff你自己...如果你可以创建值的整数数组(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();
        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();
        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;
    }
}