Алгоритм сжатия текста

Question

Мне просто интересно, может ли кто-нибудь представить мне какой-либо алгоритм, который сжимает текст Unicode до 10-20 процентов от его первоначального размера? на самом деле я читал Lempel-Ziv compression алгоритм, который уменьшает размер текста до 60% от исходного размера, но я слышал, что есть некоторые алгоритмы с этой производительностью

Answer 1

Если вы рассматриваете только сжатие текста, чем самый первый алгоритм, который использует шифрование энтропии называется Хаффман кодирование

Huffman Coding

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

LZW compression

Я думаю, что выше два являются достаточными для эффективного кодирования текстовых данных и легко реализовать.

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

Answer 2

LZ-подобные кодеры не подходят для сжатия текста. Лучшим для прямого использования с unicode будет lzma, хотя, поскольку у него есть параметры выравнивания позиции. (http://www.7-zip.org/sdk.html)

Но для лучшего сжатия я бы предложил преобразовать тексты в формате unicode в формат bytewise, например. utf8, а затем использовать алгоритм с известными хорошими результатами по текстам, например. (http://libbsc.com) или PPMd (http://compression.ru/ds/ppmdj1.rar).

Кроме того, некоторая предварительная обработка может быть применена для улучшения результатов текста сжатия (см http://xwrt.sourceforge.net/) И ты некоторые компрессоры даже лучше, чем соотношение предлагаемых единицы (в основном PAQ производные), но они также гораздо медленнее.

Здесь я тестировал различные представления русского перевода Виттена «Моделирование для сжатия текста»:

 
          7z rar4 paq8px69 
modeling_win1251.txt 156091 50227 42906 36254 
modeling_utf16.txt 312184 52523 50311 38497 
modeling_utf8.txt  238883 53793 44231 37681 
modeling_bocu.txt  165313 53073 44624 38768 
modeling_scsu.txt  156261 50499 42984 36485 

Это показывает, что больше входа не обязательно означает, что в целом лучше сжатие, и ГТС, хотя полезно , на самом деле не лучшее представление текста юникода (кодовая страница win1251 тоже одна).