Алгоритм сжатия текста
Мне просто интересно, может ли кто-нибудь представить мне какой-нибудь алгоритм, который сжимает текст Unicode до 10-20 процентов от его первоначального размера? на самом деле я читал алгоритм сжатия Lempel-Ziv, который уменьшает размер текста до 60% от исходного размера, но я слышал, что есть некоторые алгоритмы с такой производительностью
3 ответа
Если вы рассматриваете только сжатие текста, тогда самый первый алгоритм, использующий энтропийное шифрование, называется Huffman Encoding.
Затем происходит сжатие LZW, которое использует словарную кодировку, чтобы использовать ранее использованную последовательность букв для назначения кодов, чтобы уменьшить размер файла.
Я думаю, что выше двух достаточно для эффективного кодирования текстовых данных и их легко реализовать.
Примечание: Не ожидайте хорошего сжатия для всех файлов. Если данные случайные без шаблона, то никакой алгоритм сжатия не может дать вам никакого сжатия вообще. Процент сжатия зависит от символов, появляющихся в файле, а не только от используемого алгоритма.
LZ-подобные кодеры не годятся для сжатия текста. Лучшим вариантом для прямого использования с юникодом будет lzma, так как он имеет опции выравнивания позиции. ( http://www.7-zip.org/sdk.html)
Но для лучшего сжатия я бы предложил преобразовать тексты в юникоде в байтовый формат, например. utf8, а затем использовать алгоритм с известными хорошими результатами по текстам, например. BWT ( http://libbsc.com/) или PPMd ( http://compression.ru/ds/ppmdj1.rar).
Также некоторая предварительная обработка может быть применена для улучшения результатов сжатия текста (см. http://xwrt.sourceforge.net/). И есть некоторые компрессоры с еще лучшим соотношением, чем предложенные (в основном, производные от paq), но они также намного помедленнее.
Здесь я протестировал различные представления русского перевода Виттена "Моделирование для сжатия текста":
7z rar4 paq8px69 моделирование_win1251.txt 156091 50227 42906 36254 моделирование_utf16.txt 312184 52523 50311 38497 моделирование_utf8.txt 238883 53793 44231 37681 models_bocu.txt 165313 53073 44624 38768 моделирование_scsu.txt 156261 50499 42984 36485
Это показывает, что более длинный ввод не обязательно означает лучшее общее сжатие, и что SCSU, хотя и полезен, на самом деле не лучшее представление текста в кодировке Unicode (кодовая страница win1251 тоже одна).
PAQ - новый действующий чемпион по сжатию текста... Существует несколько различных вариантов, и информацию о них можно найти здесь.
Есть три вкуса, которые я рекомендую:
- ZPAQ - Контейнер будущего для алгоритмов PAQ (создан, чтобы облегчить будущее PAQ)
- PAQ8PX / PAQ8KX - самый мощный, работает также с файлами EXE и WAV.
- PAQ8PF - быстрее (как сжатие, так и распаковка) и в основном предназначено для файлов TXT
Вы должны собрать их самостоятельно из исходного кода, к счастью, кто-то создал графический интерфейс FrontPAQ, который объединяет два лучших двоичных файла в один.
Если у вас есть функциональный бинарный файл, который прост в использовании, документацию можно найти здесь.
Примечание: я знаю, что это очень старый вопрос, но я хотел бы включить соответствующие современные данные. Я искал тот же вопрос, но нашел более мощный ответ.