Материал: Модели и алгоритмы проектирования и разработки систем поддержки принятия инвестиционных решений. Морозов В.П., Баркалов С.А

Да

7

Сохранение оператив-

ных данных

8

Конец

Рис. 2.12. Блок-схема алгоритма оптимизации доступа

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

Блок 6 используется для поиска запрашиваемых данных в ХД. В случае их наличия последние перемещаются из ХД в ВД, распаковываются (разархивируются) и предоставляются пользователю для дальнейшей работы.

Блок 7 реализует запись полученных оперативных данных вВД. Большое значение при архивации данных имеет определение последова-

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

Для оценки вероятности поступления запроса использовано предположение о том, что запросы формируют поток событий, подчиняющийся статистике простого пуассоновского потока [1]. В рамках данного предположения интенсивность потока (количества событий в единицу времени) запросов на i-й набор данных определяется в соответствии со следующей эмпирической оценкой:

76

ступления данных в архив, tNi – время поступления Ni -го запроса. Вероятность

поступления запроса на i-й набор данных при интенсивности потока заказов i в момент времени t tNi определяется выражением (вероятность единичного

Полученныеоценкиопределяютрангнабораданных.Длямножестваиз Kнаборовданныхранжированиесводитсяксортировкеданныхвсоответствиисправилом:

pi pj , при i<j для любых i 1,K; j 1,K . (2.28)

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

Предложенныйподходреализованввиденаборапроцедур,обеспечивающих:

1)контроль ресурсовВД;

2)расчет ранга популярности данных;

3)автоматический перенос данных, инициируемых процедурами контроля состоянияВД.

Модуль архивации данных используется в интересах архивации и распаковки данных, соответственно при их передаче и приеме в ХД. Обобщенная схема классификация методов сжатия информации приведена на рис. 2.13.

Подробное обоснование методов архивации данных приведено в [154]. Анализ эффективности архиваторов, базирующихся на методах сжатия

данных, представленных на рис. 2.13 и используемых на практике, показал следующее. Оценивались следующие архиваторы [24]:

-7-Zip, автор Игорь Павлов (Pavlov);

-АСЕ, автор Маркел Лемке (Weinke);

-ARJ, автор Роберт Джанг (Jung);

-ARJZ, автор Булат Зиганшин (Ziganshin);

-CABARC, корпорация Microsoft;

-Imp, фирма Technelysium Pty Ltd.;

-JAR, автор Роберт Джанг (Jung);

-PKZIP, фирма PKWARE Inc.;

-RAR, автор Евгений Рошал (Roshal);

-WinZip, фирма Nico Mak Computing;

-1Zip, Info-ZIP group.

77

Методы сжатия

данных

Данные архиваторы являются или одними из самых эффективных в классе, применяющих методы Зива-Лемпела, или пользуются популярностью, или оказали существенное влияние на развитие словарных алгоритмов, или интересны с точки зрения нескольких указанных критериев.

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

Коэффициент сжатия оценивался с помощью набора файлов, получивше-

го название Calgary Compression Corpus2 (CalgCC). В состав CalgCC входят файлы различных типов данных. Набор состоит из 14 файлов, большая часть которых представляет собой тексты на английском языке или языках программирования [24].

При проведении исследований применялся тот алгоритм, который обеспечивал наилучшее сжатие. Следует отметить, что 7-Zip использует специальные методы препроцессинга нетекстовых данных, "отключить" которые не удалось, что до некоторой степени исказило картину. Тем не менее преимущество этого архиватора на данном тестовом наборе несомненно. В случае WinRAR и АСЕ режим мультимедийной компрессии намеренно не включался.

Полученные результаты показали, что скорость сжатия ARJ и PKZIP была примерно в 4,5 раза выше, чем у RAR и АСЕ, которые, в свою очередь, были

78

Таблица 2.8 Сравнительная характеристика архиваторов по степени сжатия файлов,

времени кодирования и декодирования специального набора

быстрее CABARC и 7-Zip приблизительно на 30 %. Размер словаря в ARJ и PKZIP в десятки раз меньше, чем в остальных программах.

Для Ткод и Тдек за единицу принято время сжатия всего CalgCC архиватором 7-Zip. Следует отметить, что единица соответствует скорости кодирования 2 Гб/с для ПК с процессором типа Pentium IV 2,8 ГГц, объемe оперативной памяти 1 ГГц, частоте шины 800 МГц, объемe жесткого диска 160 ГГб.

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

Среди исследуемых архиваторов рассматривались PKZIP, RAR и 7-Zip. В настоящее время они находят наибольшее распространение и являются представителями определенных диапазонов значений коэффициентов сжатия дан-

79

ных (см. табл. 2.8).

В табл. 2.9 приведены результаты сравнения архиваторов по степени сжатия файлов на реальном наборе данных, состоящем из 18 файлов фиксированного размера 1639139 байт. Анализ полученных данных показывает, что они незначительно отличаются от данных, приведенных в табл. 2.8 (на десятые доличто повышает степень доверия к полученным результатам.

Таблица 2.9 Результаты сравнения архиваторов по степени сжатия файлов

на реальном наборе данных

Лучшие характеристики продемонстрировал архиватор 7-Zip. Ему незначительно уступает RAR.

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

По результатам проведенных экспериментов для архивации данных при пересылке последних из оперативного хранилища в долговременное хранилище был выбран алгоритм 7-Zip.

Модуль резервирования данных обеспечивает резервное копирование данных из ХД и ВД на внешние носители информации (жесткие магнитные

80