Архивация данных: основные алгоритмы архивации данных. - презентация

1 Архивация данных: основные алгоритмы архивации данных

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

3 Понятие архиватора Архиватор это программа, осуществляющая упаковку одного и более файлов в архив или серию архивов для удобства переноса или хранения, а также распаковку архивов.

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

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

6 Алгоритм Хаффмана Метод Хаффмана учитывает вероятность появление объектов и кодирует их кодами различной длины. Например, в русском алфавите буквы О,Е,А встречаются часто, Ф, Ц,Щ,Э – редко Чем чаще используется буква тем короче используется для нее код Такой принцип кодирования применяется в азбуке Морзе: Е * А * - Э * * - * *

7 Алгоритм Лемпеля-Зива-Велча (Lempel-Ziv-Welch - LZW) Данный алгоритм изобрели в 1977 году математики Абрахам Лемпел и Якоб Зив, а 1984 году его доработал Терри Велч Этот метод является методом «скользящего окна». Алгоритм кодирует цепочки символов (узоры), помещая их в таблицу и заменяя более коротким кодом. Если такая цепочка встретилась вновь, то в выходной файл будет помещена не сама цепочка, а ее более короткий код. Данный алгоритм отличают высокая скорость работы как при упаковке, так и при распаковке.

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