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

Question

我想编写一个存储后端来存储更大的数据 block 。数据可以是任何东西，但主要是二进制文件(图像、pdf、jar 文件)或文本文件(xml、jsp、js、html、java...)。我发现大部分数据已经被压缩了。如果全部压缩，大约可以节省 15% 的磁盘空间。

我正在寻找一种最有效的算法，该算法能够以高概率预测数据 block (比如 128 KB)是否可以压缩(无损压缩)，而无需尽可能查看所有数据。

压缩算法将是 LZF、Deflate 或类似的算法(可能是 Google Snappy)。所以预测数据是否可压缩应该比压缩数据本身要快得多，并且使用更少的内存。

我已经知道的算法:

• 尝试压缩数据的一个子集，比如说 128 字节(这有点慢)

• 计算 128 字节的总和，如果在一定范围内则可能不可压缩(在 128 * 127 的 10% 以内)(这个速度很快，也比较好，但我在找东西更可靠，因为该算法实际上只查看每个字节的最高位)

• 看文件头(比较靠谱，但感觉像作弊)

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

更新

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

仍然欢迎其他答案(新想法)!如果可能的话，提供源代码或链接:-)

更新 2

类似的方法是now implemented in Linux .

Answer 1

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

如果你想“正确地”这样做(即使我真的看不出这样做的理由)，你要么必须对数据运行(部分)压缩算法，要么计算熵，如 tkuzzy已经提议了。