Какова наиболее эффективная кодировка двоичного текста?

Question

Ближайшими претендентами, которых я смог найти, являются yEnc (2%) и ASCII85 (25% накладных расходов). Кажется, есть некоторые проблемы вокруг yEnc, в основном связанные с тем, что он использует 8-битный набор символов. Что приводит к другой мысли: существует ли кодировка бинарного текста на основе набора символов UTF-8?

Answer 1

Это действительно зависит от характера двоичных данных и ограничений, которые «текст» накладывает на ваш вывод.

Прежде всего, если ваши двоичные данные не сжаты, попробуйте сжать перед кодированием. Затем можно предположить, что распределение 1/0 или отдельных байтов является более или менее случайным.

Теперь: зачем тебе текст? Как правило, это потому, что канал связи не проходит через все символы одинаково. например вам может потребоваться чистый текст ASCII, чьи печатаемые символы варьируются от 0x20-0x7E. У вас есть 95 персонажей для игры. Каждый символ может теоретически кодировать log2 (95) ~ = 6,57 бит на символ. Легко определить преобразование, которое подходит довольно близко.

Но: что если вам нужен символ-разделитель? Теперь у вас есть только 94 символа и т. Д. Поэтому выбор кодировки действительно зависит от ваших требований.

Возьмем очень глупый пример: если ваш канал передает все 256 символов без проблем и вам не нужны разделители, тогда вы можете написать тривиальное преобразование, которое достигает 100% эффективности. :-) Как это сделать, оставлено в качестве упражнения для читателя.

UTF-8 не подходит для произвольно закодированных двоичных данных. Он может передавать значения 0x01-0x7F только с 14% служебной нагрузки. Я не уверен, является ли 0x00 законным; скорее всего нет. Но все, что выше 0x80, расширяется до нескольких байтов в UTF-8. Я бы рассматривал UTF-8 как ограниченный канал, который передает 0x01-0x7F, или 126 уникальных символов. Если вам не нужны разделители, вы можете передавать 6,98 бит на символ.

Общее решение этой проблемы: предположим, что алфавит состоит из N символов, двоичные кодировки которых равны от 0 до N-1. (Если кодировки не соответствуют предполагаемым, используйте таблицу поиска для перевода между нашим промежуточным представлением 0..N-1 и тем, что вы на самом деле отправляете и получаете.)

Предположим, 95 символов в алфавите. Теперь: некоторые из этих символов будут представлять 6 бит, а некоторые будут представлять 7 бит. Если у нас есть A 6-битные символы и B 7-битные символы, то:

A + B = 95 (общее количество символов) 2A + B = 128 (общее количество 7-битных префиксов, которые можно сделать. Вы можете начать 2 префикса с 6-битного символа или один с 7-битным символом.)

Решая систему, вы получаете: A = 33, B = 62. Теперь вы строите таблицу символов:

Raw     Encoded
000000  0000000
000001  0000001
...
100000  0100000
1000010 0100001
1000011 0100010
...
1111110 1011101
1111111 1011110

Для кодирования сначала сдвиньте 6 бит ввода. Если эти шесть битов больше или равны 100001, сдвиньте другой бит. Затем найдите соответствующий 7-битный выходной код, переведите его, чтобы уместить в выходном пространстве, и отправьте. Вы будете сдвигать 6 или 7 бит ввода на каждой итерации.

Чтобы декодировать, примите байт и переведите в необработанный выходной код. Если необработанный код меньше 0100001, сдвиньте соответствующие 6 битов на ваш выход. В противном случае сдвиньте соответствующие 7 бит на ваш выход. Вы будете генерировать 6-7 битов вывода на каждой итерации.

Для равномерно распределенных данных я думаю, что это оптимально. Если вы знаете, что в вашем источнике больше нулей, чем единиц, то вам может потребоваться сопоставить 7-битные коды с началом пробела, чтобы более вероятно, что вы можете использовать 7-битный код.

Answer 2

Короткий ответ: нет, все еще нет.

Я столкнулся с проблемой кодирования как можно большего количества информации в строку JSON, то есть UTF-8 без управляющих символов, обратной косой черты и кавычек.

Я вышел и исследовал, сколько бит можно сжать в действительные байты UTF-8. Я не согласен с ответами о том, что UTF-8 приносит слишком много накладных расходов. Это не правда.

Если вы принимаете во внимание только однобайтовые последовательности, это так же мощно, как стандарт ASCII. Значение 7 бит на байт. Но если вы удалите все специальные символы, у вас останется что-то вроде Ascii85.

Но в высших планах меньше управляющих персонажей. Таким образом, если вы используете 6-байтовые чанки, вы сможете кодировать 5 байт на чанк. В выводе вы получите любую комбинацию символов UTF-8 любой длины (от 1 до 6 байтов).

Это даст вам лучший результат, чем Ascii85: 5/6 вместо 4/5, эффективность 83% вместо 80%. Теоретически это будет еще лучше с большей длиной фрагмента: около 84% для 19-байтовых фрагментов.

По моему мнению, процесс кодирования становится слишком сложным, хотя и обеспечивает очень небольшую прибыль. Так что Ascii85 или его модифицированная версия (сейчас я смотрю на Z85 ) будет лучше.

Answer 3

В прошлом году я искал наиболее эффективную кодировку двоичного текста. Я понял для себя, что компактность - не единственный критерий. Наиболее важным является то, где вы можете использовать закодированную строку. Например, yEnc имеет накладные расходы 2%, но это 8-битное кодирование, поэтому его использование очень и очень ограничено.

Мой выбор Z85. Он имеет приемлемые накладные расходы 25%, и закодированная строка может использоваться практически везде: XML, JSON, исходный код и т. Д. См. Z85 спецификация для получения подробной информации.

Наконец, я написал библиотеку Z85 на C / C ++ и использую ее в работе.

Answer 4

Согласно Википедии

basE91 создает кратчайший простой выход ASCII для сжатого 8-разрядного двоичного входа.

Answer 5

В настоящее время base91 - лучшая кодировка, если вы ограничены только символами ASCII и не хотите использовать непечатные символы. Он также обладает преимуществом молниеносной скорости кодирования / декодирования, поскольку может использоваться таблица поиска, в отличие от base85, который должен быть декодирован с использованием медленных делений

Превышение этого значения base122 поможет немного повысить эффективность, но это не 8-битная чистота. Однако, поскольку он основан на кодировке UTF-8, его вполне можно использовать для многих целей. А 8-битная чистота в наше время просто бессмысленна

Base-122 Кодировка

Кодирование Base-122 принимает куски по семь бит входных данных за раз. Если блок отображается на допустимый символ, он кодируется однобайтовым символом UTF-8: 0xxxxxxx. Если блок будет отображаться на недопустимый символ, мы вместо этого используем двухбайтовый символ UTF-8: 110xxxxx 10xxxxxx. Поскольку существует только шесть недопустимых кодовых точек, мы можем различить их только тремя битами. Обозначение этих битов как sss дает нам формат: 110sssxx 10xxxxxx. Оставшиеся восемь битов могут, казалось бы, кодировать больше входных данных. К сожалению, двухбайтовые символы UTF-8, представляющие кодовые точки менее 0x80, недопустимы. Браузеры будут анализировать недопустимые символы UTF-8 в символы ошибок. Простой способ применения кодовых точек, больших 0x80, состоит в использовании формата 110sss1x 10xxxxxx, эквивалентного побитовому ИЛИ с 0x80 (это, вероятно, можно улучшить, см. §4). На рисунке 3 обобщено полное кодирование base-122.

http://blog.kevinalbs.com/base122

Answer 6

Рядом с теми, что перечислены в Википедии , есть Bommanews:

B-News (или bommanews) был разработан для того, чтобы уменьшить нагрузку на кодировку UUEncode и Base64: он использует новый метод кодирования для вставки двоичных данных в текстовые сообщения. Этот метод потребляет больше ресурсов ЦП, но ему удается снизить потери примерно с 40% для UUEncode до 3,5% (десятичная точка между этими цифрами не является грязью на вашем мониторе), при этом избегая использования контрольных кодов ANSI в сообщении корпус.

Это сопоставимо с yEnc: source

yEnc менее загружен процессором, чем B-News, и достигает примерно такого же низкого уровня служебной информации, но он не избегает использования всех управляющих кодов, он просто исключает те, которые (экспериментально) были обнаружены как нежелательные эффекты на некоторых серверах, что означает, что он несколько менее соответствует RFC, чем B-News.

• http://b -news.sourceforge.net /
• http://www.iguana.be/~stef/
• http://bnews -plus.sourceforge.net /

Answer 7

Похоже, у вас уже есть ответ, Марк. UTF-8 бесполезен в качестве двоичного кодирования, поскольку любой символ UTF-8, длина которого превышает один байт, имеет служебную нагрузку более 25% даже для хранения текста (2 или более бит на байт). Base64 кодировки уже лучше.

Answer 8

Если вы ищете эффективную кодировку для больших алфавитов, вы можете попробовать escapeless . И escapeless252, и yEnc имеют накладные расходы 1,6%, но с первым оно исправлено и известно заранее, а с последним оно фактически колеблется от 0 до 100% в зависимости от распределения байтов.

Answer 9

У меня недавно была потребность кодировать двоичный файл как ascii, и это то, что я придумал. Я не знаю, является ли это наиболее эффективным (вероятно, нет), но это просто и быстро. По сути, я кодирую байт как шестнадцатеричный, но вместо использования базового набора (0-9, A-F) я использую (a-p). Поскольку набор непрерывен, он не требует поиска в таблице.

//buff is a unsigned character array containing the binary data
//N is the number of bytes to be encoded 
string simple_encode(unsigned char *buff, int N)
{
    string sEncode = "";
    for(int i = 0; i<N; i++)
    {
        sEncode += (97 + (buff[i] >> 4));
        sEncode += (97 + (buff[i] & 0x0F));
    }
    return sEncode;
}

//sbuff is a string containing the encoded ascii data
//szDecoded is an unsigned char array that has been allocated to 1/2 
//the length of sbuff
//N is an integer pointer and returns the number of converted bytes
void simple_decode(string sbuff, unsigned char *szDecode, int *N)
{
    *N = sbuff.length()/2;
    for(int i=0; i < *N; i++)
    {
        szDecode[i] = ((sbuff.at(2*i)-97) << 4) + (sbuff.at(2*i+1)-97);
    }
}