Лекция

Тема: Архивация данных. Знакомство с программами-архиваторами WinZip и WinRar. Компьютерные вирусы. Антивирусные программы

1. Общие понятия об архивации данных Архивация и сжатие

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

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

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

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

Методы сжатия без потерь

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

• Групповое кодирование RLE (Run Lengs Encoding) – один из самых старых методов сжатия, который используют в основном для архивации графики.

• Кодирование Хаффмана (Huffman) – в основе лежит тот факт, что некоторые символы в тексте могут попадаться чаще средней частоты повторений, а другие - реже.

• Кодирование Лемпеля – Зива (Lempel, Ziv) – использует факт неодноразового повторения фрагментов текста, т. е. последовательностей байтов.

Групповое кодирование RLE

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

к оторый описан байтами:

255 255 255 255 128 128 0 0 0 0

будет представлен как

255 4 128 2 0 4

Вместо 10 байт для записи этого ряда необходимо будет 6 байт. Понятно, что степень сжатия зависит от характера изображения и наявности длинных цепочек с байтами, которые повторяются. Это выполняется для изображений с большим одноцветными участками. Изображения в которых мало соседних пикселов одного цвета, не годятся для сжатия по методу RLE. Размер сжатого файла вэтом случае может превышать размер исходного файла.

Кодирование Хаффмана

Напомним, что при кодировании текстовой информации каждому символу отводится 1 байт. Однако на практике одни символы в тексте встречаются чаще, другие – реже. Основой метода Хаффмана является то, что для записи распространенных символов используются короткие последовательности бит (длинной меньше 8 бит), а для записи редких символов – длинные. При этом суммарный объем файла уменьшается.

Хаффман предложил очень простой графический спосою определения того, какому символу необходимо присвоить конкретный код. Избегая подробностей покажеи действие метода на примере кодирования слова «инфинитив». Частота появления букв в этом слове следующая:

и – 4, т – 1,

н – 2, в – 1.

ф – 1,

Используя метод Хаффмана, буквам можно присвоить кода: и- 11, н- 01; ф – 101; т – 001; в – 000. После кодирования слово «инфинитив» будет записываться как: 110110111011100111000 и иметь длину 21 бит. Так какисходное слово имело 72 (=9*8) бит, получаем сжатие больше чем в три раза.

Обратите внимание, что в коде Хаффмана ни один код символа не является начало любого другого символа. Это позволяет получателю однозначно обновлять код сжатого файла, даже если он не знает длину кода переданного символа. Во время прийома кода получатель сначала оттелит первый символ, в нашем примере: 11 – 0110111011100111000. Затем будет выделен второй символ: 11 – 01 – 10111011100111000 и так до полной расшифровки кода: 11 – 01 – 101 – 11 – 01 – 11 – 001 – 11 – 000.

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

Кодирование Лемпеля – Зива

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

Поясним это на примере выражения «давным – давно», которое кодируется как «давным – (-7,4)о». Т. е. вместо повторяемой последовательности «давн», которая состоит из 4 символов и начинается с 8-й позиции, используется такая подстановка. Отсчитывается смещение от текущей позиции на 7 знаков влево (смещение влево обозначается знаком минус) и используется фрагмент из 4 знаков.

Метод Лемпеля – Зива чаще всего используют для сжатия текстов и файлов, которые совсе не сжимаются методом RLE.