为什么base64编码的数据压缩如此糟糕？

Question

我最近压缩了一些文件,我注意到base64编码的数据似乎压缩得非常糟糕.这是一个例子:

• 原始档案:429,7 MiB
• 压缩通过xz -9:
  13,2 MiB / 429,7 MiB = 0,031 4,9 MiB/s 1:28
• base64它并压缩通过xz -9:
  26,7 MiB / 580,4 MiB = 0,046 2,6 MiB/s 3:47
• base64原始压缩的xz文件:
  17,8 MiB几乎没有时间=预期1.33x的大小增加

所以可以观察到的是:

• xz压缩真的很好☺
• base64编码的数据压缩不好,比未编码的压缩文件大2倍
• base64-then-compress比compress-then-base64明显更差,更慢

怎么会这样？Base64是一种无损,可逆的算法,为什么它会如此影响压缩呢？(我也试过gzip,结果相似).

我知道base64然后压缩文件是没有意义的,但大多数时候一个人无法控制输入文件,我会想到,因为实际的信息密度(或任何它被称为base64编码文件的几乎与非编码版本相同,因此可以类似地压缩.

Answer 1

大多数通用压缩算法使用一个字节的粒度.

我们考虑以下字符串:

"XXXXYYYYXXXXYYYY"

• 运行长度编码算法会说:"那是4'X',然后是4'Y',接着是4'X',接着是4'Y'"
• Lempel-Ziv算法会说:"那是字符串'XXXXYYYY',后跟相同的字符串:所以让我们用第一个字符串替换第二个字符串."
• 霍夫曼编码算法会说:"该字符串中只有2个符号,因此每个符号只能使用一个符号."

现在让我们在Base64中编码我们的字符串.这是我们得到的:

"WFhYWFlZWVlYWFhYWVlZWQ=="

所有算法现在都在说:"那是什么样的混乱？" .他们不太可能很好地压缩那个字符串.

提醒一下,Base64基本上是通过将(0 ... 255)中3个字节的组重新编码为(0 ... 63)中的4个字节的组来实现的:

Input bytes    : aaaaaaaa bbbbbbbb cccccccc
6-bit repacking: 00aaaaaa 00aabbbb 00bbbbcc 00cccccc

然后将每个输出字节转换为可打印的ASCII字符.按照惯例,这些字符是(这里每10个字符有一个标记):

0         1         2         3         4         5         6
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

例如,我们的示例字符串以一组三个字节开头,等于十六进制的0x58(字符"X"的ASCII码).或者二进制:01011000.让我们应用Base64编码:

Input bytes      : 0x58     0x58     0x58
As binary        : 01011000 01011000 01011000
6-bit repacking  : 00010110 00000101 00100001 00011000
As decimal       : 22       5        33       24
Base64 characters: 'W'      'F'      'h'      'Y'
Output bytes     : 0x57     0x46     0x68     0x59

基本上,在原始数据流中显而易见的"字节0x58的3倍"模式在编码数据流中不再明显,因为我们已经将字节分成6位数据包并将它们映射到现在看起来像的新字节是随机的.

换句话说:我们打破了大多数压缩算法所依赖的原始字节对齐.

无论使用何种压缩方法,它通常都会对算法性能产生严重影响.这就是为什么你应该总是先压缩然后编码第二个.

对于加密来说更是如此:先压缩,然后加密.

编辑 - 关于LZMA的说明

正如MSalters所注意到的那样,xz正在使用的LZMA正在研究比特流而不是字节流.

尽管如此,这种算法也会受到Base64编码的影响,这种方式与我之前的描述基本一致:

Input bytes      : 0x58     0x58     0x58
As binary        : 01011000 01011000 01011000
(see above for the details of Base64 encoding)
Output bytes     : 0x57     0x46     0x68     0x59
As binary        : 01010111 01000110 01101000 01011001

即使在位级工作,在输入二进制序列中识别模式比在输出二进制序列中更容易.

Answer 2

压缩必然是一个作用于多个位的操作.试图压缩个体"0"和"1"是没有可能获得的.即便如此,压缩通常一次只能在一组有限的位上工作.LZMA算法xz不会同时考虑所有36亿比特.它查看更小的字符串(<273字节).

现在看看base-64编码的作用:它用4字节字替换3字节(24位)字,仅使用256个可能值中的64个.这为您提供了x1.33的增长.

现在很明显,这种增长必然会导致一些子串超过编码器的最大子串大小.这导致它们不再被压缩为单个子串,而是作为两个单独的子串.

由于你有很多压缩(97%),你显然有很长的输入子串被压缩的情况.这意味着您还将有许多子串在base-64扩展超过编码器可以处理的最大长度.