在XML中编码二进制数据:是否有比base64更好的替代方案？

Question

我想在XML文件中编码和解码二进制数据(使用Python,但无论如何).我必须面对XML标记内容具有非法字符的事实.XML规范中描述了唯一允许的:

Char ::= #x9 | #xA | #xD | [#x20-#xD7FF] | [#xE000-#xFFFD] | [#x10000-#x10FFFF]

这意味着不允许的是:

• 29个Unicode控制字符是非法的(0x00 - 0x20)即(000xxxxx),除了0x09,0x0A,0x0D
• 任何超过2个字节的Unicode字符表示(UTF-16 +)都是非法的(U + D800 - U + DFFF)即(11011xxx)
• 特殊的Unicode非字符是非法的(0xFFFE - 0xFFFF)即(11111111 1111111x)
• <,>,&根据这篇文章了解实体内容

1个字节可以编码256种可能.通过这些限制,第一个字节限制为256-29-8-1-3 = 215个可能性.

在第一个字节的215个可能性中,base64仅使用64个可能性.Base64产生33%的开销(一旦用base64编码,6位变为1字节).

所以我的问题很简单:是否有一种比base64更有效的算法来编码XML中的二进制数据？如果没有,我们应该从哪里开始创建它？(图书馆等)

注意:你不会回答这个帖子"你不应该使用XML来编码二进制数据,因为......".只是不要.您最多可以争论为什么不使用215种不良XML解析器支持的可能性.

NB2:我不是在谈论第二个字节,但是当我们使用补充的Unicode平面时,肯定会有一些关于可用性的因素以及它应该从10xxxxxx开始遵守UTF8标准的事实(如果不是,那么？ ).

Answer 1

谢谢Aya的Asci85链接,有很好的想法.

我为我们的案例开发了它们.

UTF-8字符可能性:

对于1个字节的字符(0xxxxxxx):每个字节有96个可能字符

• + UTF-8 ASCII字符0xxxxxxx = + 2 ^ 7
• - UTF-8控制字符000xxxxx = -2 ^ 5
• + XML允许UTF-8控制字符(00000009,0000000A,0000000D)= +3
• - XML实体不允许的字符(<,>,&)= -3

编辑:这是针对XML1.0规范.XML 1.1规范允许使用除0x00之外的控制字符...

对于2字节字符(110xxxxx 10xxxxxx):每2字节1920个可能性

• + UTF-8 2字节字符110xxxxx 10xxxxxx = + 2 ^ 11
• - UTF-8非法非规范字符(1100000x 10xxxxxx)= -2 ^ 7

对于3字节字符(1110xxxx 10xxxxxx 10xxxxxx):每3字节61440个可能性

• + 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字符.

可编程的可能性就是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字节的字符结尾或者在空格中开始,但是像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%开销!

编辑:这是针对XML1.0规范.使用XML1.1(不广泛支持...),理论开销为12.55%.我设法为XML1.1制作了一个二进制安全算法,其开销为14.7%.

如何接近这18%的开销？

坏消息是,如果不使用大型"词典"(即长期插入集合),我们就不能轻易获得18%的成功率.但它很容易获得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)

注意:0,84是空格位(20,32/24)的平均"有用性".

如何构建我们的编码算法？

我们需要构建一个"dictionnary",它将"空间可能"(长度为5,10,20或21位的比特序列,取决于所选择的算法编码长度 - 只需选择一个)映射到utf8-兼容序列(utf8位序列,其长度分别为6,12,24或25位).

最简单的起点是将20位序列编码为24位兼容的UTF-8序列:这正是上面计算可能性的例子,而且是3 UTF-8字节长(所以我们不必担心未终止UTF8字符).

请注意,我们必须使用2字节(或以上)UTF-8字符编码空间来达到20%的开销.只有1字节长的UTF8字符,我们只能通过RADIX-24达到25%的开销.但是,3字节长的UTF-8字符无需达到20%的开销.

这是这个问题的下一个挑战.谁想玩？:)

算法提议,我将其命名为BaseUTF-8 for XML

要编码的20个二进制位:ABCDEFGHIJKLMNOPQRST

产生的名为"encoded"的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的倍数时,此算法不提供管理字符串终止的方法.还必须提供解码算法,但这很容易(只是不要忘记将异常强加给力)解码的独特性).

Answer 2

我已经用 C 代码开发了这个概念。

该项目位于 GitHub 上，最终名为 BaseXML： https: //github.com/kriswebdev/BaseXML

它有 20% 的开销，这对于二进制安全版本来说是很好的。

我很难让它与 Expat 一起工作，Expat 是 Python 的幕后 XML 解析器（不支持 XML1.1！）。因此，您将找到 XML1.0 的 BaseXML1.0 二进制安全版本。

如果需要的话，我可能会稍后发布“for XML1.1”版本（它也是二进制安全的，并且有 14.7% 的开销），它已经准备好并且确实可以工作，但对于 Python 内置 XML 解析器来说毫无用处，所以我不想太多的版本让人们感到困惑（到目前为止）。