我有大量的整数数组。每个整数都有几千个整数，每个整数通常与之前的整数相同，或者仅相差一两位。我想将每个阵列缩小到尽可能小，以减少我的磁盘 IO。
Zlib 将其缩小到其原始大小的 25% 左右。这很好，但我不认为它的算法特别适合这个问题。有谁知道压缩库或简单算法可能对此类信息表现更好？
更新：zlib 将其转换为 xor deltas 数组后将其缩小到原始大小的 20% 左右。
twk
问问题
1620 次
7 回答
7
如果大多数整数真的和前面的一样，而且符号间的差异通常可以表示为一个位翻转，这听起来像是 XOR 的工作。
采用如下输入流：
1101
1101
1110
1110
0110
和输出：
1101
0000
0010
0000
1000
一点伪代码
compressed[0] = uncompressed[0]
loop
compressed[i] = uncompressed[i-1] ^ uncompressed[i]
我们现在已经将大部分输出减少到 0，即使高位被更改。您使用的任何其他工具中的 RLE 压缩都会有一个现场日。它在 32 位整数上的效果会更好，而且它仍然可以对流中弹出的完全不同的整数进行编码。您可以省去自己处理位打包的麻烦，因为一切都是整数大小的数量。
当你想解压时：
uncompressed[0] = compressed[0]
loop
uncompressed[i] = uncompressed[i-1] ^ compressed[i]
这还具有一个简单的算法的优点，它将运行得非常非常快，因为它只是 XOR。
于 2008-11-08T03:03:43.970 回答
5
您是否考虑过运行长度编码？
或者试试这个：不是存储数字本身，而是存储数字之间的差异。1 1 2 2 2 3 5 变为 1 0 1 0 0 1 2。现在您必须编码的大多数数字都非常小。要存储一个小整数，请使用 8 位整数，而不是您将在大多数平台上编码的 32 位整数。那是 4 的因数。如果您确实需要为比这更大的间隙做好准备，请指定 8 位整数的高位表示“这个数字也需要接下来的 8 位”。
您可以将其与游程编码相结合，以获得更好的压缩率，具体取决于您的数据。
这些选项都不是特别难以实现，而且它们都运行得非常快且内存非常少（与 bzip 相反）。
于 2008-11-08T02:02:48.290 回答
2
也许答案是以类似于用于创建小型 PNG 图像的过滤的方式对数组进行预过滤。这里有一些想法就在我的脑海中。我没有尝试过这些方法，但如果你喜欢玩，它们可能会很有趣。
将每个整数分解为 4 个字节，因此 i 0、 i 1、 i 2、 ...、 i n变为 b 0,0、 b 0,1、 b 0,2、 b 0,3、 b 1,0 , b 1,1 , b 1,2 , b 1,3 , ..., b n,0 , b n,1 , b n,2 , b n,3。然后写出所有的 b i,0 s，然后是 b i,1 s、b i,2 s 和 b i,3s。如果大多数情况下您的数字仅相差一两点，您应该得到很好的长时间重复字节，使用 Run-length Encoding 或 zlib 之类的东西应该可以很好地压缩。这是我介绍的方法中我最喜欢的。
如果每个数组中的整数与之前的整数密切相关，您可以存储原始整数，然后存储与前一个条目的差异 - 这应该会提供一组较小的值来提取，这通常会导致更压缩形式。
如果您有各种不同的位，您仍然可能有较大的差异，但如果您更有可能有较大的数字差异对应于（通常）一个或两个不同的位，那么您最好使用创建 ahebyte 的方案数组 - 使用前 4 个字节对第一个整数进行编码，然后对于每个后续条目，使用 0 个或更多字节来指示应该翻转哪些位 - 在字节中存储 0、1、2、... 或 31，有一个哨兵（比如 32）来指示你什么时候完成。这可能导致表示所需的原始字节数和整数平均接近 2，其中大多数字节来自有限的集合 (0 - 32)。通过 zlib 运行该流，也许你会感到惊喜。
于 2008-11-08T02:09:47.620 回答
2
您想要预处理您的数据——首先将其可逆地转换为更适合您的后端数据压缩方法的某种形式。详细信息将取决于后端压缩方法，以及（更重要的是）您期望从您正在压缩的数据中获得的属性。
在您的情况下，zlib 是一种按字节压缩的方法，但是您的数据以（32 位？）整数形式出现。您不需要自己重新实现 zlib，但您确实需要阅读它是如何工作的，这样您就可以弄清楚如何使用易于压缩的数据来呈现它，或者它是否完全适合您的目的。
Zlib 实现了一种 Lempel-Ziv 编码形式。JPG 和许多其他的后端使用 Huffman 编码。游程编码在许多特殊用途中很流行。等等等等……
于 2008-11-08T02:11:36.587 回答
0
您为此尝试过 bzip2 吗？ http://bzip.org/
对我来说，它总是比 zlib 更好。
于 2008-11-08T01:56:11.393 回答
0
由于您关心的是减少磁盘 IO，因此您需要独立压缩每个整数数组，而不参考其他整数数组。
您的场景的常用技术是存储差异，因为可以使用短代码字对少量差异进行编码。听起来您需要为差异提出自己的编码方案，因为它们是多位差异，也许使用像这样的 8 位字节作为起点：
- 1 位表示后面跟着一个完整的新整数，或者该字节编码与上一个整数的差异，
- 1 位表示后面有更多字节，记录相同整数的更多个位差异。
- 6 位记录从您之前的整数切换的位数。
如果有超过 4 位不同，则存储整数。
如果您还有许多完全不同的代码，则此方案可能不合适，因为它们现在每个占用 5 个字节而不是 4 个。
于 2008-11-08T02:26:12.253 回答
0
“Zlib 将其缩小了大约 4 倍。” 表示现在100K的文件占用负300K；从任何定义来看，这都令人印象深刻:-)。我假设您的意思是将其缩小 75%，即缩小到其原始大小的 1/4。
一种优化压缩的可能性如下（它假定一个 32 位整数和最多 3 位从一个元素到另一个元素变化）。
- 输出第一个整数（32 位）。
- 输出位数变化（n=0-3，2位）。
- 输出 n 位说明符（0-31，每个 5 位）。
这种压缩的最坏情况是每个整数（2+5+5+5 位）发生 3 位变化，这将趋向于原始大小的 17/32（46.875% 压缩）。
我说“趋向于”，因为第一个整数总是 32 位，但是对于任何大小合适的数组，第一个整数可以忽略不计。
最好的情况是相同整数的文件（每个整数没有位更改，只有 2 个零位） - 这将趋向于原始大小的 2/32（93.75% 压缩）。
如果每个连续整数平均有 2 位不同（正如您所说的是您的常见情况），您将获得每个整数 2+5+5 位，这将趋向于 12/32 或 62.5% 的压缩。
您的收支平衡点（如果 zlib 提供 75% 压缩）是每个整数 8 位，这将是
- 单位变化（2+5 = 7 位）：80% 的转换。
- 双位变化（2+5+5 = 12 位）：20% 的转换。
这意味着您的平均每个整数必须更改 1.2 位才能使这变得有价值。
我建议看的一件事是 7zip——它有一个非常自由的许可证，你可以将它与你的代码链接起来（我认为源代码也是可用的）。
我注意到（无论如何我的东西）它在 Windows 平台上的性能比 WinZip 好得多，因此它也可能优于 zlib 。
于 2008-11-08T05:10:14.263 回答