Архив. Общие принципы архивации

1. Архив

Навозов М.В.
МПУ
2008

2. Архив:

Набор файлов, папок и других данных,
сжатых и сохраненных в файле
хранящихся на жёстком диске ,
дискете или CD,DVD,Flash.

3. ..:Термины:..

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

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

Все алгоритмы сжатия данных качественно делятся :
1) алгоритмы сжатия без потерь, при использовании которых
данные на приемной восстанавливаются без малейших
изменений.
2) алгоритмы сжатия с потерями, которые удаляют из потока
данных информацию, незначительно влияющую на суть данных,
либо вообще не воспринимаемую человеком
Существует два основных метода архивации без потерь:
• алгоритм Хаффмана (англ. Huffman), ориентированный на
сжатие последовательностей байт, не связанных между собой,
• алгоритм Лемпеля-Зива (англ. Lempel, Ziv), ориентированный на
сжатие любых видов текстов, то есть использующий факт
неоднократного повторения "слов" – последовательностей байт.
Практически все популярные программы архивации без потерь
(ARJ, RAR, ZIP и т.п.) используют объединение этих двух
методов – алгоритм LZH.

5. Алгоритм Хаффмана

если для записи распространенных
символов использовать короткие
последовательности бит, длиной меньше
8, а для записи редких символов –
длинные, то суммарный объем файла
уменьшится
код Хаффмана является префиксным, то
есть код никакого символа не является
началом кода какого-либо другого символа

6. символ "А" получает код "000", символ "Б" – код "01", символ "К" – код "001", а символ "О" – код "1".

символ "А" получает код "000", символ "Б" – код "01",
символ "К" – код "001", а символ "О" – код "1".
при приеме "0100010100001" им сначала отделяется первый символ "Б" :
"01-00010100001", затем снова начиная с вершины дерева – "А" "01-00010100001", затем аналогично декодируется вся запись "01-000-1-01-00001" "БАОБАБ".

7. Алгоритм Лемпеля-Зива

Классический алгоритм Лемпеля-Зива – LZ77,
названный так по году своего опубликования,
предельно прост. Он формулируется следующим
образом : "если в прошедшем ранее выходном
потоке уже встречалась подобная
последовательность байт, причем запись о ее
длине и смещении от текущей позиции короче чем
сама эта последовательность, то в выходной
файл записывается ссылка (смещение, длина), а
не сама последовательность".
Так фраза "КОЛОКОЛ_ОКОЛО_КОЛОКОЛЬНИ"
закодируется как "КОЛО(-4,3)_(-5,4)О_(-14,7)ЬНИ".

8. Асимметричные криптоалгоритмы

2.4.1. Общие сведения об асимметричных криптоалгоритмах
Каждый пользователь асимметричной криптосистемы предварительно создает по
определенному алгоритму пару ключей : закрытый и открытый – они будут в
дальнейшем использоваться для отправки писем именно ему. Для отправки письма
другому абоненту сети необходимо будет воспользоваться именно его открытым
ключом.
2.4.2. Алгоритм RSA
Алгоритм RSA является классикой асимметричной криптографии. В нем в качестве
необратимого преобразования отправки используется возведение целых чисел в
большие степени по модулю.
2.4.3. Технологии цифровых подписей
Асимметричная криптография, как оказалось, позволяет очень красиво решать и
задачу аутентификации автора сообщения – простым изменением порядка
использования открытого и закрытого ключей.
2.4.4. Механизм распространения открытых ключей
Асимметричная криптография сделала еще и достаточно мощный прорыв в
технологии первоначального распространения ключей. Если для симметричных
криптосистем обязательным был предварительный обмен по закрытому каналу
(обычно лично из рук в руки), то теперь появились совершенно новые способы для
этого.
2.4.5. Обмен ключами по алгоритму Диффи-Хеллмана
Метод Диффи-Хеллмана использует алгоритм, подобный алгоритму RSA, для
первоначального обмена ключами в симметричных криптосистемах по открытому
каналу, но только такому, в котором невозможна фальсификация сообщений.

9. Алгоритм RSA

Алгоритм RSA стоит у истоков асимметричной криптографии. Он был
предложен тремя исседователями-математиками Рональдом Ривестом
(R.Rivest) , Ади Шамиром (A.Shamir) и Леонардом Адльманом
(L.Adleman) в 1977-78 годах.
Первым этапом любого асимметричного алгоритма является создание
пары ключей : открытого и закрытого и распространение открытого
ключа "по всему миру". Для алгоритма RSA этап создания ключей
состоит из следующих операций :
Выбираются два простых (!) числа p и q
Вычисляется их произведение n(=p*q)
Выбирается произвольное число e (e<n), такое, что НОД(e,(p-1)(q-1))=1,
то есть e должно быть взаимно простым с числом (p-1)(q-1).
Методом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q1)*y=1. Здесь неизвестными являются переменные d и y – метод
Евклида как раз и находит множество пар (d,y), каждая из которых
является решением уравнения в целых числах.
Два числа (e,n) – публикуются как открытый ключ.
Число d хранится в строжайшем секрете – это и есть закрытый ключ,
который позволит читать все послания, зашифрованные с помощью
пары чисел (e,n).

10. Основные алгоритмы сжатия информации:

Если говорить об алгоритмах сжатия, то будем иметь ввиду обратимые
алгоритмы.
Алгоритм RLE (Run-Length Encoding) использует принцип выявления
повторяющихся последовательностей. При сжатии записывается
последовательность из двух повторяющихся величин: повторяемого
значения и количества его повторений.
Пример:
Исходная последовательность: 3, 3, 12, 12, 12, 0, 0, 0, 0.Сжатая
информация: 3, 2, 12, 3, 0, 4.Коэффициент сжатия: 6/9*100% = 67%.
Алгоритм KWE (Keyword Encoding) предполагает использование словаря,
в котором каждому слову соответствует двухбайтовый код. Эффективность
сжатия увеличивается с ростом объема кодируемого текста. Алгоритм
Хафмана предполагает кодирование не байтами, а битовыми группами. В
нем можно выделить три основные этапа:
1)Выявляется частота повторения каждого из встречающихся символов.
2)Чем чаще встречается символ, тем меньшим количеством битов он
кодируется.
3)К закодированной последовательности прикладывается таблица
соответствия.

11. ..:О сжатии данных:..

Целью процесса сжатия, как правило, есть получение более
компактного выходного потока информационных единиц из
некоторого изначально некомпактного входного потока при
помощи некоторого их преобразования. Основными
техническими характеристиками процессов сжатия и
результатов их работы являются:
1)степень сжатия (compress rating) или отношение (ratio)
объемов исходного и результирующего потоков;
2)скорость сжатия - время, затрачиваемое на сжатие
некоторого объема информации входного потока, до
получения из него эквивалентного выходного потока;
3)качество сжатия - величина, показывающая на сколько
сильно упакован выходной поток, при помощи применения к
нему повторного сжатия по этому же или иному алгоритму.

12. ..:Способы сжатия по алгоритмам:..

Сжатие способом кодирования серий
(RLE)
Наиболее известный простой подход и
алгоритм сжатия информации обратимым
путем - это кодирование серий
последовательностей (Run Length
Encoding - RLE). Суть методов данн

13. Алгоритм Хаффмана

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

14. 3) Арифметическое кодирование

Совершенно иное решение предлагает т.н. арифметическое
кодирование. Арифметическое кодирование является методом,
позволяющим упаковывать символы входного алфавита без
потерь при условии, что известно распределение частот этих
символов и является наиболее оптимальным, т.к. достигается
теоретическая граница степени сжатия.
Предполагаемая требуемая последовательность символов, при
сжатии методом арифметического кодирования
рассматривается как некоторая двоичная дробь из интервала [0,
1). Результат сжатия представляется как последовательность
двоичных цифр из записи этой дроби. Идея метода состоит в
следующем: исходный текст рассматривается как запись этой
дроби, где каждый входной символ является "цифрой" с весом,
пропорциональным вероятности его появления. Этим
объясняется интервал, соответствующий минимальной и
максимальной вероятностям появления символа в потоке.

15. 4)Алгоритм Лемпеля-Зива-Велча (Lempel-Ziv-Welch - LZW)

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

16. 5) Двухступенчатое кодирование. Алгоритм Лемпеля-Зива

Гораздо большей степени сжатия можно добиться при выделении из
входного потока повторяющихся цепочек - блоков, и кодирования ссылок на
эти цепочки с построением хеш таблиц от первого до n-го уровня.
Метод, о котором и пойдет речь, принадлежит Лемпелю и Зиву и обычно
называется LZ-compression. Суть его состоит в следующем: упаковщик
постоянно хранит некоторое количество последних обработанных
символов в буфере. По мере обработки входного потока вновь
поступившие символы попадают в конец буфера, сдвигая предшествующие
символы и вытесняя самые старые. Размеры этого буфера, называемого
также скользящим словарем (sliding dictionary), варьируются в разных
реализациях кодирующих систем. Экспериментальным путем установлено,
что программа LHarc использует 4-килобайтный буфер, LHA и PKZIP - 8-ми,
а ARJ - 16-килобайтный. Затем, после построения хеш таблиц алгоритм
выделяет (путем поиска в словаре) самую длинную начальную подстроку
входного потока, совпадающую с одной из подстрок в словаре, и выдает на
выход пару (length, distance), где length - длина найденной в словаре
подстроки, а distance - расстояние от нее до входной подстроки (то есть
фактически индекс подстроки в буфере, вычтенный из его размера).

17. Перечень программ сжатия с кратким указанием алгоритмов их работы:

PKPAK 3.61: Метод Packed -- алгоритм RLE. Метод
Crunched -- алгоритм LZW. Метод Squashed -двухпроходное статическое кодирование Хаффмена
PKZIP 1.10: Метод Shrinked -- модифицированный алгоритм
LZW с частичной очисткой словаря и переменной длиной
кода. Метод Imploded -- модифицированный алгоритм
Лемпеля-Зива и статическое кодирование Хаффмена.
LHArc: Алгоритм Лемпедя-Зива и динамическое
кодирование Хаффмена.
LHA: Алгоритм Лемпедя-Зива и статическое кодирование
Хаффмена.
ARJ: Алгоритм Лемпеля-Зива и оригинальный метод
кодирования

18.

Были рассмотрели основные алгоритмы
архивации.

19. ..:Архивация файлов и папок:..

В процессе архивации создается резервная копия данных. Для
архивации в файл необходимо задать имя файла и место, где
он будет сохранен. Файл архива можно сохранить на жестком
диске, дискете или на любом другом съемном либо несъемном
носителе, на котором возможно сохранение файлов.
Следующие три шага описывают простую операцию архивации:
1)Выберите файлы, папки и диски для архивации
2)В программе архивации диски, файлы и папки компьютера
представлены в виде дерева, позволяющего выбирать файлы и
папки для архивации. Открытие папок и выбор файлов в этом
дереве выполняется так же, как и в проводнике Windows.
3)Выберите носитель или файл для создания архива данных

20. Задайте параметры архивации:

1)Окно Параметры программы архивации позволяет
настраивать параметры архивации. Чтобы настроить
архивацию, выполните в окне Параметры следующие действия.
2)Выберите требуемый тип архивации. Существуют следующие
типы архивации: копирующий, ежедневный, разностный,
добавочный и обычный.
3)Укажите, требуется ли вести журнал архивации. Если ведется
файл журнала, можно также выбрать запись всех либо только
основных событий.
4)Укажите, требуется ли архивировать данные, хранящиеся на
присоединенных дисках.
5)Назначьте типы файлов, которые требуется исключить из
операции архивирования.
6)Укажите, требуется ли проверять правильность архивации
данных.

21. ..:О назначении Архиваторов:..

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

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

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

23. Для архивирования используются специальные программы - архиваторы или диспетчеры архивов

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