blocks|key|2024285|text|我们最近写了一些研究论文，调查了解决这个问题的最佳方案。请参阅：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2024286|Daniel+Lemire和Leonid+Boytsov，通过矢量化每秒解码数十亿个整数，软件:实践和经验45+(1)，2015。http://arxiv.org/abs/1209.2137|offset|length|2024287|Daniel+Lemire，Nathan+Kurz，Leonid+Boytsov，SIMD压缩和排序整数的交集，软件:实践和经验(即将出现)+http://arxiv.org/abs/1401.6399|2024288|它们包括广泛的实验评估。|2024289|您可以在C%2B%2B11+online中找到所有技术的完整实现：https://github.com/lemire/FastPFor和https://github.com/lemire/SIMDCompressionAndIntersection|2024290|还有一些C库：https://github.com/lemire/simdcomp和https://github.com/lemire/MaskedVByte|2024291|如果您更喜欢Java，请参阅https://github.com/lemire/JavaFastPFOR|2024292|entityMap|0|LINK|mutability|MUTABLE|url|http://arxiv.org/abs/1209.2137|1|http://arxiv.org/abs/1401.6399|2|https://github.com/lemire/FastPFor|3|https://github.com/lemire/SIMDCompressionAndIntersection|4|https://github.com/lemire/simdcomp|5|https://github.com/lemire/MaskedVByte|6|https://github.com/lemire/JavaFastPFOR^0|0|1T|U|0|0|1Z|U|1|0|0|T|Y|2|1S|1K|3|0|7|Y|4|16|11|5|0|E|12|6|0^^$0|@$1|2|3|4|5|6|7|19|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1A|8|@]|9|@$D|1B|E|1C|1|1D]]|A|$]]|$1|F|3|G|5|6|7|1E|8|@]|9|@$D|1F|E|1G|1|1H]]|A|$]]|$1|H|3|I|5|6|7|1I|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|1J|8|@]|9|@$D|1K|E|1L|1|1M]|$D|1N|E|1O|1|1P]]|A|$]]|$1|L|3|M|5|6|7|1Q|8|@]|9|@$D|1R|E|1S|1|1T]|$D|1U|E|1V|1|1W]]|A|$]]|$1|N|3|O|5|6|7|1X|8|@]|9|@$D|1Y|E|1Z|1|20]]|A|$]]|$1|P|3|-4|5|6|7|21|8|@]|9|@]|A|$]]]|Q|$R|$5|S|T|U|A|$V|W]]|X|$5|S|T|U|A|$V|Y]]|Z|$5|S|T|U|A|$V|10]]|11|$5|S|T|U|A|$V|12]]|13|$5|S|T|U|A|$V|14]]|15|$5|S|T|U|A|$V|16]]|17|$5|S|T|U|A|$V|18]]]]

We have written recent research papers that survey the best schemes for this problem. Please see:

Daniel Lemire and Leonid Boytsov, Decoding billions of integers per second through vectorization,Software: Practice &amp; Experience 45 (1), 2015. 
<a href="http://arxiv.org/abs/1209.2137">http://arxiv.org/abs/1209.2137</a>

Daniel Lemire, Nathan Kurz, Leonid Boytsov, SIMD Compression and the Intersection of Sorted Integers, Software: Practice and Experience (to appear) <a href="http://arxiv.org/abs/1401.6399">http://arxiv.org/abs/1401.6399</a>

They include an extensive experimental evaluation.

You can find a complete implementation of all techniques in C++11 online:
<a href="https://github.com/lemire/FastPFor">https://github.com/lemire/FastPFor</a> and <a href="https://github.com/lemire/SIMDCompressionAndIntersection">https://github.com/lemire/SIMDCompressionAndIntersection</a>

There are also C libraries: <a href="https://github.com/lemire/simdcomp">https://github.com/lemire/simdcomp</a> and <a href="https://github.com/lemire/MaskedVByte">https://github.com/lemire/MaskedVByte</a>

If you prefer Java, please see <a href="https://github.com/lemire/JavaFastPFOR">https://github.com/lemire/JavaFastPFOR</a>

blocks|key|4134024|text|首先，通过获取每个值与前一个值之间的差值来预处理您的值列表(对于第一个值，假设前一个值为零)。在您的情况下，这应该主要提供一个1序列，大多数压缩算法可以更容易地压缩这些序列。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4134025|这就是PNG格式改进其压缩的方法(它采用几种不同的方法之一，然后使用与gzip相同的压缩算法)。|4134026|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

First, preprocess your list of values by taking the difference between each value and the previous one (for the first value, assume the previous one was zero). This should in your case give mostly a sequence of ones, which can be compressed much more easily by most compression algorithms.

This is how the PNG format does to improve its compression (it does one of several difference methods followed by the same compression algorithm used by gzip).

blocks|key|1628701|text|好吧，我投票给更聪明的方式。您需要存储的所有内容是int:startnumber在本例中，您将把示例数组转换为4xInt值。在此之后，您可以根据需要进行压缩:)|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1628702|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

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

blocks|key|4134114|text|虽然您可以设计特定于您的数据流的自定义算法，但使用现成的编码算法可能更容易。我运行了几个tests+of+compression+algorithms+available+in+Java，发现一百万个连续整数序列的压缩率如下：|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|4134115|None++++++++1.0
Deflate+++++0.50
Filtered++++0.34
BZip2+++++++0.11
Lzma++++++++0.06|code-block|syntax|javascript|4134116|entityMap|0|LINK|mutability|MUTABLE|url|http://www.theeggeadventure.com/wikimedia/index.php/Java_Data_Compression^0|18|1D|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@$A|R|B|S|1|T]]|C|$]]|$1|D|3|E|5|F|7|U|8|@]|9|@]|C|$G|H]]|$1|I|3|-4|5|6|7|V|8|@]|9|@]|C|$]]]|J|$K|$5|L|M|N|C|$O|P]]]]

While you could design a custom algorithm specific to your stream of data, it's probably easier to use an off the shelf encoding algorithm. I ran a few <a href="http://www.theeggeadventure.com/wikimedia/index.php/Java_Data_Compression" rel="noreferrer">tests of compression algorithms available in Java</a> and found the following compression rates for a sequence of one million consecutive integers:

<pre><code>None 1.0
Deflate 0.50
Filtered 0.34
BZip2 0.11
Lzma 0.06
</code></pre>

blocks|key|1628786|text|这些数字有多大？除了其他答案之外，您还可以考虑base-128可变长度编码，它允许您以单个字节存储较小的数字，同时仍然允许使用较大的数字。MSB的意思是“还有另一个字节”--这里是described。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1628787|将它与其他技术结合起来，这样你就可以存储“跳过大小”、“采取大小”、“跳过大小”、“采取大小”--但请注意，“跳过”和“采取”都不会是零，所以我们将从每种技术中减去一个(这允许你为少数几个值保存一个额外的字节)|1628788|所以：|1628789|1-100,+110-160|code-block|syntax|javascript|1628790|是“跳过1”(假设从零开始，因为它使事情变得更容易)，“跳过100"，”跳过9"，“跳过51"；从每个减去1，给(作为小数)|1628791|0,99,8,50|1628792|它编码为(十六进制)：|1628793|00+63+08+32|1628794|如果我们想跳过/取一个更大的数字-+300，例如；我们减去1得到299+-但这超过了7位；从小端开始，我们编码7位的块和一个MSB来表示继续：|1628795|299+=+100101100+=+(in+blocks+of+7):+0000010+0101100|1628796|所以从最小的部分开始：|1628797|1+0101100+(leading+one+since+continuation)
0+0000010+(leading+zero+as+no+more)|1628798|给予：|1628799|AC+02|1628800|因此我们可以很容易地对大数字进行编码，但是小数字(听起来是典型的跳过/跳过)占用的空间更少。|1628801|你可以通过“”来尝试，但它可能不会有更多的帮助……|style|BOLD|1628802|1628803|如果你不想自己处理那些乱七八糟的代码...如果您可以创建值的整数数组(0,99,8,60)+-您可以使用protocol+buffers+with+a+packed+repeated+uint32/uint64+-它将为您完成所有工作;-p|1628804|我不“使用”Java，但这里有一个完整的C#实现(借用了我的protobuf-net项目中的一些编码比特)：|1628805|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%2B%2B)
++++++++{
++++++++++++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+%2B=+(int)skip%2B1;
++++++++++++for(uint+i+=+0+;+i+<=+take+;+i%2B%2B)+{
++++++++++++++++list.Add(last%2B%2B);
++++++++++++}
++++++++}
++++++++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+(%2B%2Bi+<+data.Length+&&+data[i]+==+data[i+-+1]+%2B+1)+size%2B%2B;
++++++++++++last+=+data[i+-+1];
++++++++++++len+%2B=+EncodeUInt32((uint)gap,+buffer,+stream)
++++++++++++++++%2B+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%2B%2B]+=+(byte)((value+&+0x7F)+%7C+0x80);
++++++++++++value+>>=+7;
++++++++++++count%2B%2B;
++++++++}+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%2B%2B;
++++++++++++keepGoing+=+(b+&+0x80)+!=+0;
++++++++++++value+%7C=+((uint)(b+&+0x7F))+<<+shift;
++++++++++++shift+%2B=+7;
++++++++}+while+(keepGoing+&&+i+<+4);
++++++++if+(keepGoing+&&+i+==+4)
++++++++{
++++++++++++throw+new+OverflowException();
++++++++}
++++++++return+true;
++++}
}|1628806|entityMap|0|LINK|mutability|MUTABLE|url|http://code.google.com/apis/protocolbuffers/docs/encoding.html#varints|1|http://code.google.com/apis/protocolbuffers/docs/proto.html|2|http://code.google.com/p/protobuf-net/^0|2I|9|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|6|4|0|0|1G|1H|1|0|U|C|2|0|0^^$0|@$1|2|3|4|5|6|7|1V|8|@]|9|@$A|1W|B|1X|1|1Y]]|C|$]]|$1|D|3|E|5|6|7|1Z|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|20|8|@]|9|@]|C|$]]|$1|H|3|I|5|J|7|21|8|@]|9|@]|C|$K|L]]|$1|M|3|N|5|6|7|22|8|@]|9|@]|C|$]]|$1|O|3|P|5|J|7|23|8|@]|9|@]|C|$K|L]]|$1|Q|3|R|5|6|7|24|8|@]|9|@]|C|$]]|$1|S|3|T|5|J|7|25|8|@]|9|@]|C|$K|L]]|$1|U|3|V|5|6|7|26|8|@]|9|@]|C|$]]|$1|W|3|X|5|J|7|27|8|@]|9|@]|C|$K|L]]|$1|Y|3|Z|5|6|7|28|8|@]|9|@]|C|$]]|$1|10|3|11|5|J|7|29|8|@]|9|@]|C|$K|L]]|$1|12|3|13|5|6|7|2A|8|@]|9|@]|C|$]]|$1|14|3|15|5|J|7|2B|8|@]|9|@]|C|$K|L]]|$1|16|3|17|5|6|7|2C|8|@]|9|@]|C|$]]|$1|18|3|19|5|6|7|2D|8|@$A|2E|B|2F|1A|1B]]|9|@]|C|$]]|$1|1C|3|-4|5|6|7|2G|8|@]|9|@]|C|$]]|$1|1D|3|1E|5|6|7|2H|8|@]|9|@$A|2I|B|2J|1|2K]]|C|$]]|$1|1F|3|1G|5|6|7|2L|8|@]|9|@$A|2M|B|2N|1|2O]]|C|$]]|$1|1H|3|1I|5|J|7|2P|8|@]|9|@]|C|$K|L]]|$1|1J|3|-4|5|6|7|2Q|8|@]|9|@]|C|$]]]|1K|$1L|$5|1M|1N|1O|C|$1P|1Q]]|1R|$5|1M|1N|1O|C|$1P|1S]]|1T|$5|1M|1N|1O|C|$1P|1U]]]]

What size are the numbers? In addition to the other answers, you could consider base-128 variant-length encoding, which lets you store smaller numbers in single bytes while still allowing larger numbers. The MSB means "there is another byte" - this is <a href="http://code.google.com/apis/protocolbuffers/docs/encoding.html#varints" rel="noreferrer">described</a> here.

Combine this with the other techniques so you are storing "skip size", "take size", "skip size", "take size" - but noting that neither "skip" nor "take" will ever be zero, so we'll subtract one from each (which lets you save an extra byte for a handful of values)

So:

<pre><code>1-100, 110-160
</code></pre>

is "skip 1" (assume start at zero as it makes things easier), "take 100", "skip 9", "take 51"; subtract 1 from each, giving (as decimals)

<pre><code>0,99,8,50
</code></pre>

which encodes as (hex):

<pre><code>00 63 08 32
</code></pre>

If we wanted to skip/take a larger number - 300, for example; we subtract 1 giving 299 - but that goes over 7 bits; starting with the little end, we encode blocks of 7 bits and an MSB to indicate continuation:

<pre><code>299 = 100101100 = (in blocks of 7): 0000010 0101100
</code></pre>

so starting with the little end:

<pre><code>1 0101100 (leading one since continuation)
0 0000010 (leading zero as no more)
</code></pre>

giving:

<pre><code>AC 02
</code></pre>

So we can encode large numbers easily, but small numbers (which sound typical for skip/take) take less space.

You could try running this through "deflate", but it might not help much more...

<hr>

If you don't want to deal with all that messy encoding cruff yourself... if you can create the integer-array of the values (0,99,8,60) - you could use <a href="http://code.google.com/apis/protocolbuffers/docs/proto.html" rel="noreferrer">protocol buffers with a packed repeated uint32/uint64</a> - and it'll do all the work for you ;-p

I don't "do" Java, but here's a full C# implementation (borrowing some of the encoding bits from my <a href="http://code.google.com/p/protobuf-net/" rel="noreferrer">protobuf-net</a> project):

<pre><code>using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
static class Program
{
 static void Main()
 {
 var data = new List&lt;int&gt;();
 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 &lt; len; i++)
 {
 Console.Write(buffer[i].ToString("X2"));
 }
 Console.WriteLine();
 }
 static int[] Decode(Stream stream)
 {
 var list = new List&lt;int&gt;();
 uint skip, take;
 int last = 0;
 while (TryDecodeUInt32(stream, out skip)
 &amp;&amp; TryDecodeUInt32(stream, out take))
 {
 last += (int)skip+1;
 for(uint i = 0 ; i &lt;= 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 &lt; data.Length; )
 {
 int gap = data[i] - 2 - last, size = 0;
 while (++i &lt; data.Length &amp;&amp; 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 &amp; 0x7F) | 0x80);
 value &gt;&gt;= 7;
 count++;
 } while (value != 0);
 buffer[index - 1] &amp;= 0x7F;
 stream.Write(buffer, 0, count);
 return count;
 }
 public static bool TryDecodeUInt32(Stream source, out uint value)
 {
 int b = source.ReadByte();
 if (b &lt; 0)
 {
 value = 0;
 return false;
 }

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

 int shift = 7;

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

blocks|key|5551934|text|TurboPFor:+Fastest+Integer+Compression|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|5551935|5551936|unordered-list-item|5551937|+C/C%2B%2B包括Java+Critical+Native/JNI接口|5551938|SIMD加速整数compression|5551939|Scalar+%2B集成(SIMD)已排序/未排序整数列表的差分/之字形编码/解码|5551940|全范围8/16/32/64位整数列表|5551941|直接Java应用程序|5551942|5551943|entityMap|0|LINK|mutability|MUTABLE|url|https://github.com/powturbo/TurboPFor^0|0|12|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Z|8|@]|9|@$A|10|B|11|1|12]]|C|$]]|$1|D|3|-4|5|6|7|13|8|@]|9|@]|C|$]]|$1|E|3|-4|5|F|7|14|8|@]|9|@]|C|$]]|$1|G|3|H|5|6|7|15|8|@]|9|@]|C|$]]|$1|I|3|J|5|F|7|16|8|@]|9|@]|C|$]]|$1|K|3|L|5|F|7|17|8|@]|9|@]|C|$]]|$1|M|3|N|5|F|7|18|8|@]|9|@]|C|$]]|$1|O|3|P|5|F|7|19|8|@]|9|@]|C|$]]|$1|Q|3|-4|5|6|7|1A|8|@]|9|@]|C|$]]|$1|R|3|-4|5|6|7|1B|8|@]|9|@]|C|$]]]|S|$T|$5|U|V|W|C|$X|Y]]]]

<a href="https://github.com/powturbo/TurboPFor" rel="noreferrer">TurboPFor: Fastest Integer Compression</a> 

<ul>
<li>for C/C++ including Java Critical Natives/JNI Interface</li>
<li>SIMD accelerated integer compression</li>
<li>Scalar + Integrated (SIMD) differential/Zigzag encoding/decoding for sorted/unsorted integer lists</li>
<li>Full range 8/16/32/64 bits interger lists</li>
<li>Direct access</li>
<li>Benchmark app</li>
</ul>

blocks|key|2023835|text|压缩字符串"1-100,110-160“或以某种二进制表示形式存储该字符串，并对其进行解析以恢复数组|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2023836|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

compress the string "1-100, 110-160" or store the string in some binary representation and parse it to restore the array

blocks|key|5551539|text|我结合了CesarB和Fernando+Miguélez给出的答案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|5551540|首先，存储每个值与前一个值之间的差异。正如CesarB所指出的，这将给你一个主要的序列。|5551541|然后，对此序列使用游程编码压缩算法。由于有大量的重复值，所以压缩效果会很好。|5551542|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

I'd combine the answers given by CesarB and Fernando Miguélez.

First, store the differences between each value and the previous one. As CesarB pointed out, this will give you a sequence of mostly ones.

Then, use a Run Length Encoding compression algorithm on this sequence. It will compress very nicely due to the large number of repeated values.

blocks|key|5551658|text|除了其他解决方案之外：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|5551659|您可以找到“密集”区域并使用位图来存储它们。|5551660|举个例子：|5551661|如果您有1000个介于1000-3000之间的400范围内的1000个数字，则可以使用一个位来表示一个数字的存在，并使用两个整数来表示该范围。这个范围的总存储是2000位%2B2个整数，所以你可以存储254字节的信息，这是非常棒的，因为即使是短的整数也会占用两个字节，所以在这个例子中，你可以节省7倍的成本。|5551662|区域越密集，这个算法就会做得越好，但在某些情况下，只存储开始和结束将会更便宜。|5551663|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|M|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|N|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|O|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|P|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|K|$]]

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.

blocks|key|2024023|text|我建议你看看Arithmetic+Coding的特例--+Huffman+Coding。在这两种情况下，您都可以分析您的起始序列，以确定不同值的相对频率。出现频率较高的值比出现频率较低的值使用更少的比特进行编码。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|2024024|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Arithmetic_coding|1|http://en.wikipedia.org/wiki/Huffman_coding^0|6|H|0|T|E|1|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]|$A|R|B|S|1|T]]|C|$]]|$1|D|3|-4|5|6|7|U|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]|L|$5|G|H|I|C|$J|M]]]]

I'd suggest taking a look at <a href="http://en.wikipedia.org/wiki/Huffman_coding" rel="nofollow noreferrer">Huffman Coding</a>, a special case of <a href="http://en.wikipedia.org/wiki/Arithmetic_coding" rel="nofollow noreferrer">Arithmetic Coding</a>. 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.

blocks|key|4134400|text|我知道这是一个旧的消息线程，但我正在包含我在这里找到的跳过/跳过的想法的个人PHP测试。我将我的步骤命名为(%2B)/SPAN(-)。也许有人会发现它有帮助。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4134401|注意:我实现了允许重复整数和负整数的能力，即使原始问题涉及正的、非重复的整数。如果您想尝试修剪一两个字节，请随意调整它。|4134402|代码：|4134403|++//+$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+:+'%2B'.$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,'%2B');++//+Don't+need+leading+'%2B'.
++echo+"<hr>\nOriginal+Array+has+"
++++.count($integers_array)
++++.'+elements:+{not+showing,+since+I+modified+the+original+array+directly}';
++echo+" \nCompressed+Array+has+"
++++.count($compressed_array).'+elements:+'
++++.implode(',+',$compressed_array);
++echo+" \nCompressed+String+has+"
++++.strlen($compressed_string).'+characters:+'
++++.$compressed_string;
++echo+" \nPacked+String+has+"
++++.strlen($packed_string).'+(some+probably+not+printable)+characters:+'
++++.$packed_string;
++echo+" \nBase64+String+has+"
++++.strlen($base64_string).'+(all+printable)+characters:+'
++++.$base64_string;
++echo+" \nGZipped+String+has+"
++++.strlen($gz_string).'+(some+probably+not+printable)+characters:+'
++++.$gz_string;
++echo+" \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+%2B+1,+$current_value+-+$val+-+1);
++++++$uncompressed_array+=+array_merge($uncompressed_array,+$range);
++++}
++++//+Add+the+step+value+to+the+$current_value
++++$current_value+%2B=+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>';|code-block|syntax|javascript|4134404|输出：|4134405|--------------------------------------------------------------------------------
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%2B4-1%2B6-1%2B3%2B2%2B2%2B0%2B8-1%2B2-1%2B13%2B3%2B6%2B2%2B6%2B0%2B3%2B2-1%2B8-11%2B5%2B12-1%2B3-1%2B0-1%2B3-1%2B2%2B7%2B6%2B5%2B7-1%2B0-1%2B7%2B4%2B3%2B2%2B3%2B2%2B2%2B2%2B3%2B8%2B0%2B4
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Š“%5EqçºR¬m&Òõ‹%25Ê&TFÊ‰ùÀ6ÿÁÁ+Æ
Base64+of+GZipped+String+has+72+(all+printable)+characters:+eJwNyrsNACAMA9HIzq%2BAKVmaRahNipNecee6UgSsBW0m0gj1iyXKJlRGjcqJ%2BcA2/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
--------------------------------------------------------------------------------|4134406|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|R|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|S|8|@]|9|@]|A|$]]|$1|F|3|G|5|H|7|T|8|@]|9|@]|A|$I|J]]|$1|K|3|L|5|6|7|U|8|@]|9|@]|A|$]]|$1|M|3|N|5|H|7|V|8|@]|9|@]|A|$I|J]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

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:

<pre class="lang-php prettyprint-override"><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 &gt; 0) array_push($compressed_array, -$span);
 // If $step is positive, move forward. If $step is zero, the number is duplicate.
 if ($step &gt;= 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 &lt; pow(2,7)) $pack_size = 'c';
 elseif ($largest_integer &lt; pow(2,15)) $pack_size = 's';
 elseif ($largest_integer &lt; pow(2,31)) $pack_size = 'l';
 elseif ($largest_integer &lt; 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 &lt; 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 "&lt;hr&gt;\nOriginal Array has "
 .count($integers_array)
 .' elements: {not showing, since I modified the original array directly}';
 echo "&lt;br&gt;\nCompressed Array has "
 .count($compressed_array).' elements: '
 .implode(', ',$compressed_array);
 echo "&lt;br&gt;\nCompressed String has "
 .strlen($compressed_string).' characters: '
 .$compressed_string;
 echo "&lt;br&gt;\nPacked String has "
 .strlen($packed_string).' (some probably not printable) characters: '
 .$packed_string;
 echo "&lt;br&gt;\nBase64 String has "
 .strlen($base64_string).' (all printable) characters: '
 .$base64_string;
 echo "&lt;br&gt;\nGZipped String has "
 .strlen($gz_string).' (some probably not printable) characters: '
 .$gz_string;
 echo "&lt;br&gt;\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 &lt; -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 "&lt;hr&gt;Reconstituted Array has "
 .count($uncompressed_array).' elements: '
 .implode(', ',$uncompressed_array).
 '&lt;hr&gt;';
</code></pre>

OUTPUT:

<pre><code>--------------------------------------------------------------------------------
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&amp;Òõ‹%Ê&amp;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
--------------------------------------------------------------------------------
</code></pre>

blocks|key|4134240|text|您可能应该使用的基本思想是，对于每个连续整数范围(我将这些范围称为这些范围)，存储范围的起始数字和大小。例如，如果您有一个包含1000个整数的列表，但只有10个单独的范围，那么您只能存储20个整数(1个起始号，每个范围1个大小)来表示此数据，这将是98%25的压缩率。幸运的是，您可以进行一些更多的优化，这将有助于处理范围数量较大的情况。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4134241|4134242|Store起始编号相对于上一个起始编号的偏移量，而不是起始编号本身。这里的优点是，您存储的数字通常需要更少的位(这在以后的优化建议中可能会派上用场)。此外，如果只存储起始数字，则这些数字都将是唯一的，而存储偏移量可能会使这些数字接近甚至重复，这可能会允许使用之后应用的另一种方法进一步压缩。|ordered-list-item|offset|length|style|BOLD|4134243|对这两种类型的整数都使用最小位数。您可以遍历这些数字，以获得起始整数的最大偏移量以及最大范围的大小。然后，您可以使用最有效地存储这些整数的数据类型，并只需在压缩数据的开头指定数据类型或位数。例如，如果起始整数的最大偏移量仅为12,000，而最大范围为9,000，则可以对所有这些都使用2字节的无符号整数。然后，您可以在压缩数据的开头填充对2,2，以显示两个整数都使用了2个字节。当然，您可以使用一些位操作将此信息放入单个字节中。如果您习惯于进行大量的位操作，则可以将每个数字存储为可能的最小位数，而不是符合1、2、4或8字节的representations.|4134244|4134245|有了这两个优化，让我们看几个示例(每个示例都是4000字节)：|4134246|4134247|1,000个整数，最大偏移量为500，10个范围|4134248|1,000个整数，最大偏移量为100，50个范围|4134249|1,000个整数，最大偏移量为50,100个范围|4134250|4134251|没有优化的|4134252|4134253|20个整数，每个4字节=+80字节。压缩=+98%25|4134254|100整数，每个4字节=+400字节。压缩=+90%25|4134255|200整数，每个4字节=+800字节。压缩=+80%25|4134256|4134257|具有优化功能的|4134258|4134259|1字节头%2B+20个数字，每个1字节=+21个字节。压缩=+99.475%25|4134260|1字节头%2B+100个数字，每个1字节=+101个字节。压缩=+97.475%25|4134261|1字节头%2B+200个数字，每个1字节=+201字节。压缩=+94.975%25|4134262|4134263|entityMap^0|0|0|0|N|0|C|4|0|0|0|0|0|0|0|0|0|0|M|3|0|N|3|0|N|3|0|0|0|0|T|7|0|V|7|0|U|7|0|0^^$0|@$1|2|3|4|5|6|7|1I|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|1J|8|@]|9|@]|A|$]]|$1|C|3|D|5|E|7|1K|8|@$F|1L|G|1M|H|I]]|9|@]|A|$]]|$1|J|3|K|5|E|7|1N|8|@$F|1O|G|1P|H|I]]|9|@]|A|$]]|$1|L|3|-4|5|6|7|1Q|8|@]|9|@]|A|$]]|$1|M|3|N|5|6|7|1R|8|@]|9|@]|A|$]]|$1|O|3|-4|5|6|7|1S|8|@]|9|@]|A|$]]|$1|P|3|Q|5|E|7|1T|8|@]|9|@]|A|$]]|$1|R|3|S|5|E|7|1U|8|@]|9|@]|A|$]]|$1|T|3|U|5|E|7|1V|8|@]|9|@]|A|$]]|$1|V|3|-4|5|6|7|1W|8|@]|9|@]|A|$]]|$1|W|3|X|5|6|7|1X|8|@]|9|@]|A|$]]|$1|Y|3|-4|5|6|7|1Y|8|@]|9|@]|A|$]]|$1|Z|3|10|5|E|7|1Z|8|@$F|20|G|21|H|I]]|9|@]|A|$]]|$1|11|3|12|5|E|7|22|8|@$F|23|G|24|H|I]]|9|@]|A|$]]|$1|13|3|14|5|E|7|25|8|@$F|26|G|27|H|I]]|9|@]|A|$]]|$1|15|3|-4|5|6|7|28|8|@]|9|@]|A|$]]|$1|16|3|17|5|6|7|29|8|@]|9|@]|A|$]]|$1|18|3|-4|5|6|7|2A|8|@]|9|@]|A|$]]|$1|19|3|1A|5|E|7|2B|8|@$F|2C|G|2D|H|I]]|9|@]|A|$]]|$1|1B|3|1C|5|E|7|2E|8|@$F|2F|G|2G|H|I]]|9|@]|A|$]]|$1|1D|3|1E|5|E|7|2H|8|@$F|2I|G|2J|H|I]]|9|@]|A|$]]|$1|1F|3|-4|5|6|7|2K|8|@]|9|@]|A|$]]|$1|1G|3|-4|5|6|7|2L|8|@]|9|@]|A|$]]]|1H|$]]

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.

<ol>
<li>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.</li>
<li>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.</li>
</ol>

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

<ol>
<li>1,000 integers, biggest offset is 500, 10 ranges</li>
<li>1,000 integers, biggest offset is 100, 50 ranges</li>
<li>1,000 integers, biggest offset is 50, 100 ranges</li>
</ol>

WITHOUT OPTIMIZATIONS

<ol>
<li>20 integers, 4 bytes each = 80 bytes. COMPRESSION = 98%</li>
<li>100 integers, 4 bytes each = 400 bytes. COMPRESSION = 90%</li>
<li>200 integers, 4 bytes each = 800 bytes. COMPRESSION = 80%</li>
</ol>

WITH OPTIMIZATIONS

<ol>
<li>1 byte header + 20 numbers, 1 byte each = 21 bytes. COMPRESSION = 99.475%</li>
<li>1 byte header + 100 numbers, 1 byte each = 101 bytes. COMPRESSION = 97.475%</li>
<li>1 byte header + 200 numbers, 1 byte each = 201 bytes. COMPRESSION = 94.975%</li>
</ol>

blocks|key|4134284|text|您的情况非常类似于搜索引擎中的索引压缩。常用的压缩算法是PForDelta算法和Simple16算法。您可以使用kamikaze库来满足您的压缩需求。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4134285|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Your case is very similar to compression of indices in search engines. The popular compression algorithm used is the PForDelta algorithm and Simple16 algorithm. You can use the kamikaze library for your compression needs.

blocks|key|1629010|text|对于这一点，我不能让我的压缩比.11更好。我通过python解释器生成了我的测试数据，它是一个以换行符分隔的1-100和110-160整数列表。我使用实际的程序作为数据的压缩表示。我的压缩文件如下：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1629011|main=mapM_+print+[x%7Cx<-[1..160],x`notElem`[101..109]]|code-block|syntax|javascript|1629012|这只是一个生成文件的Haskell脚本，您可以通过以下方式运行：|1629013|$+runhaskell+generator.hs+>>+data|1629014|g.hs文件的大小是54字节，python生成的数据是496字节。这提供了0.10887096774193548的压缩比。我认为有更多的时间可以缩小程序，或者你可以压缩压缩文件(即haskell文件)。|1629015|另一种方法可以是保存4字节的数据。每个序列的最小和最大值，然后将其赋予生成函数。尽管如此，文件的加载会给解压缩器增加更多的字符，给解压缩器增加更多的复杂性和更多的字节。同样，我通过程序表示了这个非常特定的序列，它不是泛化的，它是特定于数据的压缩。此外，添加通用性会使解压缩器变得更大。|1629016|另一个问题是，必须有Haskell解释器才能运行它。当我编译这个程序时，它使它变得更大。我真的不知道为什么。python也有同样的问题，所以也许最好的方法是给出范围，这样某个程序就可以解压缩文件。|1629017|entityMap^0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|U|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|V|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|W|8|@]|9|@]|A|$]]|$1|M|3|N|5|6|7|X|8|@]|9|@]|A|$]]|$1|O|3|P|5|6|7|Y|8|@]|9|@]|A|$]]|$1|Q|3|-4|5|6|7|Z|8|@]|9|@]|A|$]]]|R|$]]

I couldn't get my compression to be much better than about .11 for this. I generated my test data via python interpreter and it's a newline delimited list of integers from 1-100, and 110-160. I use the actual program as a compressed representation of the data. My compressed file is as follows:

<pre><code>main=mapM_ print [x|x&lt;-[1..160],x`notElem`[101..109]]
</code></pre>

It's just a Haskell script that generates the the file you can run via:

<pre><code>$ runhaskell generator.hs &gt;&gt; data
</code></pre>

The size of the g.hs file is 54 bytes, and the python generated data is 496 bytes. This gives 0.10887096774193548 as the compression ratio. I think with more time one could shrink the program, or you could compress the compressed file (i.e. the haskell file).

One other approach might be to save 4 bytes of data. The min and max of each sequence, then give those to a generating function. Albeit, the loading of files will add more characters to the decompresser adding more complexity and more bytes to the decompresser. Again, I represented this very specific sequence via a program and it doesn't generalize, it's a compression that's specific to the data. Furthermore, adding generality makes the decompresser larger.

Another concern is that one must have the Haskell interpreter to run this. When I compiled the program it made it much larger. I don't really know why. There is the same problem with python, so maybe the best approach is to give the ranges, so that a some program could decompress the file.

blocks|key|2023785|text|如果你有一系列重复的值，RLE是最容易实现的，并且可以给你一个好的结果。然而，考虑到熵的其他更先进的算法，如LZW，现在是无专利的，通常可以实现更好的压缩。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2023786|你可以看看这些和其他无损算法here。|offset|length|2023787|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Lossless_data_compression^0|0|E|4|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@$D|P|E|Q|1|R]]|A|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|M]]]]

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 <a href="http://en.wikipedia.org/wiki/Lossless_data_compression" rel="nofollow noreferrer">here</a>.

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.

Best Compression algorithm for a sequence of integers

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我有一个很大的数组，它的整数范围大部分是连续的，例如1-100,110-160等，所有的整数都是正数。最好的压缩算法是什么？我尝试了deflate算法，但它只提供了50%的压缩。请注意，算法不能是有损的。所有的数字都是唯一的，并且逐渐递增。另外，如果你能告诉我这种算法的java实现，那就太好了。

问整数序列的最佳压缩算法
EN

回答 15

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问整数序列的最佳压缩算法EN

回答 15

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问整数序列的最佳压缩算法
EN