Архивация данных — это сокращение фактических объёмов файлов, хранящих информацию, без существенной потери данных.
Введение
В процессе использования персональных компьютеров иногда бывает возможна утрата или искажение информационных данных, расположенных на различных носителях. Это возможно по причине неисправности жёсткого диска, неверной коррекции или неумышленного стирания файлов и так далее. Для уменьшения потерь в этих случаях, необходимо всегда создавать архивные копии применяемых файлов и периодически делать новые копии файлов, которые изменялись. Чтобы сохранить информационные архивы, можно применять внешние устройства памяти значительной ёмкости, позволяющие сделать копию жёсткого диска. Естественно, для защиты информации её можно просто дублировать, но это означает, что копии будут занимать такой же объём памяти, как и исходные файлы. То есть для копий необходимых файлов потребуются большие объёмы памяти на внешних носителях.
Удобнее применять для формирования копий специальные программные приложения, позволяющие архивировать (сжимать) файлы. Они дают возможность сэкономить место на информационных носителях, а также объединить наборы файлов совместного использования в единый файл архива, что существенно упрощает формирование архивов. Приложения информационной архивации применяют специализированные алгоритмы, которые называются алгоритмами сжатия данных. Они подразделяются на алгоритмы сжатия без информационных потерь и алгоритмы сжатия с информационными потерями. В первом случае информация при её разархивации будет восстановлена без всяких изменений, а во втором случае из информационного потока удаляются данные несущественно влияющие на смысл информации или полностью не воспринимаемые людьми (эти алгоритмы применяются для архивации аудио- и видео-файлов).
Известны два главных способа информационной архивации, исключающие потери:
- Использование алгоритма Хофмана.
- Использование алгоритма Лемпеля-Зива.
Но почти все самые распространённые архивационные программы, работающие без потерь, применяют синтез этой пары способов, а именно алгоритм LZH.
Алгоритм Хоффмана
Этот алгоритм базируется на том аспекте, что отдельные символы известного комплекта из 256-ти символов в случайно выбранных текстах встречаются более часто, чем все остальные символы. То есть, если для обозначения широко используемых символов применять укороченные битовые последовательности, а для обозначения не очень часто попадающихся символов удлиненные комбинации битов, то итоговый размер файла будет меньше. К примеру, английский алфавит обладает частотой использования, приведённой в таблице один. Коды, которые ему соответствуют, указаны там же.
Рисунок 1. Частота использования букв английского алфавита. Автор24 — интернет-биржа студенческих работ
Алгоритм Лемпеля–Зива
Стандартный алгоритм Лемпеля-Зива, обозначается как LZ77, где цифры являются годов выхода его в свет. Его формулировка достаточно проста и она следующая. Если в проходившем раньше информационном потоке уже была такая же последовательность байтов, и при этом данные о её длине и смещении от текущей позиции более короткие, чем сама эта последовательность, то в выходной файл пишется ссылка (величина смещения и длина), а не сама эта последовательность. Например, фраза
КОЛОКОЛ_ОКОЛО_КОЛОКОЛЬНИ будет кодироваться так:
КОЛО(-4, 3)_(-5, 4)0_(-14, 7)ЬНИ.
А строчка, содержащая одинаковые символы ААААААА будет кодироваться так:
А(-1, 6).
Алгоритмы сжатия изображений
Сначала для выполнения архивирования изображений применялись обычные алгоритмы, которые служили и служат сейчас для резервного копирования данных, формировании дистрибутивов и тому подобное. Данные алгоритмы выполняли архивацию данных без всяких изменений. Но с возникновением новых классов изображений эти алгоритмы уже не удовлетворяли архивационным требованиям. Большинство изображений фактически не изменялись в объёме, несмотря на их очевидную избыточность. Это стало толчком к появлению новой разновидности алгоритмов, которые выполняли сжатие с информационными потерями. Обычно, архивационный коэффициент и связанный с ним уровень потери качества в этих алгоритмах, возможно задать перед сжатием.
Одним из таких самых распространённых и очень продвинутых алгоритмов является JPEG. На практике он считается стандартом для полновесных цветных изображений. Алгоритм работает с областями восемь на восемь, у которых уровни цвета и яркости изменяются достаточно плавно. Поэтому при разложении матриц этих областей в ряд по косинусам значения имеют лишь первые коэффициенты. То есть, сжатие в данном алгоритме выполняется благодаря плавному изменению цвета в изображении. Основой алгоритма является дискретное косинусное преобразование, которое применяется к матрице изображения с целью формирования некой новой матрицы коэффициентов. А, чтобы восстановить исходное изображение, используется метод обратного преобразования.
Дискретное косинусное преобразование выполняет раскладку изображения по величине амплитуды определённых частот. Это позволяет при преобразовании получить матрицу, где часть коэффициентов близка к нулю, или равна ему. Помимо этого, несовершенство зрения человека позволяет выполнять аппроксимацию коэффициентов с более грубым приближением, что практически не влияет на видимое качество изображения.
Другой известный алгоритм называется фрактальная архивация. Он основан на том, что изображение представляется в сжатом формате при посредстве коэффициентов итерируемых функций. В обобщённом смысле, системы итерируемых функций являются набором трёхмерных аффинных операций, которые переводят один вид изображения в другой.
