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

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

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

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

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

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

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

Я предполагаю, что общая идея заключается в том, что мне нужен алгоритм, который может быстро рассчитать, если вероятность каждого бита в списке байтов составляет примерно 0,5.

Обновить

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

Дополнительные ответы (новые идеи) все еще приветствуются! Если возможно, с исходным кодом или ссылками :-)

Обновление 2

Подобный методтеперь реализовано в Linux.