Как вы можете обратимо сжимать немного текста в меньшее количество символов ASCII?

Question

Я хочу взять произвольную строку текста ASCII, например «Hello world», и сжать ее до версии с меньшим количеством символов (как можно меньше), но таким образом, чтобы ее можно было распаковать.Сжатая версия должна состоять только из символов ascii.Есть ли способ сделать это, особенно в Ruby?

Answer 1

Если вы знаете, что будут использоваться только символы ASCII, то это 7 младших бит каждого байта.С помощью битовых манипуляций можно разбивать каждые 8 ​​байтов на 7 (экономия 12,5%).Если вы можете получить его в меньшем диапазоне (только 64 действительных символа), вы можете отбросить еще один байт.

Однако, поскольку вы хотите, чтобы сжатая форма ТАКЖЕ содержала только символы ASCII, вы теряете один байт - чтовозвращается на круги своя, если только ваш ввод не может быть ограничен 64-символами (например, сжатие с потерями, замена некоторых символов другими, сохранение только в нижнем регистре и т. д.).

Если ваши строки невелики (> 1k)тогда с помощью gzip / bzip2 и т. д. достигается минимальная экономия из-за размера заголовков.Если у вас был предопределенный словарь для использования в качестве таблицы Хаффмана, вы можете получить некоторое сжатие, но в других случаях вы можете раздуваться против исходного текста .

Предыдущее обсуждение SO Эффективный алгоритм сжатия коротких текстовых строк

Answer 2

Существует много хороших алгоритмов сжатия текста, таких как кодировка Хаффмана или LZW , которые хорошо сжимают текстовые строки в битовые строки с намного меньшим количеством битов, чем стандартная кодировка ASCII.Если у вас есть такая кодировка, вы всегда можете разбить цепочку битов на группы по семь бит, чтобы упаковать их в стандартные символы ASCII.Я уверен, что есть библиотеки, которые делают это, но я не очень разбираюсь в Ruby и не знаю ни одной из них.

Answer 3

Самый простой способ сделать это - сжать его с помощью стандартного алгоритма, а затем base64 закодировать результат. Это вряд ли поможет для такой короткой строки, как «Hello world», хотя - при таком размере вы очень мало можете сделать, чтобы уменьшить его размер, если только у всех ваших строк нет одинакового ограниченного набора символов или шаблонов, которые что-то как кодирование Хаффмана может воспользоваться.

Answer 4

Если вы говорите по-английски, например, по-английски, вы можете уйти, пропустив общие символы, если ваше слово остается однозначным. Например, «Hello world» может стать «Hll wrld», если ваш словарь содержит только Hello для соответствия Hll и world для соответствия wrld. Семитские языки, такие как арабский, на самом деле не имеют вокала на своем письменном языке, и людям по-прежнему удается их читать. Кроме того, другие правила, например, когда слово должно быть в верхнем регистре, могут использоваться для сокращения набора символов до символов нижнего регистра (при условии, что данный текст следует этим правилам).

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