Архивация

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

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

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

Общие принципы архивации. Классификация методов

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

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

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

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

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

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

Дата добавления: 2015-05-07