Версия 2
от 20.09.2006

Кодирование бинарных данных в текст

Введение

    В данном документе рассматриваются проблемы кодирование бинарных данных в текст на примере, как широко применяемых Hex и base64 кодеров, так и нестандартных. Основное внимание уделено таким аспектам как оптимальность кодирования и искажение статистических характеристик кодером. Проведен анализ совместного использования RLE и LZ алгоритмов сжатия. Предложен вариант статистического кодера бинарных данных в текст с кодами переменной длины и встроенным RLE.

Hex

    Кодирование в шестнадцатеричной системе применяется достаточно широко для хранения бинарных данных в тексте. Алфавит кодера можно назвать общепринятым. Алгоритмы кодирования и декодирования очень просты и, фактически, оперируют данными на уровне байта, как единицы данных, используя для представления 2 символа. Таким образом, в закодированном виде получается 100% прирост объема данных, что собственно и является основным недостатком.

Base64

    Кодирование в алфавите из 64 символов позволяет уменьшить прирост объема данных до 33%. Достигается это тем, что данные кодируются на битовом уровне (6 бит на выходной символ), при этом каждые 3 байта данных кодируются 4 символами. Существует несколько алфавитов для такого кодера, например:

b64_MIME = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/';
b64_UU = ' !"#$%&''()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_';
b64_XX = '+-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';

Кроме того, иногда принято выравнивать закодированные данные, на границу 4х символов специальными символами-заполнителями (обычно символ =).

Оптимальность кодирования и сжатие

    Рассмотрим задачу сжатия закодированных в текст данных и более общую задачу оптимального кодирования бинарных данных передаваемых в тексте. Понятно, что кодер в текст с очень незначительной вероятностью может улучшить степень последующего сжатия данных. Можно постулировать, что в любом случае выгоднее произвести сначала сжатие бинарных данных и только потом кодирование в текст. Для экономии места в этом случае следует пользоваться base64 кодером (потенциально можно использовать, по аналогии с арифметическим кодированием, кодер с алфавитом, количество символов которого не равно 2^n).

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

    Если хранить в пакете несжатые данные, то следует рассмотреть вопросы оптимальности кодов. Так Hex кодер увеличит объем на 100%, что может оказаться неприемлемым в случае транспортировки и хранения данных в несжатом виде. Base64 кодер увеличит объем на 33% и с этой точки зрения выглядит лучше. Если применить к закодированным и оригинальным данным типовой LZ архиватор, то, как правило, можно наблюдать следующее.

• Если оригинальные данные слабо сжимаемы (упакованный файл с высокой энтропией), то во всех отношениях лучше будет Base64 кодер, поскольку из-за слабого последующего сжатия, основным фактором является длина кодов. БОльшая длина Hex кодов при сжатии приводит к попыткам сжимать короткие совпадения цепочек кодовых символов, что, в силу статистики исходных данных, приводит только к увеличению сжатого пакета. Убедиться в этом можно при помощи простого эксперимента 2.
• Если в оригинальных данных имеются длинные повторяющиеся цепочки (например, несжатые картинки без плавных переходов), то оптимальным также может оказаться Base64 кодер, т. к. по-прежнему фактором оптимальности является длина кодов. Но в данном случае, принципиальна длина цепочки и количество цепочек, попадающее в словарь архиватора. Для Hex кодера цепочки будут более длиными, и в словарь их попадет меньше. См. данные по файлу pic.dat в эксперименте 1.
• Если в оригинальных данных имеются относительно короткие повторяющиеся цепочки (текст, исполняемы, объектные файлы и тп), то оптимальным с точки зрения последующего сжатия может оказаться Hex кодер. Объясняется это просто - LZ алгоритмы строят словарь цепочек и эффективно кодируют повторы, но цепочки эти - байтовые. Base64 кодер нарушает байтовые границы, поскольку кодирование идет на битовом уровне, усложняя, таким образом, статистику исходных данных. Hex кодер фактически кодирует данные на байтовом уровне, поэтому цепочки в исходных данных преобразуются в цепочки кода с той разницей, что каждая цепочка становится в 2 раза длиннее. Такой эффект при применении Base64 кодера имеет место и в предыдущем случае, однако он нивелируется по отношению к Hex кодеру за счет длины цепочек. По отношению к пакету сжатых оригинальным данных, пакет сжатых данных, обработанных Base64, будет проигрывать по размеру, в том числе, и по причине нарушения байтовых границ. Убедиться в этом можно, проанализировав данные эксперимента 2, где большая часть обрабатываемых файлов содержит данные именно такого типа.

• двухкратное увеличение размера словаря LZ компрессора и предельной длины цепочки;
• адекватное улучшение (или увеличение глубины) поиска цепочек в словаре (если алгоритм поиска использует ограничение на глубину поиска);
• так же важно (особенно для первого случая) двухкратное увеличение минимальной длины кодируемой цепочки - так не будут кодироваться не нужные совпадения.

Улучшение результатов сжатия Base64 кода путем манипуляций с параметрами LZ компрессора представляется гораздо более сложной задачей. Однако увеличение размера словаря, длины цепочки и глубины поиска потенциально могут несколько улучшить результат.

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

• Цепочки исходных данных близки по длине цепочкам оригинальных данных (оптимальны по длине).
• Граница байта в исходных данных соответствует границе символа кода и каждый байт исходных данных кодируется однозначно.

Статистический кодер

    Рассмотрим статистический 2х проходный кодер (разработан А. Серовым) имеющий 130-символьный алфавит. В первый проход кодер считает элементарную статистику: а именно, количество байтов с установленным старшим битом. Эта статистика позволит оптимизировать кодирование статистически смещенных данных (например с большим количеством 0, текста и тп). В зависимости от подсчитанного значения выбираются байтоые значения, которые будут кодироваться одним символом (7 бит), либо это будут байты со значением более 127, либо наоборот. Другая половина в любом случае кодируется исходя из 2х символов на байт (1 служебный + 1 кодовый). Для того, чтобы декодер смог определить, какая "половина" байта кодируется 1 символом, первым символом в пакете может быть еще один служебный символ, указывающий на "короткое" кодирование "верхней половины" байта. Таким образом, во время кодирования (второй проход) используются 128 кодовых символов и 2 служебных: для указания статистики декодеру и для 2х символьного кодирования байта.

    Легко видеть, что кодер обеспечивает объем пакета в пределах 100%..150% от исходных данных в зависимости от статистических характеристик. Кодер удовлетворяет второму требованию по эффективному сжатию указанному выше - байтовые границы не нарушаются и кодирование однозначное. И теоретически и практически такой код будет лучше Hex на любых данных как с точки зрения объема пакета, так и с точки зрения сжимаемости (т. к. цепочки могут совпадать или быть близки по длине к исходным). См. данные эксперимента 1.

Из недостатков кодера можно назвать следующие.

1. Слишком крупный алфавит, в частности используется вся "кириллическая" часть.
2. Слабая статистика - структура данных может быть более неоднородна и деление на "высокие" и "низкие" значения не всегда эффективно.
3. Кодер уступит base64 при кодировании статистически однородных данных: +50% против +33%. Как и в случае Hex кодов, при применении компрессора поверх кодированных сжатых данных, пакет может увеличится из-за попытки сжатия коротких совпадений в кодовой последовательности. См. данные по файлу zip.dat в эксперименте 1.
4. Двойной проход по данным (как минимум, для кодирования).

Из названных недостатков наиболее трудно устранимым представляется последний. Избавиться от двух проходов по данным в статистическом кодере можно только путем применения адаптивных методик, но это усложнит кодер и приведет к неоднозначному кодированию символов входных данных, что снизит эффективность последующего сжатия. Фактически, данный недостаток приводит к увеличению времени кодирования и невозможности "поточного" кодирования данных недоступных кодеру полностью на момент начала кодирования.
Можно сконструировать аналогичный статистический кодер с переменной длиной кодов, который будет лишен ряда указанных выше недостатков и эффективнее использовать статистику данных, а так же учитывать возможность последующего сжатия. Ниже представлены направления таких улучшений.

1. Кодер должен основываться на алфавите, который не будет вызывать проблем при транспортировке текстовых сообщений. Таким алфавитом является MIME. Представляется допустимым ввести дополнительные служебные символы (можно позаимствовать из других алфавитов), чтобы эффективно покрыть все множество байтовых значений. 64 значения можно кодировать 1 символом, остальные 192 значения представить в 2х символьной кодировке, для чего использовать 3 служебных символа (3*64=192). Таким образом мы избавимся от крупного алфавита, но количество "коротких" кодов сократится.
2. Для того, чтобы код был оптимален по длине, необходимо в исходных данных выбрать 64 самых часто встречающихся значения, чтобы потом их закодировать одним символом. Таким образом, при первом проходе по данным необходимо постоить гистограмму на значениях байтов, которую затем отсортировать для выделения самых часто встречающихся значений.
3. Для того, чтобы декодер смог раскодировать пакет, придется передать множество байтов, которые мы кодируем одним символом ) - это, разумеется, осложнит дело при кодировании коротких данных (кроме того, повлияет на последующее сжатие). В виде битовой таблицы эти данные займут 32 байта, в кодировке MIME 43 символа. Однако их можно закодировать эффективнее, если учесть, что 3/4 битов равны 0.
4. Для эффективного кодирования коротких данных использовать либо MIME, либо фиксированную таблицу. Причем, учитывая наличие служебных символов, можно легко дифференцировать несколько вариантов, если зарезервировать первый символ для этих целей. Удобно использовать первый символ кода (не приндлежащий алфавиту MIME) как флаг, указывающий на статистическое кодирование, тогда декодор может легко дифференцировать MIME код от статистического.
5. Ввести варьируемый порог кодирования, и в случае, если статистика данных окажется такова, что статистическое кодирование будет неэффективно, то использовать MIME код.
6. Использовать RLE кодирование (+1 служебный символ-повторитель) - это, с одной стороны, благотворно скажется на объеме пакетов, а с другой не должно сильно повлиять на последующее сжатие, т. к. RLE работает только по специфическим частям данных (длинные повторы байта), для которых RLE алгоритм является достаточно эффективным для сжатия.

Такой кодер обеспечит объем пакета в пределах N..175%+43символа (не более 133% если кодер будет выбирать между статистическими кодами и MIME на основании статистики данных). При использовании RLE нижняя граница N не фиксирована и может быть существенно меньше 100%. Ориентирован кодер на крупные (однако, следует помнить, что кодер двухпроходный) объемы данных с "хорошей" статистикой. Алфавит такого кодера может быть больше 64 символов и меньше (но тогда придется вводить дополнительные служебные символы). Выбор длины алфавита будет оказывать влияние на максимальный объем кода (чем длиннее, тем меньше). Алгоритм кодера, разумеется, сложнее рассмотренных ранее, однако дополнительные издержки на сортировки и прочее являются константой по времени.

RLE и LZ сжатие

    Алгоритм RLE в простейшем случае использует кодирование длинных повторов одного и того же значения байта при помощи указания значения байта и количества повторений, например, по такой схеме:

Одним из практических применений RLE является сжатие изображений, особенно "деловой" графики, факсимильных и других, для которых характерны "заливки" одним цветом.

Рассмотрим влияние предварительного RLE кодирования данных на эффективность LZ сжатия.

1. LZ алгоритм, использует словарный метод, и как правило, достаточно эффективно кодирует длинные цепочки повторяющихся значений, обычно требуя для кодирования нахождения только первого символа цепочки в словаре, после чего кодируется смещение и длина цепочки (что сходно по смыслу с RLE кодом, но LZ код может быть несколько длинее). Однако для LZ алгоритмов это скорее вырожденный случай, тк LZ словарь предназначен для эффективного поиска разносимвольных цепочек на всех дистанциях, а в данном случае эффективность поиска может быть снижена.
2. Если в словаре уже есть цепочка с повтором аналогичных символов, то LZ алгоритм может попытаться ее использовать для кодирования текущей цепочки. При этом может быть найдено не самое оптимальное совпадение из-за снижения эффективности поиска. В этом достаточно легко убедиться, если алгоритм имеет варьируемые насройки глубины поиска цепочек и использования ленивого сравнения (lazy matching). При увеличении этих параметров, данные, хорошо сжимаемые RLE, как правило, сжимаются лучше LZ алгоритмом, тк слабая эффективность поиска в словаре компенсируется перебором большего количества вариантов совпадений. См. эксперимент 3.
3. LZ алгоритм обычно накладывает ограничение на предельную длину кодируемого совпадения и размер словаря. Кроме того, при кодировании дистанций, длина кодов обычно увеличивается с увеличением дистанции. Эти факторы для вырожденных данных, хорошо сжимаемых RLE, могут привести к повышению степени LZ сжатия при предварительной обработке данных RLE. Действительно, после обработки RLE, сократится общий объем данных, но только за счет той их части, которая сжимаема RLE. Цепочки, состоящие из разных символов, остануться без изменений и их повторы будут эффективно кодироваться LZ алгоритмом. При этом сократятся дистанции и средняя длина цепочки и большее количество таких цепочек будет попадать в словарь. RLE конструкции достаточно длинные для поиска и LZ сжатия их повторов, и их поиск в словаре будет эффективенее поиска оригинальных цепочек повторяющихся символов. См. эксперимент 1 и эксперимент 3.
4. Эффективность LZ сжатия поверх RLE может упасть на "стыках" разносимвольных цепочек и цепочек повторяющихся символов, если имеются повторы таких "стыков", а цепочки повторяющихся символов имеют разную длину. Действительно, RLE алгоритм закодирует повторы разной длины разными кодами, что может привести к тому, что "стык" цепочек будет менее эффективно закодирован словарным методом (уменьшится длина совпадения, а оставшаяся после кодирования совпадения часть RLE конструкции не будет эффективно кодироваться словарным методом). Очевидно, что чем более вариабельны длины цепочек повторяющихся символов, тем хуже будет последующее LZ сжатие, тк символ-указатель длины, имеющий разное значение, будет мешать кодировать повторы.

RLE алгоритм легко встроить в статистический кодер бинарных данных в текст - достаточно введения еще одного служебного символа-флага, который будет указывать на то, что необходимо продублировать предыдущий закодированный байт, в количестве, определяемом следующим за флагом кодовым символом. При этом в дублировании самого символа- флага нет необходимости, т. к. он является дополнительным и не может встретиться в другом контексте. Соответственно, длина повтора, кодируемого одной конструкцией, меньше, чем длина повтора в бинарном варианте RLE, т. к. количество кодовых символов меньше.

Кодер S64

Рассмотрим практическую реализацию статистического кодера, базирующуюся на рассуждениях приведенных выше. Условно будем называть этот кодер S64. Он обладает следующими особенностями.

1. Базовый алфавит кодера - MIME, дополненный четырьмя служебными символами "[\](".
2. Кодер использует статистику входных данных для выбора 64 байтовых значений, кодируемых одним MIME символом. Остальные 192 значения кодируются двумя символами, первый из которых принадлежит множеству "[\]" и оределяет "раздел" символьного кода, а второй MIME символ доопределяет кодируемое значение.
3. Для выбора оптимального статистического кода, алгоритм кодера при первом проходе по данным строит гистограмму на байтовых значениях. После сортировки гистограммы выявляются 64 самых часто встречающихся значения, которые кодируются одним символом.
4. Кодер предполагает использование RLE и учитывает повторы значений длиной 4 и более. При первом проходе по данным этот учет сводится к уменьшению значений в гистограмме так, как если бы вместо цепочки повтора в данных находился только первый ее символ.
5. Для RLE кодирования данных используется служебный символ "(". Повтор записывается в виде
   s(m
   где "s" - кодированое значение байта исходных данных (1 или 2 кодовых символа); "(" - флаг кодирования повтора; "m" - символ из алфавита MIME, определяющий количество повторов.
   Минимальное кодируемое количество повторов - 3 (цепочка их 4 значений), это означает, что максимальная кодируемая длина цепочки составляет 67 значения (3 + 64 символа-кода).
6. Для возможности однозначного декодирования присвоение символьных кодов байтовым значениям производится по старшинству, а множество значений кодируемых одним символом записывается в заголовок в виде битового массива MIME кодом (43 символа).
7. Декодер совместим с MIME. Для этого зарезервирован первый символ кода, для статистического кода он всегда равен "[", если код начинается с другого символа, то декодер считает его MIME кодом. За этим символом-флагом следует 43-символьная таблица односимвольных кодов, а далее коды данных.
8. Данные, размером менее 100 байт жестко кодируются кодируются MIME, т.к. учитывая наличие таблицы, получить ощутимый выйгрыш от статистического кодирования сложно.
9. Выполняя первый проход по данным, кодер может точно оценить длину кода, учитывая двухсимвольные коды и RLE. Если длина кода превышает 133% от размера исходных данных, то используется MIME.

Эксперимент 1

В данном эксперименте производилось кодирование данных различными кодерами и последующее сжатие полученного кода алгоритмами ZIP и LZH. В качестве тестового набора использовался известный пакет Calgary Compression Corpus, дополненный файлом zip.dat с высокой энтропией (ZIP архив файла book1.dat). Данные по каждому файлу представлены в виде трех строк: первая относится к несжатым данным, вторая - к данным, сжатым ZIP, третья к данным, сжатым LZH. В столбцах содержатся следующие данные:

• Data file - оригинальные данные и их сжатые варианты.
• Hex - оригинальные данные в Hex коде и результаты сжатия этого кода.
• MIME - оригинальные данные в MIME коде и результаты сжатия этого кода.
• V7 - оригинальные данные, закодированные упомянутым выше 130-символьным статистическим кодером, и результаты сжатия этого кода.
• S64 wo RLE - оригинальные данные, закодированные описанным выше кодером S64 без использования встроенного RLE и результаты сжатия этого кода.
• S64 + RLE - оригинальные данные, закодированные описанным выше кодером S64 c использованием встроенного RLE и результаты сжатия этого кода.
• RLE binary - оригинальные данные, упакованные RLE в бинарном варианте и результаты сжатия этого пакета. В данном случае RLE сжимает цепочки повторяющихся значений длиной 4..258, использует статистический выбор одного служебного значения-флага, которое затем передается в заголовке пакета (длиной 2 байта). В случае, если статистика данных такова, что RLE не приносит выйгрыша, кодируется заголовок в 1 байт и данные передаются без изменений.

Комментарии

Видно, что предложенный кодер S64, в среднем, показал хорошие результаты, превзойдя другие кодеры в текст, как по объему кода, так и по эффективности последующего сжатия LZ алгоритмами. Однако, результаты для конкретных файлов могут быть несколько хуже, чем при использовании кодера V7, в силу в двое более крупного алфавита последнего. Так же можно указать на следующее:

1. Видно, что на тестовых данных самым неудачным для последующего сжатия оказался чистый MIME код. Произошло это из-за упомянутого нарушения байтовых границ Base64 кодерами. На примерах обработки pic.dat и zip.dat, видно, что результат последующего сжатия MIME кода в ряде случаев могут быть существенно лучше. Однако, эти файлы являются "крайними" по своей статистике.
2. Видно, что в ряде случаев RLE может не только уменьшить дину кода, но и позитивно повлиять на позледующее LZ сжатие (как видим, даже при кодировании в текст). В частности, заметно, как нивелировано значение размера словаря и длины цепочки повтора для LZ алгоритма (у LZH словарь и длина цепочки существенно меньше, чем у ZIP).
3. Видно, как кодер S64 отдает предпочтение MIME кодированию вместо статистического на статистически однородных данных. Кроме того, заметно, что Hex код заметно хуже поддается сжатию в этом случае, как впрочем и код, сформированный алгоритмом V7.
4. Видно, что использование RLE в кодере S64 улучшило как среднюю длину кода, так и среднюю сжимаемость кода (незначительно). Однако, в конкретных случаях, применение RLE может принести незначительную потерю в последующем сжатии кода. Это видно в данных по отдельным файлам.

Эксперимент 2

В данном эксперименте мы проверим, как влияет минимальная длина цепочки повтора LZ алгоритма на эффективность сжатия Hex кода. Предположение состоит в том, что минимальная длина цепочки повтора должна быть увеличена в два раза для эффективного сжатия таких данных. Для проверки мы модифицируем LZH компрессор и пересчитаем результаты. Ниже приведены для сравнения результаты обработки файла zip.dat (отдельно) и общие результаты сжатия всего набора. В каждом случае представлены 2 строки данных о сжатии: первая - с обычными настройками (как в предыдущем эксперименте), вторая (желтая) - с удвоенной минимальной длиной цепочки повтора.

Как видим, наше предположение подтвердилось - при увеличении минимальной длины цепочки LZ алгоритма степень сжатия Hex кода повысилась - особенно хорошо это видно в случае, если исходные данные имеют высокую энтропию. При этом средняя степень сжатия исходных данных, разумеется, ухудшилась.

Эксперимент 3

В данном эксперименте мы убедимся, что на низкоэнтропийных данных с длинными цепочками повторяющихся значений эффективность поиска в LZ алгоритме может упасть. Для этого мы произведем сжатие наших данных алгоритмом LZH с максимально увеличенными глубиной поиска и длиной цепочки для ленивого сравнения. Приведем результаты для paper6.dat и pic.dat. Для каждого файла представлены 2 строки данных о сжатии: первая - с обычными настройками, вторая (желтая) - с экстремальными.

Легко видеть, что для файла paper6.dat изменение не привело к существенному улучшению сжатия, причем максимальный относительный результат в 1.5% получен для Hex кода (для него важна глубина поиска). В то же время, относительная разница в сжатии pic.dat (низкая энтропия, много повторов) превысила 10%, что подтверждает потерю эффективности поиска в LZ словаре. Также видно, что сжатие RLE кода pic.dat слабо зависит от параметров поиска LZ алгоритма, а степень сжатия лучше степени сжатия оригинальных данных.

Заключение

Исходный код. Реализация в функциях S64Encode, S64Decode. Все функции оперируют данными, хранимыми в длинной строке и возвращают строку (т. е. в памяти).