Кодирование двоичных строк в произвольные алфавиты

Question

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

У меня нет полностью сформулированного вопроса, но мне интересно, можете ли вы преобразовать произвольно длинную двоичную строку в некоторый алфавит без необходимости считывания всей строки в память .Причина, по которой этот вопрос не полностью сформирован, заключается в том, что я не совсем уверен, что обычно do считывает всю строку в память для создания закодированной версии.

Итак, если у вас есть что-то вроде этого:

... 10 ^ 50 длиннее

Что-то вроде всего генетического кода или миллиона миллиардов разэто значит, что он будет слишком большим для чтения в память и слишком медленным, чтобы ожидать динамического создания его кодировки в шестнадцатеричный формат, если вам придется поточить весь объект через память, прежде чем вы сможете выяснить окончательное кодирование.

Так что мне интересно три вещи:

1. Если вам нужно прочитать что-то полностью, чтобы закодировать его в какой-то другой алфавит.
2. Если вы do , тогда почему это так.
3. Если нет, то как это работает.

Причина, по которой я спрашиваю, заключается в том, что я смотрю настрока типа 1010101, если бы я закодировал ее как шестнадцатеричный код, есть несколько способов:

1. Один символ за раз, поэтому он по существу останется 1010101, если алфавит не будет {a, b} тогда это будет abababa.Это лучший случай, потому что вам не нужно читать что-либо больше чем 1 символ в память, чтобы выяснить кодировку.Но это ограничивает вас двухсимвольным алфавитом.(Что-нибудь больше чем 2 алфавита символов, и я начинаю путаться)
2. Превращая это в целое число, затем преобразовывая это в шестнадцатеричное значение.Но это потребует чтения всего значения для вычисления окончательного (большого) целочисленного размера.Так вот где я запутался.

Мне кажется, что третий способ (3) - это читать частичные порции входных байтов каким-то образом, например 1010 затем 010, но это не сработало бы, если бы кодировкой были целые числа, потому что 1010 010 = A 2 в шестнадцатеричном виде, но 2 = 10 не 2 = 010.Так что вам нужно разбить его, добавив 1 в начале каждого куска.Но что если вы хотите, чтобы каждый кусок не превышал 10 шестнадцатеричных символов, но у вас была длинная строка 1000 0, то вам нужен другой трюк, например, когда закодированное шестнадцатеричное значение говорит вам, сколько предшествующих нулейу вас есть, и т. д. Таким образом, кажется, что это становится сложным, интересно, есть ли уже какие-то системы, которые выяснили, как это сделать.Отсюда и вышеприведенные вопросы.

Например, скажем, я хотел закодировать приведенную выше двоичную строку в 8-битный алфавит, как в ASCII.Тогда я мог бы иметь aBc?D4*&((!....Но затем десериализовать это в биты - это одна часть, а сериализовать биты в это - другая (эти символы не являются фактическими символами, сопоставленными с приведенным выше примером битов).

Answer 1

Но что если вы хотите, чтобы каждый кусок был не длиннее 10 шестнадцатеричных символов, но у вас есть длинная строка 1000 0, то вам нужен другой трюк, например, закодированное шестнадцатеричное значение, сообщающее вам, сколькопредыдущие нули, которые у вас есть, и т. д. Таким образом, кажется, что это становится сложным, интересно, есть ли уже установленные системы, которые выяснили, как это сделать

Да, вы слишком усложняете это.Для начала рассмотрим строки битов, длина которых по определению кратна 4. Они могут быть представлены в шестнадцатеричном виде, просто сгруппировав биты в 4 и переназначив их в шестнадцатеричные цифры:

raw:   11011110101011011011111011101111
group: 1101 1110 1010 1101 1011 1110 1110 1111
remap: D    E    A    D    B    E    E    F

Итак 11011110101011011011111011101111 -> DEADBEEF.То, что у всех грызунов был установлен верхний бит, было совпадением в результате выбора примера таким образом. По определению вход делится на группы по четыре, и каждая шестнадцатеричная цифра впоследствии декодируется в группу из четырех битов, включая начальные нули, если это применимо.Это все, что вам нужно для типичных хеш-кодов, кратных 4 битам.

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

Например, оставляя в стороне механизм, который передает количество битов заполнения, мы могли бы закодировать 1010101 как A5 или AA или 5A (и более!) в зависимости от местоположения, которое мы выбираем для заполнения, в зависимости от того, какое соглашение мы выбираем, декодер должен знать, что существует 1 бит заполнения.Чтобы вернуть это обратно в виде битов, 1010101 может быть закодирован как любой из них:

x101 0101
101x 0101
1010 x101
1010 101x

Где x обозначает бит, который вставляется в кодер и сбрасывается в декодере.Значение этого бита на самом деле не имеет значения, потому что он отбрасывается, поэтому DA также является точной кодировкой и т. Д.

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

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