Каково текущее состояние алгоритмов сжатия только для текста?

Question

В честь премии Хаттера, каковы главные алгоритмы (и краткое описание каждого) для сжатия текста?

Примечание. Цель этого вопроса - получить описание алгоритмов сжатия, а не программ сжатия.

Answer 1

Компрессоры, работающие на границе, объединяют алгоритмы для безумных результатов. Общие алгоритмы включают в себя:

• Преобразование Барроуза-Уилера и здесь - перемешивание символов (или других битовых блоков) с предсказуемым алгоритмом для увеличения повторяющихся блоков, что облегчает сжатие источника. Декомпрессия происходит как обычно, и результат не перетасовывается с обратным преобразованием. Примечание: BWT сам по себе ничего не сжимает. Это просто облегчает сжатие источника.
• Прогнозирование путем частичного сопоставления (PPM) - эволюция арифметического кодирования, где модель прогнозирования (контекст) создается путем анализа статистики об источнике по сравнению с использованием статических вероятностей. Даже если его корни в арифметическом кодировании, результат может быть представлен с помощью кодирования Хаффмана или словаря, а также арифметического кодирования.
• Смешивание контекста - арифметическое кодирование использует статический контекст для прогнозирования, PPM динамически выбирает один контекст, смешивание контекста использует много контекстов и взвешивает их результаты. PAQ использует контекстное смешивание. Вот обзор высокого уровня.
• Динамическое сжатие Маркова - относится к PPM, но использует контексты на уровне битов по сравнению с байтом или дольше.
• Кроме того, участники конкурса на призы Хаттера могут заменить обычный текст небольшими байтами записей из внешних словарей и дифференцировать текст в верхнем и нижнем регистре специальным символом вместо использования двух разных записей. Вот почему они так хорошо сжимают текст (особенно текст ASCII) и не так ценны для общего сжатия.

Maximum Compression - довольно крутой текстовый и общий тестовый сайт по сжатию. Мэтт Махони публикует еще один тест. Mahoney's может представлять особый интерес, поскольку в нем перечислены основные алгоритмы, используемые для каждой записи.

Answer 2

Там всегда lzip.

Все шутки в сторону:

• Где совместимость является проблемой, PKZIP (DEFLATE алгоритм) все еще выигрывает.
• bzip2 - лучший компромисс между сравнительно широкой установочной базой и довольно хорошей степенью сжатия, но требует отдельного архиватора.
• 7-Zip (LZMA алгоритм) сжимается очень хорошо и доступен для LGPL. Однако немногие операционные системы поставляются со встроенной поддержкой.
• rzip - это вариант bzip2, который, на мой взгляд, заслуживает большего внимания. Это может быть особенно интересно для огромных файлов журналов, которые требуют длительного архивирования. Также требуется отдельный архиватор.

Answer 3

Если вы хотите использовать PAQ в качестве программы, вы можете установить zpaq пакет на системах на основе Debian. Использование есть (см. Также man zpaq)

zpaq c archivename.zpaq file1 file2 file3

Сжатие составило примерно 1/10 размера файла zip. (1,9 млн против 15 млн)