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

Question

Я хочу написать бэкэнд для хранения больших кусков данных. Данные могут быть любыми, но это в основном двоичные файлы (изображения, pdfs, jar-файлы) или текстовые файлы (xml, jsp, js, html, java ...). Я обнаружил, что большинство данных уже сжаты. Если все сжато, можно сэкономить около 15% дискового пространства.

Я ищу наиболее эффективный алгоритм, который с высокой вероятностью может предсказать, что часть данных (скажем, 128 КБ) может быть сжата или нет (сжатие без потерь), без необходимости просматривать все данные, если это возможно.

Алгоритм сжатия будет LZF, Deflate или что-то подобное (возможно, Google Snappy). Поэтому прогнозирование сжимаемости данных должно быть намного быстрее, чем сжатие самих данных, и использовать меньше памяти.

Алгоритмы, о которых я уже знаю:

• Попробуйте сжать подмножество данных, скажем, 128 байтов (это немного медленно)

• Рассчитать сумму 128 байтов, и если она находится в определенном диапазоне, то она, вероятно, не сжимается (в пределах 10% от 128 * 127) (это быстро и относительно хорошо, но я ищу что-то более надежным, поскольку алгоритм действительно просматривает только самые верхние биты для каждого байта)

• Посмотрите на заголовки файлов (относительно надежно, но похоже на читерство)

Я предполагаю, что общая идея заключается в том, что мне нужен алгоритм, который может быстро вычислить, если вероятность каждого бита в списке байтов примерно равна 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. уже предложено.

Answer 4

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

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

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

Вот БЫСТРАЯ бумага и слайды .

Answer 5

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

Answer 6

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

Answer 7

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

http://www.lzop.org

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

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

Answer 8

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

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

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

У меня вопрос инженерного характера - зачем все это? По сути, разве не угадаешь намерения пользователя / разработчика базы данных - за счет скорости?

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

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

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