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

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

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

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

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

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

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

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