Как эффективно прогнозировать, сжимаются ли данные

Ответ 1

Из моего опыта почти все форматы, которые могут быть эффективно сжаты, не являются бинарными. Поэтому, проверяя, находится ли около 70-80% символов внутри [0-127], ярость должна сделать трюк.

Если вы хотите "правильно" (хотя я действительно не вижу причины для этого), вам либо нужно выполнить (части) алгоритм сжатия данных, либо вычислить энтропию, как tskuzzy уже предложено.

Ответ 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;
}

Ответ 3

Рассчитайте entropy данных. Если он имеет высокую энтропию (~ 1.0), он вряд ли будет более сжатым. Если он имеет низкую энтропию (~ 0,0), то это означает, что в нем не так много "информации" и может быть дополнительно сжато.

Он дает теоретическое представление о том, как сжатый фрагмент данных может получить.

Ответ 4

Эта проблема интересна сама по себе, поскольку, например, zlib, сжимающая несжимаемые данные, занимает гораздо больше времени, чем сжатие сжимаемых данных. Таким образом, безуспешное сжатие особенно дорого (подробности см. В ссылках). Хорошая недавняя работа в этой области была проведена Harnik et al. от IBM.

Да, метод префикса и энтропия байта порядка-0 (называемая энтропией в других сообщениях) являются хорошими индикаторами. Другие хорошие способы угадать, является ли файл сжимаемым или нет (из бумаги):

• Размер основного набора. Набор символов, который составляет большую часть данных.
• Индикатор распределения символов-символов

Вот FAST бумага и slides.

Ответ 5

Я ожидаю, что нет способа проверить, насколько сжимаемо что-то, пока вы не попытаетесь сжать его. Вы можете проверить шаблоны (больше шаблонов, возможно, более сжимаемых), но тогда конкретный алгоритм сжатия может не использовать шаблоны, которые вы проверяли, и может делать лучше, чем вы ожидаете. Другой трюк может состоять в том, чтобы взять первые 128000 байт данных, проталкивать его через сжатие Deflate/Java и видеть, меньше ли он исходного размера. Если это так - возможно, стоит сжать всю партию.

Ответ 6

Быстрый компрессор, такой как LZ4, уже имеет встроенные проверки сжимаемости данных. Они быстро пропускают плохие сегменты, чтобы сосредоточиться на более интересных. Чтобы привести пример, LZ4 по несжимаемым данным работает с предельным пределом скорости (2 ГБ/с на моем ноутбуке). Таким образом, мало места для обнаружения детектора. Вы можете попробовать это сами: http://code.google.com/p/lz4/

Ответ 7

Также - Почему бы не попробовать lzop? Я могу лично поручиться за то, что он быстрее, намного быстрее (сжатие и декомпрессия), чем bzip, gzip, zip, rar...

http://www.lzop.org

Использование этого для сжатия образа диска делает процесс disk-Io связанным. Использование любого из других компрессоров делает процесс привязанным к процессору (т.е. Другие компрессоры используют весь доступный процессор, lzop (на разумном процессоре) может обрабатывать данные с той же скоростью, что и жесткий диск с жестким диском 7200 об/мин. )

Готов поспорить, если вы протестировали его с помощью первых X байтов строки "тестового сжатия", это будет намного быстрее, чем большинство других методов...

Ответ 8

В вашем профиле говорится, что вы являетесь автором H2 Database Engine, базы данных, написанной на Java.

Если я правильно догадываюсь, вы ищете, чтобы этот механизм базы данных автоматически сжимал данные BLOB, если это возможно.

Но - (я угадываю) вы поняли, что не все будет сжиматься, а скорость важна - так что вы не хотите тратить микросекунду больше, чем это необходимо при определении необходимости сжатия данных...

Мой вопрос - это техника в природе - зачем все это? В принципе, разве это не угадывает намерение разработчика пользовательских приложений/приложений - за счет скорости?

Не могли бы вы подумать, что разработчик приложения (кто первым записывает данные в поля blob) будет лучшим человеком для принятия решения, если данные должны быть сжаты или нет, а если так - выбрать соответствующий метод сжатия?

Единственное возможное место, где я могу видеть автоматическое сжатие базы данных, возможно, добавление некоторого значения в поля text/varchar - и только если они превышают определенную длину - но даже в этом случае эта опция может быть лучше решена приложением разработчик... Я бы даже зашел так далеко, чтобы позволить разработчику приложений плагин для сжатия, если так... Таким образом, они могут принимать собственные решения для своих собственных данных...

Если мои предположения о том, что вы пытаетесь сделать, были неправильными - тогда я смиренно извиняюсь за то, что сказал, что я сказал... (Это всего лишь одно незначительное мнение пользователей.)