pde*_*eva 50 compression algorithm
我有一个大数组,其中包含大多数连续的整数,例如1-100,110-160等.所有整数都是正数.压缩它的最佳算法是什么？
我尝试了deflate算法,但这只给我50%的压缩.请注意,算法不能有损.
所有数字都是独一无二的并逐渐增加.
另外,如果你能指出我的这种算法的java实现会很棒.
Dan*_*ire 67
我们写了最近的研究论文,调查了这个问题的最佳方案.请参阅:
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
Ces*_*arB 32
首先,通过获取每个值与前一个值之间的差值来预处理您的值列表(对于第一个值,假设前一个值为零).在您的情况下,这应该主要提供一系列的,可以通过大多数压缩算法更容易地压缩.
这就是PNG格式如何改进其压缩(它采用了几种差异方法之一,后跟gzip使用的相同压缩算法).
Tam*_*mir 17
好吧,我投票支持更聪明的方式.所有你必须存储的是[int:startnumber] [int/byte/whatever:迭代次数]在这种情况下,你将把你的示例数组转换为4xInt值.在它之后你可以按你想要压缩:)
bri*_*gge 14
虽然您可以设计特定于您的数据流的自定义算法,但使用现成的编码算法可能更容易.我运行了一些Java中可用的压缩算法测试,并发现了一百万个连续整数序列的以下压缩率:
None 1.0
Deflate 0.50
Filtered 0.34
BZip2 0.11
Lzma 0.06
Mar*_*ell 11
数字的大小是多少？除了其他答案之外,您还可以考虑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<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;
}
}