整数序列的最佳压缩算法

小开

如果你有一系列重复的值，RLE 是最容易实现的，可以给你一个很好的结果。然而，其他更先进的算法，如 LZW，考虑到熵，现在是免费的专利，通常可以实现更好的压缩。

您可以看看这些算法和其他无损算法给你。

小开

压缩字符串“1-100,110-160”或以某种二进制表示形式存储字符串，并对其进行解析以恢复数组

小开

我要投给更聪明的人。在这种情况下，只需要存储[ int: startnumber ][ int/byte/whatever: number of iterations ] ，就可以将示例数组转换为4xInt 值。之后，你可以按照自己的意愿进行压缩:)

小开

首先，通过获取每个值与前一个值之间的差值来预处理您的值列表(对于第一个值，假设前一个值为零)。在您的情况下，这应该给出一个序列，它可以被大多数压缩算法更容易地压缩。

这就是 PNG 格式如何改进其压缩性能的(它使用几种不同的方法之一，然后使用与 gzip 相同的压缩算法)。

小开

我会把 CesarB 和 Fernando Miguelez 的答案结合起来。

首先，存储每个值与前一个值之间的差异。正如 CesarB 指出的，这会给你一个大多数情况下的序列。

然后，对这个序列使用一个运行长度编码压缩算法。由于大量的重复值，它将被很好地压缩。

小开

我建议看看霍夫曼编码，一种特殊的算术编码。在这两种情况下，你分析你的起始序列，以确定不同值的相对频率。出现频率较高的值比出现频率较低的值用更少的位进行编码。

小开

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

None        1.0
Deflate     0.50
Filtered    0.34
BZip2       0.11
Lzma        0.06

小开

号码是多少？除了其他答案之外，您还可以考虑 base-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

因此，我们可以很容易地编码大数字，但是小数字(听起来像是跳过/提取的典型代码)占用的空间更少。

你可以通过“放气”运行 试试看，但它可能不会帮助更多..。

如果你不想自己处理那些乱七八糟的编码问题... ... 如果你可以创建值的整数数组(0,99,8,60)-你可以使用重复打包的 uint32/uint64协议缓冲-它会为你做所有的工作;-p

我不“做”Java，但这里有一个完整的 C # 实现(从我的原始病毒网络项目中借用了一些编码部分) :

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

小开

除其他解决办法外:

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

例如:

如果在1000-3000之间的400个范围内有1000个数字，那么可以使用一个位来表示一个数字的存在，使用两个 int 来表示范围。这个范围的总存储空间是2000位 + 2 int，所以你可以用254字节来存储信息，这非常棒，因为即使是短整数也会占用两个字节，所以在这个例子中你可以节省7X。

面积越密集，这个算法的效果就越好，但是在某种程度上，仅仅存储开始和结束就会更便宜。

小开

您可能应该使用的基本思想是，对于每个连续整数范围(我称之为范围) ，存储起始数字和范围的大小。例如，如果你有一个1000个整数的列表，但是只有10个独立的范围，你只能存储20个整数(每个范围1个起始数和1个大小)来表示这个数据，压缩率为98% 。幸运的是，您可以进行一些更多的优化，这些优化将有助于处理范围较大的情况。

存储起始数字相对于前一个起始数字的偏移量 ，而不是起始数字本身。这里的优点是您存储的数字通常需要更少的位(这可能会在以后的优化建议中派上用场)。另外，如果只存储起始数字，那么这些数字都是唯一的，而存储偏移量时，这些数字有可能是接近的，甚至是重复的，这可能允许进一步压缩，之后再应用另一个方法。
对这两种类型的整数使用 可能的最小位数。可以迭代这些数字以获得起始整数的最大偏移量以及最大范围的大小。然后，您可以使用最有效地存储这些整数的数据类型，并在压缩数据的开始指定数据类型或位数。例如，如果一个起始整数的最大偏移量仅为12,000，而最大范围为9,000，那么可以对所有这些整数使用2字节无符号整数。然后，您可以在压缩数据的开始填充对2,2，以显示两个整数都使用了2个字节。当然，您可以使用一点点位操作将这些信息放入单个字节中。如果你习惯于进行大量的位操作，你可以将每个数字存储为尽可能少的位，而不是遵循1、2、4或8字节的表示。

通过这两个优化，让我们看一些示例(每个示例为4,000字节) :

1000个整数，最大偏移量是500,10个范围
1000个整数，最大偏移量是100,50个范围
1000个整数，最大偏移量是50100个范围

没有最优化

20个整数，每个4字节 = 80字节
100个整数，每个4字节 = 400字节
200个整数，每个4字节 = 800字节

最优化

1字节头 + 20个数字，每个1字节 = 21字节
1字节头 + 100个数字，每个1字节 = 101字节
1字节头 + 200个数字，每个1字节 = 201字节

小开

您的情况非常类似于搜索引擎中的索引压缩。流行的压缩算法是 PForDelta 算法和 Simple16算法。您可以使用神风特攻队库来满足您的压缩需求。

小开

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

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

小开

我知道这是一个老的消息线程，但我包括我的个人 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
--------------------------------------------------------------------------------

小开

TurboPFor: 最快的整数压缩

用于 C/C + + ，包括 Java 关键原生/JNI 接口
加速整数压缩
排序/未排序整数列表的标量 + 集成(SIMD)差分/Zigzag 编码/解码
全范围8/16/32/64位整数列表
直接访问
基准应用

小开

我不能让我的压缩比大约。11为这个。我通过 python 解释器生成了我的测试数据，它是一个从1-100到110-160的整数的换行分隔列表。我使用实际的程序作为数据的压缩表示。我的压缩文件如下:

main=mapM_ print [x|x<-[1..160],x`notElem`[101..109]]

它只是一个 Haskell 脚本，用于生成您可以通过以下方式运行的文件:

$ runhaskell generator.hs >> data

Hs 文件的大小为54字节，python 生成的数据为496字节。以0.10887096774193548为压缩比。我认为有更多的时间可以缩小程序，或者你可以压缩压缩文件(即 haskell 文件)。

另一种方法可能是保存4字节的数据。每个序列的最小值和最大值然后把它们给一个母函数。尽管如此，加载文件会给解压器增加更多的字符，给解压器增加更多的复杂性和更多的字节。同样，我通过一个程序表示了这个非常特殊的序列，它不是泛化的，它是一个特定于数据的压缩。此外，增加通用性使得解压器更大。

另一个问题是必须有 Haskell 解释器来运行它。当我编译这个程序时，它变得更大了。我也不知道为什么。Python 也有同样的问题，所以最好的方法可能是给出范围，这样一些程序就可以解压缩文件。