什么是文本编码最有效的二进制文件？

Question

到目前为止,我能找到的最接近的竞争者是yEnc(2%)和ASCII85(25%的开销).yEnc似乎存在一些问题,主要是因为它使用的是8位字符集.这引出了另一个想法:是否存在基于UTF-8字符集的二进制文本编码？

Answer 1

这实际上取决于二进制数据的性质以及"文本"对输出的约束.

首先,如果您的二进制数据未压缩,请在编码前尝试压缩.然后我们可以假设1/0或单个字节的分布或多或少是随机的.

现在:你为什么需要文字？通常,这是因为通信通道不会平等地通过所有字符.例如,您可能需要纯ASCII文本,其可打印字符范围为0x20-0x7E.你有95个字符可供玩耍.理论上,每个字符可以编码每个字符的log2(95)〜= 6.57位.定义一个非常接近的变换很容易.

但是:如果你需要一个分隔符,该怎么办？现在你只有94个字符等.所以编码的选择实际上取决于你的要求.

举一个非常愚蠢的例子:如果你的频道通过所有256个字符没有问题,并且你不需要任何分隔符,那么你可以编写一个平凡的变换,实现100%的效率.:-)如何做到这一点留给读者练习.

UTF-8不是任意编码二进制数据的良好传输.它能够传输值0x01-0x7F,只有14%的开销.我不确定0x00是否合法; 可能不是.但是,任何高于0x80的内容都会扩展为UTF-8中的多个字节.我将UTF-8视为传递0x01-0x7F或126个唯一字符的约束通道.如果您不需要分隔符,则每个字符可以传输6.98位.

该问题的一般解决方案:假设N个字符的字母表,其二进制编码为0到N-1.(如果编码不是假定的,那么使用查找表在我们的中间0..N-1表示与您实际发送和接收的表示之间进行转换.)

假设字母表中有95个字符.现在:其中一些符号代表6位,有些代表7位.如果我们有一个6位符号和B 7位符号,那么:

A + B = 95(符号总数)2A + B = 128(可以进行7位前缀的总数.您可以使用6位符号开始2个前缀,或者使用7位符号开始. )

求解系统得到:A = 33,B = 62.您现在构建一个符号表:

__PRE__

要进行编码,首先要关闭6位输入.如果这六位大于或等于100001,则移位另一位.然后查找相应的7位输出代码,转换为适合输出空间并发送.每次迭代,您将移动6或7位输入.

要解码,接受一个字节并转换为原始输出代码.如果原始代码小于0100001,则将相应的6位移到输出上.否则将相应的7位移到输出上.每次迭代,您将生成6-7位输出.

对于均匀分布的数据,我认为这是最佳的.如果您知道源中的零比零多,则可能需要将7位代码映射到空间的开头,以便更有可能使用7位代码.

Answer 2

简短的回答是:不,仍然没有.

我遇到了将尽可能多的信息编码到JSON字符串中的问题,这意味着没有控制字符,反斜杠和引号的UTF-8.

我出去研究了你可以挤进有效的UTF-8字节多少位.我不同意答案,说明UTF-8带来了太多的开销.这不是真的.

如果只考虑一个字节的序列,它就像标准ASCII一样强大.含义每字节7位.但如果你删掉所有特殊字符,你会留下类似Ascii85的东西.

但是在更高的平面中控制字符更少.因此,如果您使用6字节块,您将能够编码每个块5个字节.在输出中,您将获得任意长度的UTF-8字符的任意组合(1到6个字节).

这将给你一个比Ascii85更好的结果:5/6而不是4/5,83%效率而不是80%.从理论上讲,块长度越大,效果越好:19字节块大约为84%.

在我看来,编码过程变得太复杂,而它提供的利润很少.所以Ascii85或它的一些修改版本(我现在正在看Z85)会更好.

Answer 3

根据维基百科

basE91为压缩的8位二进制输入生成最短的纯ASCII输出.

Answer 4

我去年搜索了最有效的二进制文本编码.我意识到紧凑性不是唯一的标准.最重要的是您可以使用编码字符串.例如,yEnc有2%的开销,但它是8位编码,因此它的使用非常有限.

我的选择是Z85.它可以承受25%的开销,编码字符串几乎可以在任何地方使用:XML,JSON,源代码等.有关详细信息,请参阅Z85 规范.

最后,我用C/C++ 编写了Z85 库并在生产中使用它.

Answer 5

目前，如果您仅限于 ASCII 字符并且不想使用不可打印的字符，那么base91是最佳编码。它还具有闪电般快速编码/解码速度的优点，因为可以使用查找表，这与必须使用慢速除法进行解码的 base85 不同

\n

高于该base122将有助于稍微提高效率，但它不是 8 位干净的。然而，由于它基于 UTF-8 编码，因此应该可以用于多种用途。现在8位干净已经毫无意义了

\n

请注意，base122 实际上是 base-128，因为 6 个无效值 (128 \xe2\x80\x93 122) 是经过特殊编码的，因此一系列 14 位始终可以用最多 2 个字节表示，与 base-128 完全相同，其中7 位将编码为 1 个字节，实际上可以优化为比 base-128 更高效

\n

\n

Base-122 编码

\n

Base-122 编码一次采用七位输入数据块。如果块映射到合法字符，则使用单字节 UTF-8 字符对其进行编码：0xxxxxxx。如果该块映射到非法字符，我们将使用两字节 UTF-8 字符：110xxxxx 10xxxxxx。由于只有六个非法代码点，我们只需用三位就可以区分它们。将这些位表示为sss给我们提供了格式：110sssxx 10xxxxxx。剩下的八位似乎可以编码更多的输入数据。遗憾的是，表示小于 0x80 的代码点的两字节 UTF-8 字符无效。浏览器会将无效的 UTF-8 字符解析为错误字符。强制代码点大于 0x80 的一个简单方法是使用 格式110sss1x 10xxxxxx，相当于与 0x80 进行按位或（这可能会得到改进，请参阅 \xc2\xa74）。图 3 总结了完整的 base-122 编码。

\n

\n

http://blog.kevinalbs.com/base122

\n

\n

另请参阅base128 编码对于 JavaScript 字符串等场景有多可行？

\n