Методы архивации

 

 

Процесс сжатия в общем  виде протекает следующим образом: на вход алгоритма сжатия поступает непрерывный входной поток. Алгоритм постоянно хранит некоторое достаточно большое количество последних обработанных символов в области SDB (Sliding Dictionary Buffer - Буфер скользящего словаря). По мере обработки входного потока вновь поступившие символы попадают в конец SDB, смещая предыдущие символы и вытесняя самые старые. Размер SDB сильно варьируется в разных реализациях (от 8 Kb в ранних версиях ZIP, до 1 Mb в WinRAR v2.0). Увеличивая размер SDB, мы улучшаем степень сжатия, но при этом падает его скорость, и растет требуемый объем памяти.

Путем поиска в SDB алгоритм выделяет самую длинную начальную  подстроку входного потока, совпадающую  с одной из подстрок в SDB, и выдает на выход пару (Distance, Length), где Distance - расстояние от найденной в SDB подстроки до входной подстроки, а Length - ее длина. В случае если подстрока в SDB не найдена, в выходной поток просто копируется очередной символ входного потока. Поясним на следующем примере. Имеется входной поток АDСАВDВАDAССADDВDАВDВАЕDАСCAD. Для первых 17-ти символов алгоритм не находит подстрок, поэтому они просто копируются в выходной поток. Но в 18-й позиции он обнаруживает подстроку АВDВА и видит, что такая же подстрока располагается в 4-й позиции. Поэтому он заменяет ее ссылкой [14, 5], где 14 - это расстояние от 18-й позиции до 4-й, а 5 - длина подстроки. Далее подстроки опять не находятся, т.е. происходит простое копирование, до тех пор пока в 25-й позиции не обнаруживается подстрока АССА, которая расположена также и в 10-й позиции. Она заменяется ссылкой [15, 4], где 15 - это расстояние от 25-й позиции до 10-й, а 4 - длина подстроки.

В результате выходной поток  будет иметь вид АDСАВDВАDAССADDВD [14, 5]ЕD[15,4]D.

Таким образом, алгоритм Лемпеля-Зива (иногда называемый также LZ-compression) преобразует входной поток в два выходных параллельных потока Distance и Length. Эти потоки хорошо поддаются сжатию алгоритмом Хаффмана, или арифметическим сжатием, и отсюда мы логично приходим к идее двухступенчатого сжатия, при котором на первом этапе входной поток сжимается за счет замены подстрок на ссылки на такие же подстроки, встречающиеся ранее, а на втором этапе происходит дополнительное сжатие за счет компрессии ссылок.

 

 

АЛГОРИТМ ДВУХСТУПЕНЧАТОГО СЖАТИЯ

Алгоритм двухступенчатого сжатия является наиболее эффективным  алгоритмом, из практически применяемых  в настоящее время. Именно он применяется  в архиваторах ZIP, RAR, ARJ и многих других случаях, где требуется сжатие данных.

При использовании этого  алгоритма возникают две проблемы: проблема синхронной записи двух выходных потоков в файл и проблема быстрого поиска в SDB. Первая из них, как правило, решается чередованием записи символов из потока Distance и из потока Length, т.е. Distance1, Length1, Distance2, Length2,:

Вторая проблема серьезнее. Первоначально предлагалось использовать простой поиск в SDB, но на практике это оказалось неприемлемым, т.к. время сжатия при этом будет пропорционально  произведению размера SDB на количество символов во входном потоке. Решение предложил Белл (Bell), использовавший двоичное дерево для быстрого поиска в SDB.

 

 

Архиваторы

 

Весь спектр существующих сегодня архиваторов можно разделить  на три группы:

1. файловые архиваторы

2. программные архиваторы

3. дисковые архиваторы

 

 

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

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

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

 

    Для архивирования  используются специальные программы  - архиваторы или диспетчеры архивов.  Наиболее известные архиваторы: WinZip; WinRar; WinArj. Эти программы обеспечивают возможность использования и других архиваторов, поэтому, если на компьютере, куда перенесены сжатые в них файлы, отсутствуют указанные программы, архивы можно распаковать с помощью другого архиватора. До сих пор широко используются и соответствующие программы, созданные в MS DOS, но способные работать и в Windows.

    Почти все  архиваторы позволяют создавать  удобные самораспаковывающиеся архивы (SFX - Self-extracting-архивы) - файлы с расширением .ехе. Для распаковки такого архива не требуется программы-архиватора, достаточно запустить архив *.ехе как программу. Многие архиваторы позволяют создавать многотомные (распределенные) архивы, которые могут размещаться на нескольких дискетах.

 

 

Основными характеристиками программ-архиваторов являются:

• скорость работы;

• сервис (набор функций архиватора);

• степень сжатия - отношение размера исходного файла к размеру упакованного файла.

 

 

Основными функциями  архиваторов являются:

• создание архивных файлов из отдельных (или всех) файлов текущего каталога и его подкаталогов, загружая в один архив до 32 000 файлов;

• добавление файлов в архив;

• извлечение и удаление файлов из архива;

• просмотр содержимого архива;

• просмотр содержимого архивированных файлов и поиск строк в архивированных файлах;

• ввод в архив комментарии к файлам;

• создание многотомных архивов;

• создание самораспаковывающихся архивов, как в одном томе, так и в виде нескольких томов;

• обеспечение защиты информации в в архиве и доступ к файлам, помещенным в архив, защиту каждого из помещенных в архив файлов циклическим кодом;

• тестирование архива, проверка сохранности в нем информации;

• восстановление файлов (частично или полностью) из поврежденных архивов;

• поддержки типов архивов, созданных другими архиваторами и др.

 

 

 

 

 

 

 

 

Типы архивов

 

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

Характерными форматами  сжатия с потерей информации являются:

• .jpg - для графических данных;

• .mpg - для видеоданных;

• .mp3 - для звуковых данных.

 

Характерные форматы  сжатия без потери информации:

• .tif, .pcx и другие - для графических файлов;

• .avi - для видеоклипов;

• .zip, .arj, .rar, .lzh, .cab и др. - для любых типов файлов.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список литературы

 

Новожилов, О. П. 

«Информатика: учебное пособие»  Юрайт Издательство ООО, 2011

 

Семакин, И.Г.

Информатика и ИКТ : базовый уровень : учебник для 10-11-го классов 
Бином. Лаборатория знаний, 2010, Несерийное издание.

 

Интернет-ресурс:

• http://www.comprice.ru

 

• http://www.windxp.com.ru

 

• http://ru.wikipedia.org