Что такое наиболее эффективная бинарная кодировка?

Question

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

Answer 1

Для вдохновения вы можете проверить the Twitter Image Encoding Challenge. Речь идет о кодировании как можно большего количества информации об изображении в 140 символах Юникода. Это, по сути, версия с потерями вашего вопроса, специально связанная с данными изображения.

Answer 2

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

Прежде всего, если ваши двоичные данные не сжаты, попробуйте выполнить сжатие перед кодированием. Мы можем тогда предположить, что распределение 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 бит. Если у нас есть 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 3

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

Answer 4

В соответствии с Wikipedia "basE91 производит самый короткий простой выход ASCII для сжатого 8-битного двоичного входа"

Answer 5

Рядом с теми, что перечислено на Wikipedia, есть Bommanews:

B- Новости (или 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 6

Короткий ответ был бы: нет, там до сих пор нет.

Я столкнулся с проблемой кодирования как можно больше информации в строку 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 7

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

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

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

Answer 8

Мне недавно пришлось кодировать двоичный файл как 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); 
    } 
}