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

Question

Недавно я сжимал некоторые файлы и заметил, что данные в кодировке base64 сжимаются очень плохо. Вот один пример:

• Исходный файл: 429,7 МиБ
• сжимать через xz -9:
  13,2 MiB / 429,7 MiB = 0,0314,9 MiB/s1:28
• base64 это и сжимать через xz -9:
  26,7 MiB / 580,4 MiB = 0,0462,6 MiB/s3:47
• base64 оригинальный сжатый файл xz:
  17,8 MiB почти без времени = ожидаемый 1.33x увеличение в размере

Итак, что можно наблюдать, так это:

• xz сжимает действительно хорошо ☺
• Данные в кодировке base64 плохо сжимаются, они в 2 раза больше, чем сжатые файлы без кодирования
• base64-then-compress значительно хуже и медленнее, чем сжатие-затем-base64

Как это может быть? Base64 - это обратимый алгоритм без потерь, почему он так сильно влияет на сжатие? (Я тоже пробовал с gzip, с похожими результатами).

Я знаю, что не имеет смысла сжимать файл base64-затем-сжимать файл, но большую часть времени никто не контролирует входные файлы, и я бы подумал, что с фактической плотностью информации (или как она там называется)) файла в кодировке base64 будет почти идентичен некодированной версии и, следовательно, будет сжиматься аналогичным образом.

Answer 1

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

Давайте рассмотрим следующую строку:

"XXXXYYYYXXXXYYYY"

• Алгоритм кодирования по длине прогона скажет: "это 4" X ", затем 4" Y ", затем 4" X ", затем 4" Y ""
• Алгоритм Лемпеля-Зива скажет: "Это строка" XXXXYYYY ", за которой следует та же строка: поэтому давайте заменим 2-ю строку ссылкой на 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-битные пакеты и отобразили их в новые байты, которые теперь кажутся быть случайным

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

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

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

РЕДАКТИРОВАТЬ - заметка о 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

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

Answer 2

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

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

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

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

Answer 3

Это не Base64. Требования к памяти библиотек: "Предустановки 7–9 похожи на предустановки 6, но используют большие словари и предъявляют более высокие требования к памяти компрессора и декомпрессора". https://tukaani.org/xz/xz-javadoc/org/tukaani/xz/LZMA2Options.html