Какой алгоритм наиболее подходит для сжатия большого текста?
В настоящее время я ищу алгоритм сжатия без потерь, который подходит для большого объема текста, который будет дополнительно зашифрован AES и будет использоваться в качестве полезной нагрузки в стеганографии.
РЕДАКТИРОВАТЬ:
Основываясь на сравнительном исследовании алгоритмов сжатия текста, кажется, что арифметическое кодирование предпочтительнее в методах статистического сжатия, в то время как LZB рекомендуется для методов сжатия словаря.
Поэтому теперь мне интересно, является ли статистическое сжатие или словарное сжатие более подходящим для сжатия большого английского текста с точки зрения степени сжатия и простоты реализации.
У меня есть поиск через, но все еще едва ли есть представление о подходящем алгоритме. Большое спасибо за ваше время ответить. Хорошего дня.:)
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.
Кодирование Шеннона-Фано, кодирование Хаффмана, арифметическое кодирование, кодирование по дальности и кодирование асимметричной системы счисления - все это энтропийные кодеры нулевого порядка, применяемые после того, как вы впервые смоделировали свои данные, используя преимущества внутренней избыточности.
Для текста эта избыточность представляет собой повторяющиеся строки и корреляции высшего порядка в данных. Существует несколько способов моделирования текста. Наиболее распространенными являются Lempel-Ziv 77, который ищет совпадающие строки, преобразование Барроуза-Уилера (ищите описание) и прогнозирование путем частичного сопоставления.
Обратитесь к тесту сжатия большого текста, чтобы увидеть сравнение по сжатию, скорости сжатия, используемой памяти и скорости распаковки.