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

Question

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

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

Answer 1

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

• Burrows-Wheeler Transform и here - перетасовать символы (или другие битовые блоки) с предсказуемым алгоритмом для увеличения повторных блоков, что делает источник легче сжать. Декомпрессия происходит как обычно, и результат не перепутан с обратным преобразованием. Примечание. Только BWT фактически ничего не сжимает. Это просто облегчает сжатие источника.
• Prediction by Partial Matching (PPM) - эволюция arithmetic coding, где модель прогнозирования (контекст) создается путем хрустания статистики об источнике и использовании статических вероятностей. Хотя его корни в арифметическом кодировании, результат может быть представлен кодировкой Хаффмана или словарем, а также арифметическим кодированием.
• Контекстное смешивание. Арифметическое кодирование использует статический контекст для прогнозирования, PPM динамически выбирает один контекст, Context Mixing использует множество контекстов и взвешивает их результаты. PAQ использует смешивание контекста. Here's обзор высокого уровня.
• Dynamic Markov Compression - связанный с PPM, но использует контексты бит-уровня по сравнению с байтом или дольше.
• Кроме того, конкурсанты премии Hutter могут заменять обычный текст с помощью маленьких байтов из внешних словарей и различать текст верхнего и нижнего регистра со специальным символом в сравнении с использованием двух разных записей. Вот почему они так хороши в сжатии текста (особенно в тексте ASCII), а не как ценном для общего сжатия.

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

Answer 2

Всегда есть lzip.

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

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

Answer 3

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

zpaq c archivename.zpaq file1 file2 file3 

Сжатие было около 1/10th размер ZIP-файла. (1.9M против 15M)