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

Выходной код также  формируется несколько иначе (сравните с предыдущим описанием):

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

2. В выходной файл  помещается номер найденного  слова в словаре <positior>. Длина кода равна |position|=[logV] (бит);

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

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

Алгоритм PPM

 

Алгоритм PPM (prediction by partial matching) - это метод контекстно-ограниченного моделирования, позволяющий оценить вероятность символа в зависимости от предыдущих символов. Строку символов, непосредственно предшествующую текущему символу, будем называть контекстом. Модели, в которых для оценки вероятности используются контексты длиной не более чем N, принято называть моделями порядка N.

Вероятность символа может быть оценена в контекстах разных порядков. Например, символ "о" в контексте "to be or not t" может быть оценен в контексте первого порядка «t», в контексте второго порядка «_t», в контексте третьего порядка «t_t» и т.д. Он также может быть оценен в контексте нулевого порядка, где вероятности символов не зависят от контекста, и в контексте минус первого порядка, где все символы равновероятны. Контекст минус первого порядка используется для того, чтобы исключить ситуацию, когда символ будет иметь нулевую вероятность и не сможет быть закодирован. Это может случиться, если вероятность символа не будет оценена ни в одном из контекстов (что возможно, если символ в них ранее не встречался).

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

Второй подход называется «методом исключений». При этом подходе  сначала делается попытка оценить  символ в контексте самого высокого порядка. Если символ кодируется, алгоритм переходит к кодированию следующего символа. В противном случае кодируется «уход» и предпринимается попытка закодировать символ в контексте меньшего порядка. И так далее, пока символ не будет закодирован.

BWT - преобразование и компрессор

 

BWT-компрессор (Преобразование Барроуза – Уиллера) - сравнительно новая и революционная техника для сжатия информации (в особенности-текстов), основанная на преобразовании, открытом в 1983 г. и описанная в 1994 г.. BWT является удивительным алгоритмом. Во-первых, необычно само преобразование, открытое в научной области, далекой от архиваторов. Во-вторых, даже зная BWT, не совсем ясно, как его применить к сжатию информации. В-третьих, BW преобразование чрезвычайно просто. И, наконец, сам BWT компрессор состоит из "магической" последовательности нескольких рассмотренных ранее алгоритмов и требует, поэтому, для своей реализации самых разнообразных программных навыков.

BWT не сжимает данные, но преобразует блок данных в формат, исключительно подходящий для компрессии. Рассмотрим его работу на упрощенном примере. Пусть имеется словарь V из N символов. Циклически переставляя символы в словаре влево, можно получить N различных строк длиной N каждая. В нашем примере словарь-это слово V="БАРАБАН" и N=7. Отсортируем эти строки лексикографически и запишем одну под другой:

F L

АБАНБАР

АНБАРАБ

АРАБАНБ

БАНБАРА

БАРАБАН

НБАРАБА

РАБАНБА

Далее нас будут интересовать только первый столбец F и последний столбец L. Оба они содержат все те же символы, что и исходная строка (словарь). Причем, в столбце F они отсортированы, а каждый символ из L является префиксом для соответствующего символа из F.

Фактический "выход" преобразования состоит из строки L="РББАНАА" и первичного индекса I, показывающего, какой символ из L является действительным первым символом словаря V (в нашем случае I=2). Зная L и I можно восстановить строку V.

 

Кодирование Хаффмана

 

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

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево). Алгоритм построения Н-дерева прост и элегантен.

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

2. Выбираются два свободных  узла дерева с наименьшими  весами.

3. Создается их родитель  с весом, равным их суммарному  весу.

4. Родитель добавляется  в список свободных узлов, а  двое его детей удаляются из этого списка.

5. Одной дуге, выходящей  из родителя, ставится в соответствие  бит 1, другой - бит 0.

6. Шаги, начиная со  второго, повторяются до тех  пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Допустим, у нас есть следующая таблица частот:

 

15	7	6	6	5
А	Б	В	Г	Д

 

На первом шаге из листьев  дерева выбираются два с наименьшими  весами — Г и Д. Они присоединяются к новому узлу-родителю, вес которого устанавливается в 5+6 = 11. Затем узлы Г и Д удаляются из списка свободных. Узел Г соответствует ветви 0 родителя, узел Д — ветви 1.

На следующем шаге то же происходит с узлами Б и  В, так как теперь эта пара имеет  самый меньший вес в дереве. Создается новый узел с весом 13, а узлы Б и В удаляются из списка свободных. После всего этого дерево кодирования выглядит так, как показано на рис. 2.

 

Рис. 2. Дерево кодирования  Хаффмана после второго шага

 

На следующем шаге «наилегчайшей» парой оказываются узлы Б/В и Г/Д. Для них еще раз создается родитель, теперь уже с весом 24. Узел Б/В соответствует ветви 0 родителя, Г/Д—ветви 1.

На последнем шаге в списке свободных осталось только два узла — это А и узел (Б/В)/(Г/Д). В очередной раз создается родитель с весом 39 и бывшие свободными узлы присоединяются к разным его ветвям.

Поскольку свободным  остался только один узел, то алгоритм построения дерева кодирования Хаффмана завершается. Н-дерево представлено на рис. 3.

 

Рис. 3. Окончательное дерево кодирования Хаффмана

 

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

Дня данной таблицы символов коды Хаффмана будут выглядеть следующим образом.

А 0

Б 100

В 101

Г 110

Д 111

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

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

 

Заключение

Как показывает практика, резервирование базы данных лучше всего  проводить в «холодном» виде, когда перед резервированием БД закрывается. Такое резервирование лучше всего выполнять в ночное время, когда пользователей можно отключать от базы. Однако во многих случаях этот вариант неприемлем. Во-первых, базы данных сейчас нередко достигают в объеме сотен и тысяч гигабайт, поэтому их копирование требует слишком много времени, и даже ночи для этого не хватит. Блокировать же доступ к базе на длительное время могут позволить себе немногие. Во-вторых, нередко СУБД работают в режиме on-line (например, на серверах Internet), и отключение их в принципе невозможно.

Чтобы нивелировать проблемы копирования баз данных, производители систем резервирования поставляют специальные агенты для конкретных СУБД. Большинство агентов рассчитано на поддержку таких СУБД, как Oracle, Informix, Sybase. В свою очередь разработчики мощных СУБД снабжают свои продукты программными интерфейсами резервирования или даже отдельными утилитами резервирования. К сожалению, распространенные системы резервирования поддерживают ограниченное количество основных СУБД ввиду экзотичности остальных (в смысле узости рынка). К сожалению, сами производители СУБД не очень-то стремятся восполнить данный пробел. К тому же огромное количество сетевых приложений опирается на собственные базы данных (например, Lotus Notes), найти для них агенты резервирования также может оказаться непросто.

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

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

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

 

 

Список литературы

 

1. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. - М.: ДИАЛОГ-МИФИ, 2010. - 384 с.
2. Сэломон Д. Сжатие данных, изображений и звука. Data Compression Methods. Серия: Мир программирования. Издательство: Техносфера, 2009. - 368 с.
3. Артюшенко В. М., Шелухин О. И., Афонин М. Ю. Цифровое сжатие видеоинформации и звука. Издательство: Дашков и Ко, 2009. - 426 с.
4. Седжвик Р. Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск. Издательство: ДиаСофт, 2010. - 688 с.

 

Приложения