Функции архивации

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

Напомним, что при кодировании текстовой информации каждому символу отводится 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.

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

Ø Резервное копирование. В процессе эксплуатации компьютера не исключены ситуации, которые угрожают невозвратимой потерей информации (неисправность устройства накопления или дефекты на поверхности жесткого диска, неправильные операции с файлами или случайное удаление файлов, или уничтожение информации компьютерным вирусом). Для сохранения важной информации используется резервное копирование на внешние носители (магнитооптические диски, диски CD – R и CD – RW, винчестеры). Резервное копирование выполняется спомощью специальных утилит, которые обеспечивают создание компактных архивов. Одна из таких утилит входит в комплект Windows.

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