Упаковка данных на простых примерах

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

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

Вот один из методов: имеется текст, который нужно упаковать. Выделяя из него список слов, составляем словарь, причем для слов в разных падежах можно высчитать максимальную длину совпадения. Сортируем словарь по убыванию совпадений и кодируем повторяющиеся части двухбайтовым кодом: первый указывает на присутствие сжатия, второй – на номер текста в словаре. После этого коды добавляются в словарь, а затем текст окончательно кодируется: если у слова нет кода, оно выводится как есть, если код есть, то выводится код. Иногда для кодирования используются незанятые служебные коды, и тогда упаковку можно сделать еще плотнее. Таким способом упаковывали раньше некоторые системы помощи, электронные словари и руководства.

Интересный прием дает неравномерное использование битов под сообщение. К примеру, в словаре Брайля используются всего 2^6 знаков, т.е. 64 символа. Их можно упаковать 6-битовыми последовательностями, что дает на каждом символе экономию в 25%, но требует от программы специальных функций записи и чтения кода. Более универсальный алгоритм – метод Хаффмана, где наиболее частому сообщению соответствует более короткий бинарный код. В этом случае составляется бинарное дерево, каждый узел которого является кодом. К примеру, слово «сарай» кодируется примерно так:

А 2(0) А 2(0) РЙС 3(Р=100, Й=111, С=11)
С 1(1) РЙ 2(Р=10, Й=11)+ А 2(0)
Р 1(1)+ С 1(1)+
Й 1(1)+

На каждом этапе дерево разветвляется, а сообщения с малым весом группируются и объединяются с вышестоящими, чтобы создать новый код. Данное сообщение в итоге будет 1101000111, т.е. 10 битов вместо 5х8 = 40. Упаковка в 4 раза, причем выборка кодов для распаковки уникальна для каждого символа сообщения. Примерно так же организуется арифметическая компрессия, только в итоге получается длинное вещественное число, где каждый символ представлен своим диапазоном знаков после нуля.

Наиболее простой способ – RLE упаковка, применяемая в графике: там число одинаковых байтов упаковываются в два три байта – идентификатор упаковки, количество повторений и сам байт сообщения.

В популярном алгоритме LZW используются словари, которые постоянно сравниваются с прочитанным сообщением: если соответствие находится, то сообщение заменяется ссылкой на словарную статью, иначе попадает в словарь для дальнейшего поиска. Еще более интересный способ – специальная упаковка, которая зависит от формата файла и использует его особенности. Как правило, в настоящих архиваторах используются все методы сразу, для чего проводится предварительное моделирование процесса и сравнение результатов.

Leave a Comment

Ваш e-mail не будет опубликован.