64

我最近在压缩一些文件,我注意到 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 压缩得真好☺</li>
  • base64编码的数据压缩不好,比未编码的压缩文件大2倍
  • base64-then-compresscompress-then-base64明显更差和更慢

怎么会这样?Base64是无损、可逆的算法,为什么对压缩影响这么大?(我也尝试使用 gzip,结果相似)。

我知道base64-then-compress一个文件没有意义,但大多数时候人们无法控制输入文件,我会认为因为实际的信息密度(或任何它被称为) 的 base64 编码文件几乎与非编码版本相同,因此同样可压缩。

4

3 回答 3

155

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

让我们考虑以下字符串:

"XXXXYYYYXXXXYYYY"
  • Run-Length-Encoding 算法会说:“那是 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

基本上,在原始数据流中明显的“3 倍字节 0x58”模式在编码数据流中不再明显,因为我们已将字节分解为 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

即使在位级别上工作,在输入二进制序列中识别模式也比在输出二进制序列中识别模式要容易得多。

于 2016-06-30T14:56:22.160 回答
11

压缩必然是作用于多个位的操作。尝试压缩单个“0”和“1”没有任何好处。即便如此,压缩通常一次只处理一组有限的位。中的 LZMA 算法xz不会一次考虑所有 36 亿位。它查看小得多的字符串(<273 字节)。

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

现在很清楚,这种增长必须导致一些子串增长超过编码器的最大子串大小。这导致它们不再被压缩为单个子字符串,而是确实被压缩为两个单独的子字符串。

由于您有很多压缩(97%),您显然会遇到很长的输入子字符串被整体压缩的情况。这意味着您还将有许多以 base-64 为基础的子字符串扩展超过编码器可以处理的最大长度。

于 2016-06-30T13:46:40.263 回答
-6

这不是 Base64。其库的内存要求“预设 7-9 与预设 6 类似,但使用更大的字典并且具有更高的压缩器和解压缩器内存要求。” https://tukaani.org/xz/xz-javadoc/org/tukaani/xz/LZMA2Options.html

于 2018-06-04T05:11:49.303 回答