Преобразование двоичных данных в текст с наименьшими накладными расходами

Двоично-текстовое кодирование с любой системой счисления от 2 до 94

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

Задний план

Основная цель такого конвертера — привести двоичный файл к виду, пригодному для передачи по каналу с ограниченным набором поддерживаемых символов. Хорошим примером является любой текстовый сетевой протокол, такой как HTTP или SMTP, где все передаваемые двоичные данные должны быть обратимо преобразованы в чисто текстовую форму и не должны содержать управляющих символов в составе таких данных. Как известно, коды ASCII от 0 до 31 считаются управляющими символами, и поэтому они обязательно будут потеряны при передаче по любому логическому каналу, который не позволяет конечным точкам передавать полные 8-битные байты (двоичные) с кодами. от 0 до 255.

В настоящее время стандартным решением для этой цели является алгоритм Base64, определенный в RFC 4648 (легкое чтение). Он также описывает Base32 и Base16 как возможные варианты. Ключевой момент здесь: все они имеют одну и ту же характеристику, поскольку все они являются степенями двойки. Чем шире диапазон поддерживаемых символов (кодов), тем более компактным будет результат преобразования. В любом случае он будет больше, но вопрос только в том, насколько больше. Например, кодировка Base64 дает приблизительно на 33 % больше выходных данных, потому что 3 входных (8 битов со значением) байтов преобразуются в 4 выходных (6 битов со значениями, 2⁶=64) байтов. Таким образом, соотношение всегда равно 4/3, то есть выход больше на 1/3 или 33,(3)%. С практической точки зрения, Base32 очень неэффективен, потому что он подразумевает преобразование 5 входных (8 битов со значением) байтов в 8 выходных (5 битов со значением, 2⁵=32) байтов, и соотношение составляет 8/5, то есть выход больше на 3/5 или 60%. В этом контексте трудно рассматривать какую-либо эффективность Base16, так как его выходной размер больше на 100% (каждый байт с 8-значными битами представлен двумя байтами с 4-значными битами, также известными как полубайты, 2⁴= 16). Это даже не перевод, а просто представление 8-битного байта в шестнадцатеричном виде.

Если вам интересно, как эти соотношения входных/выходных байтов были рассчитаны для кодировок Base64/32/16, то ответ — LCM (наименьший общий кратный). Давайте посчитаем их сами, а для этого нам понадобится еще одна функция, GCD (Greatest Common Divisor)

В чем смысл?

Дело в следующем. Что, если канал способен передавать только несколько разных символов, например 9 или 17. То есть у нас есть файл, представленный 256 символами алфавита (обычный 8-битный байт), мы не ограничены вычислительной мощностью или памятью. ограничения обеих сторон, но мы можем отправить только 7 разных символов вместо 256? Base64/32/16 здесь не подходят. Тогда Base7 является единственным возможным выходным форматом.

Другой пример: что, если количество передаваемых данных является проблемой для канала? Base64, как было показано, увеличивает данные на 33% независимо от того, что передается, всегда. Например, Base94 увеличивает производительность всего на 22%.

Может показаться, что Base94 — это не предел. Если первые 32 кода ASCII являются управляющими символами, а всего имеется 256 кодов, что мешает использовать алфавит из 256–32 = 224 символов? Есть причина. Не все из 224 кодов ASCII имеют печатные символы. Как правило, только 7 бит (0..127) стандартизированы, а остальные (128..255) используются для различных локалей, например. Koi8-R, Windows-1251 и т. д. То есть в стандартном диапазоне доступно только 128–32 = 96. Кроме того, код ASCII 32 — это символ пробела, а 127 также не имеет видимого символа. Следовательно, 96–2 дает нам те 94 печатных символа, которые имеют одинаковую связь со своими кодами на всех возможных машинах.

Решение

Это решение довольно простое, но эта простота также накладывает значительные вычислительные ограничения. Весь входной файл можно рассматривать как одно большое число с основанием 256. Это может быть действительно большое число, требующее тысяч битов. Затем нам просто нужно преобразовать это большое число в другое основание. Вот и все. А Python3 делает это еще проще! Обычно преобразования между разными базами выполняются через промежуточную базу 10. Хорошей новостью является то, что Python3 имеет встроенную поддержку вычислений больших чисел (она интегрирована с Int), а класс Int имеет метод, который считывает любое количество байтов и автоматически представляет их в виде большого числа Base10 с желаемым порядком байтов. Таким образом, все эти сложности могут быть реализованы всего в двух строках кода, что довольно удивительно!

with open('inpit_file', 'rb') as f:
    in_data = int.from_bytes(f.read(), 'big')

где in_data — это наше большое число с Base10. Это всего лишь две строки, но именно здесь происходит больше всего вычислений и тратится больше всего времени. Итак, теперь преобразуйте его в любую другую базу, как это обычно делается с обычными маленькими десятичными числами.

Первоначально опубликовано наhttps://vorakl.com/articles/base94/