Резервное копирование и архивация. Назначение. Обратимые и необратимые методы сжатия данных

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

1. Аппаратные поломки, особенно поломка дисководов. Несмотря на то что за последнее время надежность аппаратных средств значительно увеличилась, аварии и сбои тем не менее по-прежнему происходят.

2. Ошибки и сбои в операционных системах и прикладном программном обеспечении. В любом ПО всегда имеются ошибки, при определенных условиях они могут привести к порче данных.

3. Вирусы и «троянские кони». Очень распространенная причина потери информации, особенно в системах Windows. Однако и в других ОС разного рода закладки и «троянские кони» не раз приводили к таким серьезным последствиям, как утрата или несанкционированное изменение информации.

4. Непреднамеренное уничтожение данных. По статистике — самая распространенная причина потери информации (по некоторым источникам, до 75% информации теряется в результате ошибок пользователей или обслуживающего персонала).

5. Преднамеренное уничтожение информации в результате атак злоумышленников. Проблема не столько в недостатках приложений и ОС, сколько в неверном конфигурировании системы безопасности.

Использование системы  резервного копирования на внешние  носители вовсе не обязательно может быть вызвано всеми перечисленными причинами, с некоторыми из них можно бороться другими способами. Уменьшить риск потери информации в результате поломок оборудования и в некоторых случаях сбоев ПО позволяет применение таких отказоустойчивых конфигураций, как массивы RAID и кластеры. Однако от таких опасностей, как вирусы, ошибки пользователей или атаки хакеров, отказоустойчивые решения не спасают. А ведь, как говорилось выше, именно непреднамеренное уничтожение данных является самой распространенной причиной потери информации. Далеко не всегда оно заканчивается потерей всего одного-двух пользовательских файлов, хотя и это тоже неприятно. В нашем издательстве за последний год два раза имели место такие случаи, когда, находясь в корневом каталоге (/), системный администратор UNIX по небрежности выполнял команду:

rm   -r   *

полагая, что он находится  в другом месте файловой системы. Самый надежный способ обезопасить себя от подобных ошибок, вирусов и атак хакеров состоит в использовании систем резервного копирования.

Технические проблемы резервного копирования связаны не столько  с самим резервным копированием, сколько с процессом восстановления данных после аварии. Как справедливо отмечает Куртис Престон, написавший одну из самых толковых книг по резервному копированию UNIX, основной недостаток литературы по резервному копированию связан с тем, что только 10% объема книг отводится процедуре восстановления данных, а остальная часть посвящена самому процессу резервного копирования. Таким образом, даже при наличии резервных копий в процессе восстановления информации администратор сталкивается с массой проблем.

Новые функции архивации и восстановления данных в составе Microsoft Windows Vista упрощают задачу защиты данных и компьютера от пользовательских ошибок, аппаратных сбоев и других проблем, которые могут привести к потере данных.

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

Все функции собраны на унифицированной  панели архивации и восстановления. С нее можно запустить новое средство автоматической архивации для создания резервных копий файлов, а затем выполнить поиск файлов, которые необходимо восстановить из резервной копии.

Еще одна новая функция позволяет  получать доступ к более ранним версиям файлов, даже если раньше они не архивировались. Эта функция построена на основе технологии теневого копирования тома, впервые реализованной в системах семейства Windows Server. Кроме того, в Windows Vista реализована функция создания архивного образа всего ПК, получившая название «Архивация CompletePC», которая дополняет функции архивации файлов и является важным средством на случай аварийного восстановления системы.

С помощью обновленной и более  надежной функции восстановления системы  можно отменить внесенные в систему изменения, не повреждая данных пользователя. Кроме того, используя среду восстановления Windows, которая устанавливается многими производителями на новых ПК, функция «Восстановление системы» обеспечивает даже устранение неполадок, препятствующих загрузке системы.

2. Обратимые и необратимые методы  сжатия данных

Целью процесса сжатия, как  правило, есть получение более компактного выходного потока информационных единиц из некоторого изначально некомпактного входного потока при помощи некоторого их преобразования. Основными техническими характеристиками процессов сжатия и результатов их работы являются:

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

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

Под необратимым сжатием подразумевают такое преобразование входного потока данных, при котором выходной поток, основанный на определенном формате информации, представляет, с некоторой точки зрения, достаточно похожий по внешним характеристикам на входной поток объект, однако отличается от него объемом. Степень сходства входного и выходного потоков определяется степенью соответствия некоторых свойств объекта (т.е. сжатой и несжатой информации в соответствии с некоторым определенным форматом данных), представляемого данным потоком информации. Такие подходы и алгоритмы используются для сжатия, например данных растровых графических файлов с низкой степенью повторяемости байтов в потоке. При таком подходе используется свойство структуры формата графического файла и возможность представить графическую картинку приблизительно схожую по качеству отображения (для восприятия человеческим глазом) несколькими (а точнее n) способами. Поэтому, кроме степени или величины сжатия, в таких алгоритмах возникает понятие качества, т.к. исходное изображение в процессе сжатия изменяется, то под качеством можно понимать степень соответствия исходного и результирующего изображения, оцениваемая субъективно, исходя из формата информации. Для графических файлов такое соответствие определяется визуально, хотя имеются и соответствующие интеллектуальные алгоритмы и программы. Необратимое сжатие невозможно применять в областях, в которых необходимо иметь точное соответствие информационной структуры входного и выходного потоков. Данный подход реализован в популярных форматах представления видео и фото информации, известных как JPEG и JFIF алгоритмы и JPG и JIF форматы файлов.

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

В обратимых алгоритмах кодирование, как процесс, можно  рассматривать со статистической точки  зрения, что еще более полезно  не только для построения алгоритмов сжатия, но и для оценки их эффективности. Для всех обратимых алгоритмов существует понятие стоимости кодирования. Под стоимостью кодирования понимается средняя длина кодового слова в битах. Избыточность кодирования равна разности между стоимостью и энтропией кодирования, а хороший алгоритм сжатия всегда должен минимизировать избыточность (под энтропией информации понимают меру ее неупорядоченности.). Фундаментальная теорема Шеннона о кодировании информации говорит о том, что "стоимость кодирования всегда не меньше энтропии источника, хотя может быть сколь угодно близка к ней". Поэтому, для любого алгоритма, всегда имеется некоторый предел степени сжатия, определяемый энтропией входного потока.

3. Основные алгоритмы сжатия данных

Алгоритм LZ77

Этот словарный алгоритм сжатия является самым старым среди методов LZ. Описание было опубликовано в 1977 г., но сам алгоритм разработан не позднее 1975 г.

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

Скользящее окно имеет  длину N, т. е. в него помещается N символов, и состоит из двух частей:

■ последовательности длины W=N-n уже закодированных символов, которая и является словарем;

■ упреждающего буфера, или буфера предварительного просмотра, длины n; обычно и на порядки меньше W.

Пусть к текущему моменту  времени мы уже закодировали t символов S₁, S₂, ...,S_t. Тогда словарем будут являться W предшествующих символов S_t-(W-1), S_t-(W-1)+1, …, S_t. Соответственно, в буфере находятся ожидающие кодирования символы S_t+1, S_t+2, …, S_t+n. Очевидно, что если W≥ t, то словарем будет являться вся уже обработанная часть входной последовательности.

Идея алгоритма заключается  в поиске самого длинного совпадения между строкой буфера, начинающейся с символа S_t+1, и всеми фразами словаря. Эти фразы могут начинаться с любого символа S_t-(W-1), S_t-(W-1)+1,…, S_t выходить за пределы словаря, вторгаясь в область буфера, но должны лежать в окне. Следовательно, фразы не могут начинаться с S_t+1. поэтому буфер не может сравниваться сам с собой. Длина совпадения не должна превышать размера буфера. Полученная в результате поиска фраза S_t-(i-1), S_t-(i-1)+1, …, S_{t-(i-1)+(j-1)} кодируется с помощью двух чисел:

1) смещения (offset) от начала буфера, i;

2) длины соответствия, или совпадения (match length), j;

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

Таким образом, на каждом шаге кодер выдает описание трех объектов: смещения и длины соответствия, образующих код фразы, равной обработанной строке буфера, и одного символа s (литерала). Затем окно смещается на j+1 символов вправо и осуществляется переход к новому циклу кодирования. Величина сдвига объясняется тем, что мы реально закодировали именно j+1 символов: j с помощью указателя на фразу в словаре и 1(? i) с помощью тривиального копирования. Передача одного символа в явном виде позволяет разрешить проблему обработки еще ни разу не виденных символов, но существенно увеличивает размер сжатого блока.

Алгоритм LZ78-LZW84

Алгоритм LZ78, предложенный в 1978 г. Лемпелом и Зивом, нашел свое практическое применение только после реализации LZW84, предложенной Велчем в 1984 г.

Словарь является расширяющимся (expanding). Первоначально в нем содержится только 256 строк длиной в одну букву-все коды ASCII. В процессе работы словарь разрастается до своего максимального объема |V_max| строк (слов). Обычно, объем словаря достигает нескольких десятков тысяч слов. Каждая строка в словаре имеет свою известную длину и этим похожа на привычные нам книжные словари и отличается от строк LZ77, которые допускали использование подстрок. Таким образом, количество слов в словаре точно равно его текущему объему. В процессе работы словарь пополняется по следующему закону:

1. В словаре ищется  слово str, максимально совпадающее с текущим кодируемым словом в позиции pos исходного текста. Так как словарь первоначально не пустой, такое слово всегда найдется;

2. В выходной файл помещается номер найденного слова в словаре position и следующий символ из входного текста В (на котором обнаружилось различие) - <position,B>. Длина кода равна |position|+|B||=[logVmax]+8 (бит);

3. Если словарь еще  не полон, новая строка strВ добавляется в словарь по адресу last_position, размер словаря возрастает на одну позицию;

4. Указатель в исходном  тексте pos смещается на |strB|=|str|+l байт дальше к символу, следующему за В.

В таком варианте алгоритм почти не нашел практического  применения и был значительно модернизирован. Изменения коснулись принципов управления словарем (его расширения и обновления) и способа формирования выходного кода:

Птак как словарь  увеличивается постепенно и одинаково  для кодировщика и декодировщика, для кодирования позиции нет необходимости использовать [logV_max] бит, а можно брать лишь [logV] бит, где V-текущий объем словаря.

Самая серьезная проблема LZ78-переполнение словаря: если словарь полностью заполнен, прекращается его обновление и процесс сжатия может быть заметно ухудшен (метод FREEZE). Отсюда следует вывод-словарь нужно иногда обновлять. Самый простой способ как только словарь заполнился его полностью обновляют. Недостаток очевиден кодирование начинается на пустом месте, как бы с начала, и пока словарь не накопится сжатие будет незначительным, а дальше-замкнутый цикл опять очистка словаря!.. Поэтому предлагается словарь обновлять не сразу после его заполнения, а только после того, как степень сжатия начала падать (метод FLUSH). Более сложные алгоритмы используют два словаря, которые заполняются синхронно, но с задержкой на |V|/2 слов один относительно другого. После заполнения одного словаря, он очищается, а работа переключается на другой (метод SWAP). Еще более сложными являются эвристические методы обновления словарей в зависимости от частоты использования тех или иных слов (LRU, TAG).