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

Question

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

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

Answer 1

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

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

Максимальное сжатие - довольно крутой текстовый и общий тестовый сайт по сжатию. Мэтт Махони публикует еще один тест . 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 млн)