лучший алгоритм сжатия со следующими характеристиками

Question

Какой лучший алгоритм сжатия со следующими функциями:

• для распаковки требуется меньше времени (может потребоваться больше времени для сжатия)
• должен иметь возможность сжимать отсортированные данные (примерный список из 3 000 000 строк / целых чисел ...)

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

Answer 1

Весь сайт посвящен сравнительному анализу компрессии здесь

Answer 2

Вам не нужно беспокоиться о времени декомпрессии. Время, потраченное на более высокий уровень сжатия, в основном находит самый длинный образец соответствия.

Декомпрессия либо

1) Writes the literal 
2) for (backward position, length)=(m,n) pair, 
   goes back, in the output buffer, m bytes, 
   reads n bytes and 
   writes n bytes at the end of the buffer.

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

Answer 3

Ну, если вам нужна скорость, тогда стандартное сжатие ZIP просто отлично, и оно, скорее всего, уже интегрировано в ваш язык / фреймворк (например, в .NET есть, в Java есть) Иногда самое универсальное решение является лучшим, ZIP является очень зрелым форматом, любая библиотека ZIP и приложение будут работать с любым другим.

Но если вам нужно лучшее сжатие, я бы предложил 7-Zip , так как автор очень умен, его легко достать и поощряет людей использовать этот формат.

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

Answer 4

Это интересный вопрос. Для таких отсортированных данных строк и целых чисел я бы ожидал, что подходы к сжатию с разностным кодированием превзойдут любой готовый подход к сжатию текста как LZ77 или LZ78 с точки зрения сжатия соотношение. Универсальный кодировщик не использует специальные свойства данных.