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

前端之家收集整理的这篇文章主要介绍了在XML中编码二进制数据:是否有比base64更好的替代方案?前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
我想在XML文件中编码和解码二进制数据(使用Python,但无论如何).我必须面对XML标记内容具有非法字符的事实.唯一允许的是在 XML specs中描述的:
Char ::= #x9 | #xA | #xD | [#x20-#xD7FF] | [#xE000-#xFFFD] | [#x10000-#x10FFFF]

这意味着不允许的是:

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

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标准的事实(如果没有,那么? ).

谢谢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 specs允许使用除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%的开销.比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位).

最简单的起点是长度为20bits的编码序列插入到24位兼容UTF-8的序列:这正是上面采取计算possibilites的例子,这就是3 UTF-8字节长(因此我们将不必担心未端接UTF8字符).

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

这是这个问题的下一个挑战.谁想玩?

猜你在找的XML相关文章