Алгоритмы Сжатия информации

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

Сжатие сокращает объем пространства, которое требуется для хранения файлов в ЭВМ, и количество времени, необходимое для передачи информации по каналу установ­ленной ширины пропускания. Это есть форма кодирования. Другими целями кодиро­вания являются поиск и исправление ошибок, а также шифрование. Процесс поиска и исправления ошибок противоположен сжатию - он увеличивает избыточность дан­ных, когда их не нужно представлять в удобной для восприятия человеком форме. Удаляя из текста избыточность, сжатие способствует шифрованию, что затрудняет поиск шифра доступным для взломщика статистическим методом.

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

Одним из самых ранних и хорошо известных методов сжатия является алгоритм Хаффмана, который был и остается предметом многих исследований. Однако, в конце 70-х годов благодаря двум важным переломным идеям он был вытеснен. Од­на заключалась в открытии метода арифметического кодирования, имеющего схожую с кодированием Хаффмана функцию, но обладающего не­сколькими важными свойствами, которые дают возможность достичь значительного превосходства в сжатии. Другим новшеством был метод Зива-Лемпела, да­ющий эффективное сжатие и применяющий подход, совершенно отличный от хаффма­новского и арифметического. Обе эти техники со времени своей первой публикации значительно усовершенствовались, развились и легли в основу практических высо­коэффективных алгоритмов.

Что такое архивирование и зачем оно нужно

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

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

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

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

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

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

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

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

Ряд архиваторов позволяют создавать многотомные архивы, саморазворачивающиеся архивы, архивы, содержащие каталоги. Наиболее популярны и широко используются следующие архиваторы: ARJ, PKZIP/PKUNZIP, RAR, ACE, LHA, ICE, PAK, PKARC/PKXARC, ZOO, HYPER, AIN.

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

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

Существуют два основных метода архивации без потерь:

· алгоритм Хаффмана (англ. Huffman), ориентированный на сжатие последовательностей байт, не связанных между собой,

· алгоритм Лемпеля-Зива (англ. Lempel, Ziv), ориентированный на сжатие любых видов текстов, то есть использующий факт неоднократного повторения "слов" – последовательностей байт.

Практически все популярные программы архивации без потерь (ARJ, RAR, ZIP и т.п.) используют объединение этих двух методов – алгоритм LZH.

Терминология

Сжимаемые данные называются по-разному - строка, файл, текст или ввод. Предполагается, что они производятся источником, который снабжает компрессор символами, принадлежащими некоторому алфавиту. Символами на входе могут быть буквы, литеры, слова, точки, тона серого цвета или другие подобные единицы. Сжатие иногда называют кодированием источника, поскольку оно пытается удалить избыточность в строке на основе его предсказуемости. Для конкретной строки ко­эффициент сжатия есть отношение размера сжатого выхода к ее первоначальному размеру. Для его выражения используются много разных единиц, затрудняющих сра­внение экспериментальных результатов. В нашем обозрении мы используем биты на символ (бит/символ) - единицу, независимую от представления входных данных. Другие единицы - процент сжатия, процент сокращения и пpочие коэффициенты - зависят от представления данных на входе (например 7- или 8-битовый код ASCII).

Методы кодирования

Кодирование (encoding) имеет дело с потоком символов в некотором алфавите, причем частоты символов различны. Целью кодирования является преобразование этого потока в поток бит минимальной длины. Это достигается уменьшением энтропии потока путем учета частоты символов: длина кода должна быть пропорциональна информации, содержащейся во входном потоке. Если распределение вероятностей частот известно, то можно построить оптимальное кодирование. Задача усложняется в случае, если распределение частот символов заранее неизвестно. В этом случае в зависимости от технических требований и выбранного алгоритма кодирования используется адаптивная, полуадаптивная или статичная модель.

Модели входного потока

Моделирование и энтропия

Одним из наиболее важных достижений в теории сжатия за последнее десятиле­тие явилась идея разделения процесса на две части: на кодирование, при котором непосредственно производится сжатый поток битов, и на модели­рование, которое поставляет информацию кодированию. Эти две раздельные части названы кодированием и моделированием. Моделирование присваивает вероятности символам, а кодирование переводит эти вероятности в последовательность битов. К сожалению, последнее понятие нетрудно спутать, поскольку "кодирование" часто используют в широком смысле для обозначения всего процесса сжатия (включая моделирование). Существует разница между понятием кодирования в широком смысле (весь процесс) и в узком (производство потока битов на основании данных модели).

Связь между вероятностями и кодами установлена в теореме Шеннона кодирова­ния истоточника, которая показывает, что символ, ожидаемая вероятность по­явления которого есть p, лучше всего представить -log p битами. Поэтому сим­вол с высокой вероятностью кодируется несколькими битами, тогда как маловеро­ятный требует многих битов. Мы можем получить ожидаемую длину кода посредством усреднения всех возможных символов, даваемого формулой:

H=-∑ p(i) log p(i) .

Это значение называется энтропией распределения вероятности, т.к. это мера ко­личества порядка (или беспорядка) в символах.

Задачей моделирования является оценка вероятности для каждого символа. Из этих вероятностей может быть вычислена энтропия. Очень важно отметить, что эн­тропия есть свойство модели. В данной модели оцениваемая вероятность символа иногда называется кодовым пространством, выделяемым символу, и соответствует распределению интервала (0,1) между символами, и чем больше вероятность симво­ла, тем больше такого "пространства" отбирается у других символов.

Наилучшая средняя длина кода достигается моделями, в которых оценки веро­ятности как можно более точны. Точность оценок зависит от широты использования контекстуальных знаний. Например, вероятность нахождения буквы "о" в тексте, о котором известно только то, что он на английском языке, может быть оценена на основании того, что в случайно выбранных образцах английских текстов 6% си­мволов являются буквами "о". Это сводится к коду для "о", длиной 4.17. Для ко­нтраста, если мы имеем фразу "to be or not t", то оценка вероятности появления буквы "о" будет составлять 99% и ее можно закодировать через 0.014 бита. Боль­шего можно достичь, формируя более точные модели текста. Практические модели лежат между двумя крайностями этих примеров.

Модель по существу есть набор вероятностей распределения, по одному на каждый контекст, на основании которого символ может быть закодирован. Контекс­ты называются классами условий, т.к. они определяют оценки вероятности. Нетри­виальная модель может содержать тысячи классов условий.

Не нашли, что искали? Воспользуйтесь поиском по сайту: