Алгоритм сжатия строки в строку?

Question

Я ищу алгоритм, который сжимал бы некоторую строку в другую строку (т.е. без "\ 0" или специальных управляющих символов), но я не могу найти что-либо в Интернете. Есть ли такой алгоритм? Это не должно быть особенно эффективно, просто что-то базовое.

Answer 1

Легко:

$ echo "Hello world" | gzip -c | base64
H4sIALnHeU4AA/NIzcnJVyjPL8pJ4QIA1eA5twwAAAA=

$ echo "H4sIALnHeU4AA/NIzcnJVyjPL8pJ4QIA1eA5twwAAAA=" | base64 -d | gzip -dc
Hello world

Примечание: похоже, сжатия нет, но для больших данных степень сжатия будет лучше: -)

Answer 2

Ваше требование об отсутствии «специальных символов» является очень строгим, если только вы не можете гарантировать, что подмножество символов (скажем, «~») не будет использоваться никогда . Затем вы можете использовать эти символы для обозначения вашего сжатия:

~ a -> the
~ b -> The
~ c -> и
~ d -> А
~ e -> Sirius Robotics Corporation Ltd.
и т. д.

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

Answer 3

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

Стандартные процедуры сжатия (например, gzip ) работают с байтомstrings.

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

Другой вариант - построить отображение 1-к-1 между строками.в вашем наборе символов и произвольных строках байтов отобразите исходную строку в строку байтов, сожмите строку байтов с помощью стандартной утилиты или функции сжатия и отобразите результат обратно в строку, используя ваш набор символов.(Строго говоря, вы можете использовать два разных сопоставления.)

Один из способов построения сопоставления состоит в том, чтобы дополнить ваш набор символов манекенами и специальным символом дополнения, пока у вас не будет 2 ^ k разных символов (для некоторого k);тогда каждый из 8 ваших символов соответствует k байтов (и более короткие строки могут быть дополнены символом pad).

Answer 4

Насколько я могу судить, самый популярный алгоритм сжатия, который позволяет повторно использовать стандартные процедуры обработки строки C для обработки сжатого текста (т. Е. Тщательно избегает помещения любых 0x00 байтов в сжатую строку, кроме как в концеМаркер-of-сжатых данных) представляет собой простое кодирование пары байтов , также называемое кодирование двойной мозаики или DTE.DTE часто используется для сжатия текста в ПЗУ видеоигр.

Когда декомпрессор DTE распечатывает строку, сжатую DTE, он читает по 1 байту за раз из строки, сжатой DTE, и выводит 1 или два байта:

• сжатый байт B в диапазоне 0x01..0xFF: декодер использует это в качестве индекса в «словаре» и печатает 1 или 2 байта, хранящихся в словаре с этим индексом.
• сжатый байт B равен 0x00, это конец строки - готово.

Типичная реализация DTE имеет встроенный словарь, хранящийся как в кодере, так и в декодере, что-то вродеэто:

• индексы часто используемых букв - возможно, весь диапазон isprint () ASCII (от 0x20 до 0x7e и символ новой строки 0x0A) - представляют себя.(Сжатый байт 'a' декодируется как одна буква 'a')
• индексирует от 0xc0 до 0xff: байт декодируется в 2 символа: пробел и буква, образованная из этого байта, XORed с0x80.(Сжатый байт (0x80 xor 'a') декодируется в 2 символа: пробел и букву 'a').
• Любые другие доступные индексы (0x7f..0xbf) хранят другие распространенные биграммы ("th "," re "и т. д.).