如何有效地预测数据是否可压缩

我想编写一个存储后端来存储更大的数据块。 数据可以是任何东西，但它主要是二进制文件（图像，pdf，jar文件）或文本文件（xml，jsp，js，html，java …）。 我发现大部分数据已经被压缩了。 如果所有内容都已压缩，则可以节省大约15％的磁盘空间。

我正在寻找最有效的算法，可以高概率地预测一块数据（比如说128 KB）是否可以被压缩（无损压缩），而不必在可能的情况下查看所有数据。

压缩算法将是LZF，Deflate或类似的东西（可能是Google Snappy）。 因此，预测数据是否可压缩应该比压缩数据本身快得多，并且使用更少的内存。

我已经知道的算法：

• 尝试压缩数据的一个子集，比方说128个字节（这有点慢）

• 计算128个字节的总和，如果它在一定范围内，则它可能不可压缩（在128 * 127的10％范围内）（这很快，而且相对较好，但我正在寻找更可靠的东西，因为算法实际上只查看每个字节的最高位）

• 查看文件头（相对可靠，但感觉像作弊）

我想一般的想法是我需要一种能够快速计算字节列表中每个位的概率是否大约为0.5的算法。

更新

我实现了’ASCII检查’，’熵计算’和’简化压缩’，并且都给出了很好的结果。 我想改进算法，现在我的想法是不仅要预测数据是否可以被压缩，还要预测它可以被压缩多少 。 可能使用算法的组合。 现在，如果我只能接受多个答案……我会接受给出最佳结果的答案。

其他答案（新想法）仍然欢迎！ 如果可能，使用源代码或链接:-)

更新2

现在在Linux中实现了类似的方法。

Answer 1

根据我的经验，几乎所有可以有效压缩的格式都是非二进制的。 因此，检查大约70-80％的角色是否在[0-127]愤怒范围内应该可以解决问题。

如果你想“正确”（即使我真的看不出这样做的原因），你要么必须在数据上运行（部分）压缩算法，要么计算熵，就像tskuzzy已经提出的那样。

Answer 2

我实现了一些方法来测试数据是否可压缩。

简化压缩

这基本上检查重复的字节对：

static boolean isCompressible(byte[] data, int len) { int result = 0; // check in blocks of 256 bytes, // and sum up how compressible each block is for (int start = 0; start < len; start += 256) { result += matches(data, start, Math.min(start + 255, len)); } // the result is proportional to the number of // bytes that can be saved // if we can save many bytes, then it is compressible return ((len - result) * 777) < len * 100; } static int matches(byte[] data, int i, int end) { // bitArray is a bloom filter of seen byte pairs // match counts duplicate byte pairs // last is the last seen byte int bitArray = 0, match = 0, last = 0; if (i < 0 || end > data.length) { // this check may allow the JVM to avoid // array bound checks in the following loop throw new ArrayIndexOutOfBoundsException(); } for (; i < end; i++) { int x = data[i]; // the bloom filter bit to set int bit = 1 << ((last ^ x) & 31); // if it was already set, increment match // (without using a branch, as branches are slow) match -= (-(bitArray & bit)) >> 31; bitArray |= bit; last = x; } return match; } 

在我的（有限的）测试数据集上，该算法非常准确。 如果数据不可压缩，它比压缩自身快5倍。 对于普通数据（全零），它的速度大约是一半。

部分熵

该算法估计高半字节的熵。 我想避免使用太多的桶，因为每次都必须将它们清零（如果要检查的块很小，则速度很慢）。 63 - numberOfLeadingZeros是对数（我想避免使用浮点数）。 根据数据，它比上面的算法更快或更慢（不确定原因）。 结果不如上面的算法那么精确，可能是因为仅使用了16个桶，而只使用整数算术。

 static boolean isCompressible(byte[] data, int len) { // the number of bytes with // high nibble 0, 1,.., 15 int[] sum = new int[16]; for (int i = 0; i < len; i++) { int x = (data[i] & 255) >> 4; sum[x]++; } // see wikipedia to understand this formula :-) int r = 0; for (int x : sum) { long v = ((long) x << 32) / len; r += 63 - Long.numberOfLeadingZeros(v + 1); } return len * r < 438 * len; } 

Answer 3

计算数据的熵 。 如果它具有高熵（~1.0），则不太可能进一步压缩。 如果它具有低熵（~0.0），那么这意味着其中没有很多“信息”并且可以进一步压缩。

它提供了对一段数据压缩程度的理论测量。

Answer 4

这个问题很有意思，因为例如zlib压缩不可压缩数据比压缩可压缩数据需要更长的时间。 因此，不成功的压缩尤其昂贵（有关详细信息，请参阅链接）。 Harnik等人已经在这方面做了很好的工作。 来自IBM。

是的，前缀方法和字节顺序-0熵（在其他post中称为熵）是很好的指标。 猜测文件是否可压缩的其他好方法是（来自论文）：

• 核心集大小 – 构成大部分数据的字符集
• 符号对分布指标

这是快速论文和幻灯片 。

Answer 5

我希望在你尝试压缩之前没有办法检查可压缩的东西是什么。 您可以检查模式（更多模式，可能更可压缩），但是特定的压缩算法可能不会使用您检查的模式 – 并且可能比您预期的更好。 另一个技巧可能是获取前128000字节的数据，将其推送到Deflate / Java压缩，并查看它是否小于原始大小。 如果是这样的话 – 很有可能压缩整个批次。

Answer 6

诸如LZ4之类的快速压缩器已经内置了数据压缩性检查。 他们很快跳过坏节目，专注于更有趣的节目。 举一个正确的例子，不可压缩数据的LZ4工作在几乎RAM速度限制（我的笔记本电脑上2GB / s）。 因此探测器几乎没有更快的空间。 您可以亲自尝试： http ： //code.google.com/p/lz4/

Answer 7

它在您的个人资料中说您是H2数据库引擎的作者，这是一个用Java编写的数据库。

如果我猜对了，你正在设计这个数据库引擎来自动压缩BLOB数据，如果可能的话。

但是 – （我猜）你已经意识到并不是所有东西都会压缩，速度很重要 – 所以你不想在确定是否应该压缩数据时浪费超过微秒的时间……

我的问题是工程性的 – 为什么这一切？ 基本上，是不是第二次猜测数据库用户/应用程序开发人员的意图 – 以牺牲速度为代价？

难道您不认为应用程序开发人员（首先将数据写入blob字段）是决定数据是否应该被压缩的最佳人选，如果是这样的话 – 选择适当的压缩方法？

我可以看到自动数据库压缩可能添加一些值的唯一可能的地方是text / varchar字段 – 并且只有当它们超出一定长度时 – 但即便如此，该选项可能由应用程序开发人员更好地决定。我甚至可能会允许应用程序开发人员使用压缩插件，如果是这样的话…这样他们就可以为自己的数据做出自己的决定……

如果我对你想要做的事情的假设是错误的 – 那么我谦卑地道歉说出我说的话……（这只是一个微不足道的用户的意见。）

Answer 8

另外 – 为什么不尝试lzop？ 我个人可以保证它比bzip，gzip，zip，rar更快，更快（压缩和解压缩）…

http://www.lzop.org

使用它进行磁盘映像压缩会使进程磁盘IO绑定。 使用任何其他压缩器使得进程受CPU限制（即，其他压缩器使用所有可用的CPU，lzop（在合理的CPU上）可以以相同的速度处理数据，7200 RPM的硬盘驱动器可以将其清除… ）

我敢打赌，如果用“测试压缩”字符串的前X个字节测试它，它会比大多数其他方法快得多……