Почему данные, закодированные в base64, так плохо сжаты?

Я недавно сжимал некоторые файлы, и я заметил, что данные с кодировкой 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-then-compress файла, но большую часть времени у него нет контроля над входными файлами, и я бы подумал, что с фактической плотностью информации (или что-то еще он называется) файла с кодировкой base64, будет почти идентичен некодированной версии и, таким образом, будет сжимаемым образом.

Ответ 1

Большинство общих алгоритмов сжатия работают с однобайтной детализацией.

Рассмотрим следующую строку:

"XXXXYYYYXXXXYYYY"

Алгоритм Run-Length-Encoding скажет: "4 'X', за которым следует 4 'Y', за которым следует 4 'X', а затем 4 'Y'"
Алгоритм Lempel-Ziv скажет: "Это строка" XXXXYYYY ", за которой следует одна и та же строка: так что замените вторую строку ссылкой на 1-й."
Алгоритм кодирования Хаффмана скажет: "В этой строке всего 2 символа, поэтому я могу использовать только один бит на символ".

Теперь позвольте закодировать нашу строку в Base64. Вот что мы получаем:

"WFhYWFlZWVlYWFhYWVlZWQ=="

Все алгоритмы теперь говорят: "Какой беспорядок это?". И они вряд ли сжимают эту строку очень хорошо.

В качестве напоминания Base64 в основном работает с перекодированием групп из 3 байтов в (0... 255) в группы по 4 байта в (0... 63):

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

Каждый выходной байт затем преобразуется в печатный символ ASCII. По соглашению, эти символы (здесь с отметкой каждые 10 символов):

0         1         2         3         4         5         6
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

Например, наша примерная строка начинается с группы из трех байтов, равной 0x58 в шестнадцатеричном формате (ASCII-код символа "X" ). Или в двоичном формате: 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-битные пакеты и сопоставили их с новыми байтами, которые теперь кажутся случайными.

Другими словами: мы нарушили исходное выравнивание байтов, на которое полагаются большинство алгоритмов сжатия.

Какой бы метод сжатия не использовался, он обычно оказывает сильное влияние на производительность алгоритма. Вот почему вы всегда должны сначала сжимать и кодировать второй.

Это еще более верно для шифрования: сначала сжать, зашифровать второй.

EDIT - заметка о LZMA

Как заметил MSalters, LZMA, который использует xz, работает на потоках бит, а не на байтовых потоках.

Тем не менее, этот алгоритм также будет страдать от кодирования 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

Даже при работе на уровне бит гораздо легче распознать шаблон во входной двоичной последовательности, чем в выходной двоичной последовательности.

Ответ 2

Сжатие - это операция, действующая на несколько бит. Нет никакой возможной выгоды при попытке сжать отдельные "0" и "1". Тем не менее, сжатие обычно работает с ограниченным набором бит за раз. Алгоритм LZMA в xz не будет рассматривать все 3,6 миллиарда бит одновременно. Он смотрит на гораздо меньшие строки (< 273 байта).

Теперь посмотрим, что делает кодировка base-64: он заменяет 3-байтовое (24-битное) слово словом 4 байта, используя только 64 из 256 возможных значений. Это дает вам рост x1.33.

Теперь совершенно очевидно, что этот рост должен приводить к тому, что подстроки будут расти за максимальный размер подстроки кодера. Это заставляет их больше не сжиматься как одна подстрока, а как две отдельные подстроки.

Поскольку у вас много сжатия (97%), у вас, по-видимому, есть ситуация, когда очень большие входные подстроки сжаты в целом. это означает, что у вас также будет множество подстрок, которые будут base-64 расширены за максимальную длину, с которой может работать кодировщик.