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

Question

我想编写一个存储后端来存储更大的数据块.数据可以是任何数据,但主要是二进制文件(图像,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

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

简化压缩

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

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 2

计算数据的熵.如果它具有高熵(~1.0),则不太可能进一步压缩.如果它具有低熵(~0.0),那么这意味着其中没有很多"信息"并且可以进一步压缩.

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

Answer 3

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

如果你想"正确"(即使我真的看不出这样做的理由),你要么必须在数据上运行(部分)压缩算法,要么计算熵,就像tskuzzy已经提出的那样.