9

我想在 XML 文件中编码和解码二进制数据（使用 Python，但无论如何）。我必须面对 XML 标记内容包含非法字符的事实。XML 规范中描述了唯一允许的：

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 )
  • <, >, & 根据这篇文章获取实体内容

1 个字节可以编码 256 种可能。有了这些限制，第一个字节被限制为 256-29-8-1-3 = 215 possiblities。

在第一个字节的 215 个可能性中，base64仅使用 64 个可能性。Base64 产生 33% 的开销（使用 base64 编码后，6 位变为 1 字节）。

所以我的问题很简单：有没有比 base64 更有效的算法来编码 XML 中的二进制数据？如果没有，我们应该从哪里开始创建它？（图书馆等）

注意：您不会通过“您不应该使用 XML 来编码二进制数据，因为......”来回答这篇文章。只是不要。您最多可以争论为什么不使用 215 种可能性来支持糟糕的 XML 解析器。

NB2：我不是在谈论第二个字节，但是当我们使用补充 Unicode 平面时，wa 可以开发一些关于可能性数量以及它应该以 10xxxxxx 开头以尊重 UTF8 标准的事实（如果不是呢？ ）。

4

3 回答 3

8

感谢 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 字节字符 (110xxxxxx 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 101xxxxxx 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) 的平均“有用性”。

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

我们需要构建一个“字典”，它将“可能的空间”（长度为 5、10、20 或 21 位的随机位序列，取决于为算法选择的编码长度 - 只需选择一个）映射到 utf8-兼容序列（相应的长度为 6、12、24 或 25 位的 utf8 位序列）。

最简单的起点是将 20 位序列编码为 24 位兼容的 UTF-8 序列：这正是上面用于计算可能性的示例，它有 3 个 UTF-8 字节长（所以我们不必担心未终止UTF8 字符）。

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

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

一种算法的提议，我将 XML 命名为 BaseUTF-8

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 的倍数时，该算法还没有提供管理字符串终止的方法。还必须提供解码算法，但这很容易（只是不要忘记抛出异常强制解码的唯一性）。

于 2013-06-27T22:56:18.477 回答
2

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

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

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

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

如果需要，我可能会在稍后发布“for XML1.1”版本（它也是二进制安全的，并且有 14.7% 的开销），它已经准备好并且确实可以工作，但对于 Python 内置的 XML 解析器没有用，所以我不想用太多版本混淆人们（还）。

于 2013-07-04T22:11:24.433 回答
1

比这更糟糕的是：您实际上并没有可以使用的 215 个不同的字节值。生成的二进制数据必须在 XML 表示的任何编码中都有效（几乎可以肯定是 UTF-8），这意味着很多很多字节序列都是被禁止的。0xc2 后跟 0x41 只是一个随机示例。XML 是文本（Unicode 字符序列），而不是二进制数据。传输时，它使用某种编码（几乎总是 UTF-8）进行编码。如果您尝试将其视为二进制数据，那么在我看来，您所要求的麻烦比它值得处理的要多得多。

如果你还想这样做...

XML 是文本。因此，我们不要尝试将二进制数据编码为二进制数据。这不会导致一种简单或明显的方式将其显示为 XML 文档。让我们尝试将二进制数据编码为文本！

让我们尝试一种非常简单的编码：

  • 将二进制数据分组为 20 位的块
  • 将每组 20 位编码为 Unicode 字符 U+10000 加上 20 位的数值。

这意味着您只能使用平面 1 到 16 中的字符。所有受限制的字符都在平面 0（BMP）中，因此您在这里是安全的。

然后，当您将此 XML 文档编码为 UTF-8 以进行传输时，这些字符中的每一个都需要 4 个字节进行编码。因此，每 20 位原始数据消耗 32 位，与原始数据的纯二进制编码相比，这是 60% 的开销。这比 base64 的 33% 差，这使它成为一个糟糕的主意。

这种编码方案有点浪费，因为它没有使用 BMP 字符。我们可以使用 BMP 字符使其更好吗？不是微不足道的。20 是我们可以用于组的最大大小 ( log(0x10FFFF) ~ 20.09)。我们可以重新映射方案以尽可能使用一些手动 BMP 字符，因为这些使用 UTF-8 编码占用的空间更少，但这不仅会使编码复杂很多（禁止字符分散，所以我们有几种情况要处理) 但它只能改善大约 6.25% 的位模式（BMP 中的 Unicode 字符的一部分），而对于这 6.25% 的大部分，我们只会节省一个字节。对于随机数据，开销从 60% 降低到 55% 左右。结果还是会比base64差很多，除了一些非常做作的数据. 请注意，开销取决于数据。对于 0.2% 的位模式，您实际上将获得压缩而不是开销（0.012% 的模式压缩为 60%，0.18% 的模式压缩为 20%）。但是这些分数真的很低。这不值得。

换句话说：如果您想使用 4 字节 UTF-8 序列对任何内容进行编码，则每个序列需要使用 32 位（当然），但其中 11 位是固定且不可更改的：这些位必须符合模式11110xxx 10xxxxxx 10xxxxxx 10xxxxxx并且那里只有 21x秒）。UTF-8 内置了 60% 的开销，因此，如果您想将其用作任何改进 base64 开销的编码的基础，那么您从后面开始！

我希望这能让你相信，使用任何这种类型的方案都无法提高 base64 的密度。

于 2013-06-25T17:37:21.160 回答