Кодирование двоичных данных в XML: Существуют ли лучшие альтернативы, чем base64?

Ответ 1

Я разработал концепцию в коде C.

Проект находится на GitHub и, наконец, называется BaseXML: https://github.com/kriswebdev/BaseXML

У этого есть 20% накладных расходов, что хорошо для двоичной безопасной версии.

Мне было трудно заставить его работать с Expat, который находится за парсером XML-анализатора Python (ЭТО НЕ ПОДДЕРЖИВАЕТ XML1.1!). Таким образом, вы найдете бинарную безопасную версию BaseXML1.0 для XML1.0.

Возможно, я выпущу версию "для XML1.1" позже, если будет запрошена (она также будет бинарной и будет иметь 14,7% накладных расходов), она готова и работает действительно, но бесполезна с встроенными анализаторами XML на Python, t хотите запутать людей со слишком многими версиями (пока).

Ответ 2

Спасибо Aya за ссылку Asci85, есть очень хорошие идеи.

Я разработал их ниже для нашего случая.

Возможны символы UTF-8:

Для 1 байтовых символов (0xxxxxxx): 96 возможных в байтах

• + UTF-8 ASCII chars 0xxxxxxx = + 2 ^ 7
• - UTF-8 Контрольные символы 000xxxxx = -2 ^ 5
• + XML разрешает символы управления UTF-8 (00000009, 0000000A, 0000000D) = +3
• - XML-объект не разрешенных символов (<, > , &) = -3

EDIT: это для спецификаций XML1.0. Спецификации XML 1.1 позволяют использовать контрольные символы, кроме 0x00...

Для двухбайтовых символов (110xxxxx 10xxxxxx): 1920 возможных за 2 байта

• + UTF-8 2-байтовые символы 110xxxxx 10xxxxxx = + 2 ^ 11
• - UTF-8 незаконные неканонические символы (1100000x 10xxxxxx) = -2 ^ 7

Для 3-байтных символов (1110xxxx 10xxxxxx 10xxxxxx): 61440 возможностей на 3 байта

• + UTF-8 3-байтовые символы 1110xxxx 10xxxxxx 10xxxxxx = + 2 ^ 16
• - Незаконные неканонические символы UTF-8 (11100000 100xxxxx 10xxxxxx) = -2 ^ 11
• - Unicode зарезервированные коды UTF-16 (11101101 101xxxxx 10xxxxxx) = -2 ^ 11

И я не буду делать вычисления для 4-байтных символов, что бессмысленно: количество возможных вариантов будет незначительным, и в этом диапазоне слишком много незаконных символов UTF-8.

Возможно использование кодирования в let 3-байтового пространства

Итак, посмотрим, какие комбинации мы можем сделать в 3-байтовом (24-битном) пространстве:

• 0xxxxxxx 0xxxxxxx 0xxxxxxx: Это 96 * 96 * 96 = 884736 возможностей
• 0xxxxxxx 110xxxxx 10xxxxxx: Это 96 * 1920 = 184320 возможностей
• 110xxxxx 10xxxxxx 0xxxxxxx: что 1920 * 96 = 184320 возможностей
• 1110xxxx 10xxxxxx 10xxxxxx: что 61440 = 61440 возможностей

Были бы другие возможности (например, 3 байта char, заканчивающиеся или начинающиеся в пространстве, но как 4-байтовые символы, которые было бы трудно оценить (для меня) и, вероятно, незначительно).

Общее количество возможностей:

• 3-байтовое пространство имеет 2 ^ 24 = 16777216 возможности.
• UTF-8 СОВМЕСТИМЫЕ возможности в этом пространстве - это 884736 + 2 * 184320 + 61440 = 1314816 возможностей.

Сколько накладных расходов это означает?

• 24-разрядные используемые двоичные разряды: Log2 (16777216) = 24 (конечно, что для понимания математики)
• Это пространство полезных битов UTF-8: Log2 (1314816) = 20,32 полезных бита.
• Это означает, что нам нужно 24 бит пространства для кодирования 20,32 бит полезной информации, т.е. минимальные теоретические накладные расходы 18% overhead. Лучше, чем Base64 33% накладных расходов и Ascii85 25% накладных расходов!

EDIT: это для спецификаций XML1.0. С XML1.1 (не широко поддерживается...) теоретические накладные расходы составляют 12,55%. Мне удалось создать двоичный безопасный алгоритм с 14,7% накладных расходов для XML1.1.

Как приблизиться к этим 18% -ным накладным расходам?

Плохая новость заключается в том, что мы не можем легко получить это 18% ovearhead, не используя большой "dictionnary" (т.е. длинные блокировки). Но он легко получить 20%, и довольно легко, но менее практично получить 19%.

Хорошие кандидаты на длину кодирования:

• 6 бит могут кодировать 5 бит с 20% служебными данными (2 ^ (6 * 0,84) > 2 ^ 5)
• 12 бит могут кодировать 10 бит с 20% служебными данными (2 ^ (12 * 0,84) > 2 ^ 10)
• 24 бита могут кодировать 20 бит с 20% служебными данными (2 ^ (24 * 0,84) > 2 ^ 20)
• 25 бит могут кодировать 21 бит с 19% служебными данными (2 ^ (25 * 0,84) > 2 ^ 21)

NB: 0,84 - средняя "полезность" пробельного бита (20,32/24).

Как построить наш алгоритм кодирования?

Нам нужно построить "dictionnary", который отобразит "пробелы" (последовательность randoms битов, длина которых составляет 5, 10, 20 или 21 бит в зависимости от выбранной длины кодирования для алгоритма - просто выберите один) в совместимые с utf8 последовательности (последовательность бит utf8, длина которой равна 6, 12, 24 или 25 бит соответственно).

Простейшей отправной точкой будет кодирование последовательности из 20 битов в 24-битные совместимые последовательности UTF-8: это именно тот пример, который был взят выше, чтобы вычислить возможности и что 3 байта UTF-8 (поэтому нам не придется беспокоиться о unterminated символы UTF8).

Обратите внимание, что мы ДОЛЖНЫ ИСПОЛЬЗОВАТЬ 2-байтовое (или выше) кодированное пространство символов UTF-8, чтобы достичь 20% -ной накладной. Только с 1-байтным символом UTF8 мы можем достичь 25% накладных расходов с помощью RADIX-24. Однако 3-байтовые символы UTF-8 бесполезны для достижения 20% -ной накладной.

Это следующая задача для этого вопроса. Кто хочет играть?:)

Предложение алгоритма, я назову BaseUTF-8 для XML

20 двоичных битов для кодирования: ABCDEFGHIJKLMNOPQRST

Результирующая строка UTF-8 с именем "закодированная": длина 24 бит

Алгоритм математического кодирования (не основанный на любом известном языке программирования):

If GH != 00 && NO != 00:
    encoded = 01ABCDEF 0GHIJKLM 0NOPQRST # 20 bits to encode, 21 space bits with restrictions (1-byte UTF-8 char not starting by 000xxxxx ie ASCII control chars)

If ABCD != 0000:
    If GH == 00 && NO == 00: # 16 bits to encode
        encoded = 0010ABCD 01EFIJKL 01MPQRST    
    Else If GH == 00:  # 18 bits to encode, 18 space bits with restrictions (1-byte  UTF-8 ASCII control char, 2-bytes UTF-8 char noncanonical)
        encoded = 0NOFIJKL 110ABCDE 10MPQRST
    Else If NO == 00:  # 18 bits to encode
        encoded = 110ABCDE 10MPQRST 0GHFIJKL

If ABCD == 0000: # 16 bits to encode
    encoded = 0011EFGH 01IJKLMN 01OPQRST

On "encoded" variable apply:
    convert < (0x3C) to Line Feed (0x0A)
    convert > (0x3E) to Cariage Return (0x0D)
    convert & (0x26) to TAB (0x09)

И как вы получите только 20% накладных расходов.

Этот алгоритм еще не дает возможности управлять завершением строки, когда строка для кодирования не кратна 20. Алгоритм декодирования также должен быть предоставлен, но это довольно просто (просто не забудьте бросить исключения для принудительного единства декодирования).

Ответ 3

Это хуже, чем у вас: у вас на самом деле нет 215 различных байтовых значений, которые вы можете использовать. Результирующие двоичные данные должны быть действительными в любой кодировке, представленной XML (что почти наверняка означает UTF-8), что означает, что многие, многие байтовые последовательности запрещены. 0xc2, за которым следует 0x41, будет всего лишь одним случайным примером. XML - это текст (последовательность символов Юникода), а не двоичные данные. При передаче он кодируется с использованием некоторой кодировки (что почти соответствует UTF-8). Если вы попытаетесь рассматривать его как двоичные данные, то вы, на мой взгляд, задаете себе больше проблем, чем это стоит.

Если вы все еще хотите это сделать...

XML - это текст. Поэтому не пытайтесь кодировать двоичные данные в виде двоичных данных. Это не приведет к простому или очевидному способу показать его в XML-документе. Попробуйте вместо этого кодировать ваши двоичные данные как текст!

Попробуйте одну очень простую кодировку:

• Группируйте свои двоичные данные в блоки по 20 бит
• Кодировать каждую группу из 20 бит как символ Юникода U + 10000 плюс числовое значение 20 бит.

Это означает, что вы используете исключительно символы из плоскостей с 1 по 16. Все ограниченные символы находятся в плоскости 0 (BMP), поэтому вы здесь в безопасности.

Когда вы затем кодируете этот XML-документ как UTF-8 для передачи, каждому из этих символов потребуется 4 байта для кодирования. Таким образом, вы потребляете 32 бита для каждых 20 бит исходных данных, что на 60% выше, чем чистая двоичная кодировка исходных данных. Это хуже, чем base64 33%, что делает его ужасной идеей.

Эта схема кодирования немного расточительна, потому что она не использует символы BMP. Можем ли мы использовать символы BMP, чтобы сделать их лучше? Не тривиально. 20 - наибольший размер, который мы можем использовать для групп (log(0x10FFFF) ~ 20.09). Мы могли бы переназначить схему, чтобы использовать некоторые из них как персонажи BMP-персонажа, потому что они занимают меньше места для кодирования с UTF-8, но это не только усложнит кодировку (запрещенные символы будут разбросаны, поэтому у нас есть несколько дел для обработки), но это может привести только к улучшению порядка 6,25% битовых шаблонов (доля символов Юникода, которые находятся в BMP), и для большей части этого 6,25% мы сохранили бы только один байт. Для случайных данных накладные расходы снижаются с 60% до 55%. Результат будет намного хуже, чем base64, за исключением некоторых очень надуманных данных. Обратите внимание, что накладные расходы зависят от данных. Для 0,2% битовых шаблонов вы фактически получите сжатие вместо накладных расходов (60% сжатия для 0,012% шаблонов и 20% сжатия для 0,18% шаблонов). Но эти фракции действительно низки. Это просто не стоит.

Иными словами, если вы хотите кодировать что-либо с помощью 4-байтовых последовательностей UTF-8, вам нужно использовать 32 бита на последовательность (конечно), но 11 из этих бит являются фиксированными и неизменяемыми: бит должен соответствовать шаблон 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx и там всего 21 x). Это накладные расходы на 60% встроены в UTF-8, поэтому, если вы хотите использовать это как основу любой кодировки, которая улучшается при накладных расходах base64, вы начинаете сзади!

Надеюсь, это убедит вас в том, что вы не можете улучшить плотность base64, используя любую схему этого типа.