嵌套编码效率

Posted on 2022-12-27

您希望通过受限通道发送数据是比较常见的。例如，URL 路径不能包含?或空字节。一个常见的解决方案是使用某种编码格式将您的数据转换为可接受的字符串。

Base64

Base64是一种非常常见的格式。它可以将任意二进制数据转换为 64 个字符的字母表（如果需要，加上一个额外的字符用于填充）。 

 b64_encode ([ 'a' , '?' , 0 , 'b' , ' ' , 0xFF ]) == "YT8AYiD/"

使用 Base64，输出总是比输入长（空字符串除外）。事实上输出长度很容易预测。 

 # Assumes no padding. def b64_length ( in : bytes ) -> int : complete_chunks = len ( in ) // 3 remainder = len ( in ) % 3 complete_encoded = complete_chunks * 4 remainder_encoded = 0 if remainder == 0 else remainder + 1 return complete_encoded + remainder_encoded

余数最多为 3 个字节，因此我们可以说随着输入数据变大，比率接近 4/3。因此，将数据编码为 Base64 或多或少会使其变大 1/3。

Base64 采用一种非常简单的编码方法，它需要 3 个输入字节并将其映射到 4 个输出字节。冲洗并重复直到完成（对于任何不适合 3 字节块的剩余部分都有一些特殊的逻辑）。这简单、快速且可预测，但输出看起来像 nonsense cat变成Y2F0并且hello变成aGVsbG8 。如果您希望人类可读的字符串保持人类可读怎么办？

C 字符串转义

C 风格的字符串转义非常简单。您有一些按字面输入的“允许”字符集，其他任何内容都需要“转义”。 

 c_encode ([ 'a' , '?' , 0 , 'b' , ' ' , 0xFF ]) == "a? \x00b \xFF "

任何不允许的字节都被反斜杠-x ( \x ) 替换，然后是该字节的十六进制表示。在实践中，大多数实现都有常用字符的快捷方式。例如， \\表示反斜杠， \0表示空字节。用手阅读和书写很容易。

那么这种编码的效率如何呢？这要看情况。如果你只编码允许的字符，它的比率是 1，如果你只编码有快捷方式的字符，它是 2，但如果你只编码没有快捷方式的不允许的字符，它是 4！与 Base64 不同，编码效率取决于数据。

但我觉得有趣的是嵌套编码的缩放。例如，假设我想对单个空字节进行编码，然后对结果进行编码，然后再次对结果进行编码……

  1. \0 （2 个字节）
  2. \\0 （3 个字节）
  3. \\\\0 （5 个字节）
  4. \\\\\\\\0 （9 个字节）
  5. \\\\\\\\\\\\\\\\0 （17 字节）
  6. \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\0 （33 字节）

重复编码往往会使大小加倍！这似乎不是最佳选择。你会希望这种情况很少见，但如果我每次看到 JSON 编码在 JSON 字符串中时得到 1 美元，我就可以给自己买一些不错的东西。

百分比编码

百分比编码最常用于 URL。它类似于 C 字符串转义，只是它没有元字符本身的快捷方式。 

 percent_encode ([ 'a' , '?' , 0 , 'b' , ' ' , 0xFF ]) == "a?%00b %FF" percent_encode ([ '%' ]) == "%25"

它也依赖于数据。它的大小比在 1 到 3 之间变化。但是，嵌套编码没有那么大的问题。

  1. %00 （3 个字节）
  2. %2500 （5 个字节）
  3. %252500 （7 个字节）
  4. %25252500 （9 个字节）
  5. %2525252500 （11 个字节）
  6. %252525252500 （13 字节）

由于编码不会添加需要在每次迭代中转义增长的额外字符，因此增长是一个常数因子，基于初始字符串中需要编码而不是每次加倍的字符数。

我们能做得更好吗？

进行微小的改进很容易。在 C 风格的编码中使用\.而不是\\来代表\会避免这个问题。可以通过为常见字符添加快捷方式（例如%p而不是%25 ）来稍微优化百分比编码，但代价是复杂性和性能。

元字符切换

一个想法是可变元字符。例如，想象将"'\编码为\"\'\\ 。想象一下，然后我们可以做\1\"\'\\来表示元字符现在是1而不是\ 。这将避免向字符串的其余部分添加字符，在这个例子中它已经保存了一个字符。

主要缺点是您需要选择以下弊端之一：

  1. 放弃流媒体支持。
  2. 允许元字符切换发生在流中的任何位置。
  3. 接受你可能不会选择最好的元字符。

不可怕但不伟大也不漂亮。

编码级别

另一个想法是在消息的开头声明“编码级别”。遇到这种情况时，解码器只会递减计数器并通过数据不变。

例如，想象一下 base64 的修改。

  1. Y2F0
  2. =1=Y2F0
  3. =2=Y2F0
  4. =3=Y2F0

这基本上与第一种方法存在相同的问题，并且需要您向字母表中添加另一个字符或要求始终声明嵌套级别（这会增加非嵌套编码的开销）。

研究？

我试着环顾四周，但找不到任何其他关于此的讨论。我可能使用了错误的关键字。如果您知道任何考虑过此问题的编码系统，请告诉我。

原文： https://kevincox.ca/2022/12/26/nested-encoding-efficency/