Какой алгоритм наиболее подходит для сжатия большого текста?

Question

В настоящее время я ищу алгоритм сжатия без потерь, который подходит для большого объема текста, который будет дополнительно зашифрован AES и будет использоваться в качестве полезной нагрузки в стеганографии.

EDIT:

На основании Сравнительного исследования алгоритмов сжатия текста , кажется, что Арифметическое кодирование является предпочтительным в методах статистического сжатия, в то время как LZB рекомендуется для методов сжатия в словаре.

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

У меня есть поиск, но я все еще не знаю подходящего алгоритма. Большое спасибо за ваше время в ответе. Хорошего дня. :)

Answer 1

Кодирование Шеннона-Фано, кодирование Хаффмана, арифметическое кодирование, кодирование по диапазонам и кодирование асимметричной системы счисления - все это энтропийные кодеры нулевого порядка, применяемые после , когда вы сначала смоделировали свои данные, используя преимущества присущей им избыточности .

Для текста эта избыточность представляет собой повторяющиеся строки и корреляции высшего порядка в данных. Существует несколько способов моделирования текста. Наиболее распространенными являются Lempel-Ziv 77, который ищет подходящие строки, преобразование Барроуза-Уилера (см. Описание) и прогнозирование путем частичного сопоставления.

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

Answer 2

Многие алгоритмы, которые вы описываете в этом вопросе, называются энтропийными кодерами (Шеннон-Фано, Хаффмана, арифметика и т. Д.). Энтропийные кодеры используются для сжатия последовательностей символов (часто байтов), где некоторые символы встречаются гораздо чаще, чем другие. Простое энтропийное кодирование символов (букв) для сжатия естественного языка даст только сжатие 2: 1.

Вместо этого популярные современные методы сжатия без потерь для текста включают такие методы, как LZ77, LZW и BWT. Грубо говоря, семейство LZ включает создание словаря повторяющихся коротких последовательностей символов (мы будем называть их «словами»), а затем использует указатели для ссылки на эти слова. Некоторые из реализаций LZ, такие как LZ77 и LZW, могут быть довольно просты для кодирования, но, вероятно, не дают наивысших коэффициентов сжатия. Смотрите, например, это видео: https://www.youtube.com/watch?v=j2HSd3HCpDs. На другом конце спектра, LZMA2, это относительно более сложный вариант с более высокой степенью сжатия.

Преобразование Барроуза-Уилера (BWT) предоставляет умную альтернативу словарным методам. Я отошлю вас к статье в Википедии, https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform

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

Если бы для простоты мне пришлось кодировать технику сжатия с нуля, я бы, вероятно, выбрал LZW или LZ77.