Оглавление
Введение. 3
1. Понятие архивации. Характеристика методов архивации. 4
2. Методы архивации и сжатия данных. 7
2.1 Метод RLE. 7
2.2 Метод Хаффмана. 8
Заключение. 11
Список литературы. 12
Введение
С давних времен хранение и передача информации были важными вопросами для человечества. В качестве носителей информации использовались камни, глиняные и деревянные дощечки, кожа животных, бумага и т.д. В современном мире широкое распространение получили персональные компьютеры и электронные гаджеты .С каждым годом объёмы информации увеличиваются. Благодаря техническому прогрессу и развитию технологий современные компьютеры позволяют обрабатывать всё большие и большие массивы данных. Для хранения информации требуется всё больше носителей. Поэтому архивация и сжатие данных являются важнейшими вопросами информатики.
1. Понятие архивации. Характеристика методов архивации
Архивация – это совокупность процессов подготовки и обработки данных, которая включает в себя сбор, классификацию, каталогизацию и сжатие информации для последующего хранения или передачи. Основной целью архивации является создание резервных копий наиболее ценных документов, а также уменьшение занимаемого ними места на диске.
Архивация файлов — перекодирование данных с целью уменьшения их объёма без значительных информационных потерь. Архивный файл представляет собой совокупность исходных файлов, обработанных с помощью специального алгоритма, а также оглавление, в котором указан список этих файлов. При необходимости архивный файл позволяет восстановить хранящиеся в нём файлы в исходном виде.
Процесс архивации основан на устранении избыточности, содержащейся в исходной информации. Элементарным примером избыточности является повторение одинаковых слов в тексте. Подобная избыточность устраняется путем замены повторяющейся последовательности ссылкой на закодированный фрагмент с указанием его длины. Другой вид избыточности проявляется в наличии значений, который встречаются в исходных данных чаще остальных. Для уменьшения подобной избыточности, часто встречающиеся значения заменяются короткими кодовыми словами, а редко встречающиеся – длинными. Данный тип кодирования называется энтропийным. Исходя из этого, можно сделать вывод, что данные, не имеющие избыточности невозможно сжать без потерь.
2. Методы архивации и сжатия данных
2.1 Метод RLE
Метод RLE (Run Length Encoding) является одним из самых быстрых и простых и понятных алгоритмов сжатия информации. В некоторых случаях он является достаточно эффективным. Данный метод применяется для сжатия изображений в формате PCX. Принцип работы этого алгоритма можно описать так: последовательность повторяющихся символов заменяется последовательностью из трёх байт – байта prefix, указывающего, что встретилась последовательность повторяющихся символов, байта length, указывающего длину последовательности и байта symbol, указывающего собственно символ, из которых состоит последовательность.
Рассмотрим работу данного алгоритма на примере конкретной: шестнадцатеричной последовательности
05 05 05 05 05 01 01 03 03 03 03 03 03 05 03 FF FF FF FF
из 20 байт. Выберем в качестве префикса байт FF. Тогда на выходе архиватора мы получим последовательность
FF 05 05 FF 02 01 FF 06 03 FF 01 05 FF 01 03 FF 04 FF
Длина выходной последовательности - 18 байт, соответственно достигнуто некоторое сжатие. Однако, нетрудно заметить, что при кодировании некоторых символов размер выходного кода возрастает (например, вместо 01 01 - FF 02 01). Очевидно, что последовательности повторяющиеся символов длиною менее четырёх кодировать бессмысленно - их надо записывать в явном виде. Получим новую последовательность:
FF 06 05 01 01 FF 06 03 05 03 FF 04 FF
2.2 Метод Хаффмана
Метод Хаффмана – это адаптивный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью, разработанный в 1952 году Дэвидом Хаффманом. Данный метод применяется во многих архиваторах и форматах фалов. Этот метод основан на том, что различные символы любого алфавита имеют разную вероятность появления в тексте. Для примера - в русском языке буква "А" встречается намного чаще, чем "Ъ". Итак, раз разные символы имеют разные вероятности появления, следовательно, если кодировать их не все по 8 бит, как они хранятся в ASCII формате, а длину кода наиболее часто встречаемых уменьшить за счёт увеличения длины кода редких символов - можно сжать исходный текст.
Рассмотрим алгоритм кодирования информации, применяемый в методе Хаффмана на примере фразы «beep boop beer!». Прежде всего формируется алфавит символов с частотой появления каждого символа в тексте. Далее символы сортируются по убыванию частоты появления:
“e” - 4, “b” - 3, “ “ - 2, “o” – 2, “p” – 2, “r” – 1, “!” – 1
Далее формируется так называемое дерево Хаффмана. Для его построения применяется следующий алгоритм:
-
Из списка выбирается два узла с наименьшей частотой появления
-
Формируется новый узел и присоединяется к нему, в качестве дочерних, два узла выбранных из списка. При этом частоту появления сформированного узла положим равной сумме частот дочерних узлов.
-
Добавим сформированный узел к списку.
-
Если в списке больше одного узла, то повторить 1-3.
Заключение
В заключении следует отметить, что количество информации в современном мире растёт с каждым днём, поэтому вопрос сжатия и архивации данных является очень важным. Практически любая информация имеет избыточность. Современные методы и алгоритмы кодирования информации позволяют снизить избыточность до нуля.
Различают сжатие с потерями и без потерь. Сжатие без потерь позволяет восстановить информацию в исходном виде, но сжатие с потерями в некоторых случаях является гораздо более эффективным.
Алгоритмы сжатия информации бывают статичными и адаптивными. Статичные методы более простые и менее ресурсоёмкие, однако адаптивные являются более универсальными и эффективными.
