автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Автоматическое сжатие данных в вычислительных системах

п

V г-'! "!-'-.'■■'.'■ ■

На правах рукописи

МАСТРЮКОВ Дмитрий Львович

Автоматическое сжатие данных в вычислительных системах

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Автор:

Научный руководитель: доктор технических наук, профессор Перминоз Олег Николаевич

МОСКВА - 1996

Работа выполнена в Московском государственном инженерно-физическом институте (техническом университете).

Научный руководитель:

доктор технических наук, профессор Перминов Олег Николаевич.

Официальные оппоненты:

доктор технических наук, старший научный сотрудник Кузнецов Сергей Дмитриевич

кандидат технических наук, доцент Кларин Аркадий Павлович

Ведущая организация: .

Вычислительный центр РАН

Защита состоится ^Ау 1996 г. в часов && мин. на

заседании диссертационного совета Д053.03.04 в МИФИ по адресу: 115409, Москва, Каширское шоссе, д. 31, МИФИ, тел. 323-91-57, 324-84-98.

С диссертацией можно ознакомиться в библиотеке МИФИ.

Автореферат разослан * * 1996 г.

Просим принять участие в работе совета или прислать отзыв в одном

экземпляре, заверенный печатью организации.

Ученый секретарь диссертационного совета доктор технических наук, профессор

В.Э. Вольфенгагсн

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Сжатие данных может быть реализовано на разных уровнях иерархии . программного и аппаратного обеспечения вычислительного, комплекса. Сжатие на уровне • прикладной программы может быть достаточно эффективным, но приводит усложнению ео разработки и появлению закрытых форматов хранения данных. Сжатие на уровне системной утилиты, работающей в пакетном режиме, получило большое распространение; но требует достаточной квалификации пользователя. Размещение сжатия на аппаратном уровне хорошо зарекомендовало себя, но является достаточно дорогостоящим. Наиболее эффективным', с точки зрения автора, является размещение сжатия на уровне элемента операционной системы, так как оно лишено присущих предыдущим подходам недостатков, и хорошо вписывается в идеологию построения современных ОС, поддерживающих концепцию аппаратной независимости через программную прослойку между ОС и устройством, называемую драйвером устройства. Выполняя автоматическую компрессию/декомпрессию данных обмена ОС с устройством, драйвер может эмулировать устройство большего объема, нежели физический носитель. При таком подходе сжатие является невидимым ни для пользователей системы, ни для прикладных программ', работающих в ней, что позволяет значительно повысить эффективность использования пространства

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

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

Методы исследования. Основные. результаты диссертационной работы получены и математически обоснованы с использованием аппарата теории информации и кодирования, математического анализа и методов математического программирования, л

Научная новизна работы состоит в том, что впервые;

• предложена классификация существующих схем сжатия данных;

• предложена методика формальной оценки мощности адаптивных схем сжатия;

• предложен критерий оценки применимости схемы сжатия для работы в автоматическом режиме в компоненте ОС и критерий оценки сбалансированности реализации схемы сжатия;

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

• разработана и предложена адаптивная схема сжатия данных без потерь, определена ее мощность и проведено ее сравнение с существующими схемами по мощности;

• предложена эффективная реализация разработанной схемы со временем выполнения одного шага 0(1).

На защиту выносятся:

• новая методика автоматического сжатия данных без потерь в вычислительных системах

• новые методы формальной и экспериментальной оценки схем сжатия данных

• программный комплекс автоматического сжатия данных для накопителя на магнитном диске и результаты его практического использования

Практическая ценность. Разработанные в диссертации адаптивная схема сжатия данных и ее эффективная практическая реализация могут

■ иметь широкий спектр практического применения: от прикладных программ и использования в компоненте ОС .- до размещения в контроллерах внешних устройств, бортовых компьютерах и микропроцессорах. Реализованный на ПЭВМ IBM/PC программный комплекс автоматического сжатия данных на дисковом устройстве, позволяет в среднем удвоить эффективный объем накопителя на магнитном диске, при снижении средней производительности обмена с устройством на 20-30 процентов, позволяя таким образом программным путем увеличить "аппаратные" возможности вычислительного комплекса. Так как в настоящее время вычислительная техника устаревает морально значительно быстрее, чем физически, то использование разработанного комплекса позволяет продлить срок ее службы.

Внедрение. Эффективность разработанных в диссертационной работе методов интеграции автоматического сжатия в'структуру вычислительного комплекса подтверждена положительным опытом их практического использования. При непосредственном участии автора результаты работы были внедрены в вычислительном центре. ЦНИИ "Циклон", в конструкторских бюро электрозавода им. Куйбышева, а также в АОЗТ "Альтер Системы"

Личный оста д. Все основные положения и результаты, выносимые на заидоту, получены автором самостоятельно.

Апробпция работы. Результаты работы докладывались на ежегодной международной конференции Technology of Object-Oriented Languages and Systems'14, Santa-Barbara, CA, 1994 год.

Публикации. Основные результаты, полученные автором, опубликованы в работах [5],[8]. Результаты исследований опубликованы в . работах [1]-[4], [6]-[7]. Ссылки на указанные работы приведены в конце автореферата.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы. Работа содержит 110 стр., в том числе 107 стр. машинописного текста, 24 рисунка, 8 таблиц, а также список

литературы { 3 стр., наименования ).

СОДЕРЖАНИЕ РАБОТЫ

Во введении'обоснована актуальность темы, сформулированы цель исследований и основные проблемы, рассматриваемые в работе. Описаны структура диссертационной работы, взаимосвязь и краткое содержание ее .разделов. Приводятся основные положения, которые выносятся на защиту.

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

Термин сжатие данных здесь и далее будет обозначать процедуру их преобразования к более компактной форме, из которой в дальнейшем можно восстановить оригинал или некоторое приближение к нему. Будем называть, алфавитом А некоторое непустое конечное множество. Элементы алфавита будем называть символами. Строкой s над алфавитом А будем называть конечную последовательность символов j„ такую что для любого /', s, принадлежит Л. Определим меру близости строкs и s" над алфавитом А, как функцию М(s, s"), возвращающую 0 в случае, когда строки в точности совпадают, и некоторое число, характеризующее степень их различия, в противном случае. Пусть также F - преобразование строки s над алфавитом л в строку i' над алфавитом С, а F' - преобразование строки s' над алфавитом С а строку s" над алфавитом А. Будем называть схемой сжатия пару <F.F'>, такую что \M(s, f' (F(s))\ <= с, для заданного и >*-- С. Будем называть схемой сжатия без потерь пару <F,F'>, такую что \м(s, F'(F(s}}\ = и. Будем называть схемой сжатия с потерями пару <f,F'>, такую что 0 <\M(s. F'(F(s)J\<= с, для заданного е > 0. Общая схема процесса сжатия приведена на рисунке 1.

Символы Коды

Входной |_ поток 1 Модель |_^ Кодер S Выходной поток |

•

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

Сжатие данных в режиме off-line подразумевает, что модель сообщения полностью построена еще до начала процесса кодирования. При on-line или адаптивном' сжатии модель данных постоянно обновляется по мере

обработки и кодирования очередного фрагмента сообщения. Общая схема адаптивного сжатия приведена на рисунках 2-3. Рисууюх 2. Обиия схема процесса адаптивного сжатия

Символы-

Прочитать В символ

Закодировать символ

Обновить | модель

Выдать код

Модель |

Коды

Рисунок 3. Общая схема пррцесса адаптивной декомпрессии

Коды

код

Декоди- Обновить ]

ровать 1 модель

символ

5

-{ Модель"

Выдать символ

- Символы

Рисунок 4. Классификация'существующих схем сжатия данных

Схемы сжатия )

—»•{ С потерями )

—Звук ,|

—Н Фото I

—>•{ Видео"]

—«4 Без потерь )

Словарные

—Статический словарь } Скользящий словарь } —>•] Динамический словарь |

-ч

Статистические

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

Арифметическое кодирование

Двухуровневые (словарно-статистические)

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

Предлагаемая классификация существующих схем сжатия данных на основе используемых подходов к моделированию и кодированию приведена на рисунке 4. В статистических схемах сжатия модель сообщения содержит условные вероятности появления очередного символа в контексте нескольких предыдущих. Их количество определяет порядок модели. Простейшая статистическая модель порядка 0, основывается на независимых вероятностях появления символов. К классу статистических схем сжатия относятся адаптивное сжатие по Хаффмену, основанное на классическом алгоритме, предложенном Дэвидом Хаффменом в 1952 году, и адаптивное арифметическое кодирование, предложенное Элиасом в 1975 году как альтернатива методу Хаффмена, позволяющая устранить ряд недостатков своего предшественника, проявляющихся на сообщениях с большим разбросом вероятностей появления символов. И адаптивное сжатие по Хаффмену, и адаптивное арифметическое кодирование могут быть использованы во взаимодействии с моделью порядка > 0. Однако при линейном росте порядка модели, наблюдается степенной рост затрат памяти на ее хранение, что видимо еще долгое время будут сдерживать широкое, распространение подобных методов. Словарные схемы получили свое название потому, что в качестве модели сообщения используют словарь из его подстрок. Впервые были предложены в 1977 году Лемпслем и Зивом. . Словарные схемы пытаются заменять текущую подстроку сообщения короткой ссылкой на ее предыдущее вхождение. Данный подход аналогичон правилам использования местоимений в разговорной речи. Словарная схема в общем виде параметризуется 4-мя эвристиками: инициализации, совпадения, обновления, и удаления элементов словаря. Выбор различных эвристик порождает множество разнообразных словарных схем сжатия. Наибольшее распространение получили словарные схемы со статическим словарем, со скользящим окном и с динамическим словарем. Словарные и статистические схемы сжатия различным образом оценивают избыточность сжимаемого сообщения. Двухступенчатые схемы представляют собой

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

Рисунок 5. Структура лвухуропнепой схемы сжатия

_ . , Словарная Сообщение-Н подсхема

Статистическая|

подсхема § КоДы

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

Основным требованном к схеме сжатая, работающей в режиме встроенного компонента ОС является се "прозрачность" для остальных компонентов вычислительной системы; то есть автоматическая схема сжатия должна: . -

• представлять собой схему сжатия без потерь, иначе она не может быть использована для работы с любыми данными;

• быть адаптивной, так как отсутствуют априорные сведения о сжимаемых данных;

• обладать высоким быстродействием, чтобы не снижать общую производительность системы в целом;

• обладать достаточной производительностью, чтобы компенсировать затраты системных ресурсов на сжатие данных;

• использовать минимально возможный объем оперативной памяти для поддержания модели сообщения. -

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

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

Рисунок 6. Результаты использования "классических" длгоритмоо

600% 400% 200%

...............■-.......

г—П , ; r-t j

.ОУменьшениа объема

ВЗамедление доступа

Huffman Arithm LZW. LZSS • LZ+Arithm

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

Интерфейс обмена ОС с драйвером устройства в принципе позволяет использовать и off-line сжатие, в расчете на получение максимальной производительности." Однако, его практическое использование, ограничивается принципиальными 'проблемами. Далее приводятся дво теоремы, касающиеся Л'Р-полноты задачи off-line- словарного- сжатия, и сравнительной производительности off-line и on-1'шс словарных схем.

Теорема: Имея строку j и некоторое целое число К, проверка истинности следующего неравенства, в общем случае, представляет собой . 'WP-полную'задачу: \OFFLWE(s)[<~K. ■ •

Теорема: Пусть D - словарь, s строка, р - размер указателя. Будем . обозначать OFFUNE(D,s) - сжатую форму-v, полученную off-line алгоритмом, U ONLTNE(D.s) - сжатую форму s, полученную on-line алгоритмом. Тогда:

| OFFUNE(D,s)\ г

i-i->- Где г . некоторая константа.

\ONLlNE(D,s)\ р + г-1

Это позволяет сделать вывод о нецелесообразности применения offline словарной схемы для решения поставленной задачи.

Словарная схема сжатия, заменяет каждое повторное вхождение, . некоторой подстроки в сообщение указателем, представляющим собой пару полей <смещение, длина>. Разумно было попытаться определить размеры полей , позволяющие получить максимальное сжатие. Формальная постановка задачи выглядит следующим образом:

х, + х}<= С

■. -

х2>-1

2*1

max F(x,,x2) ---: ..

где X/ - размер поля смещения, дг3 - размер поля длины совпадения в битах, С - некоторая константа. определяющая размер указателя, F(x,, xj -степень сжатая, которая может быть достигнута при использовании таких параметров указателя. Как нетрудно заметить, данная задача представляет собой задачу поиска условного экстремума выпуклой функции. Графическое изображение области исследования целевой функции показано на рисунке 7.

I рыоора оптимальных

ппраметроч указателя

х2

.. А

xl >- 1

Максимум /С в точке [С/2. С/2].

х2>=1

С

xl

Максимум целевой функции находится в точке [с/2, с/2]. На практике вероятность появления повторяющихся подстрок длиной 2е'2 значительно ниже вероятности появления более коротких подстрок, что может быть отражено в дополнительных ограничениях на область йсследования целевой функции..

Здесь и далее разработанный алгоритм будет называться 1_гм (Лсмпель-Зив-Мастрюкоп). Так как требования к степени сжатия, быстродействию и объему памяти, необходимой для работы алгоритма, являются практически взаимоисключающими, ' отдает предпочтение быстродействию и экономии памяти на модели сообщения.

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

Рисунок 7. Алгоритм работы компрессора IZM ;

Обозначения: А - {at...aj, - входной алфавит, L2M(A) = {А и С}, - крдовый алфавит, С = {Си,Сг,Ср}, - алфавит маркеров, # . операция конкатенации строк

и :-0;

v := ПусшаяСтрока; Пока I <= |s|

г = /7одсчитать11оаморы(з,-...}п); Если г > \Сг\ то

Если и > 0 то

v :=vncu(u)#si.u.:.si.i; ' и 0; Конец Если; v:^vttC/r)#s/; i - i + г; . .

Иначе

<о,1> — ДлинаСоападе'нияО); . .

Если I > )Ср\ то

Если и > Ото

v := vttCu(u)ttSi.u..-.Si.i;

и:=0; '

Конец Если; v := vttCp(<o,l~>): i :=/ + /;

Иначе

и и + 1; i := / + 1; Конец Если; Конец Если; Конец Пока;

Схема работы декомпрессора 12М приведена на рисунке 9, Алгоритм декомпрессии может выполняться со скоростью, близкой к скорости прямого копирования, входного потока в выходной поток. Это является его несомненным достоинством, так как он должен включаться в работу при каждой попытке чтения данных с устройства.

Рисунок 9. Алгоритм работы декомпрессора LZM / 1

s := ПустаяСтрока;

. Пока I < M

code := v/...v|q; Переключатель code

Когда code = \Си\ То s s tt v,-...vi+„; / ;= / + и; Когда code ~ \Cr\ То

s := s # Sym(Cr)* R(Cr); Когда code - \Cp\ То

s s # SO...SO+1; Конец Переключатель; /:= / + |C| Конец Пока;

Адекватной математическим аппаратом для исследования мощности схемы сжатия является аппарат теории информации. В силу того, что степень сжатия адаптивных алгоритмов. зависит от обрабатываемых данных, получение формальных оценок их средней мощности не представляется возможным. Однако можно оценивать минимальную и максимальную мощность схемы сжатия на примере вырожденных случаев - сообщения с энтропией, равной нулю, и сообщения с энтропией равной log,\A\, где А размер входного алфавита. Очевидно, что схема сжатия, являющаяся "хорошей" в смысле теории информации, должна давать наилучшие результаты в первом вырожденном случае, и наихудшие - во втором. Далее были доказаны утверждения, касающиеся мощности схемы LZM.

Пусть А - входной алфавит, С - алфавит маркеров, р - указатель, ЛП -лучшая производительность, ХП - худшая производительность, тогда: Лемма 1: ЯП схемы LZM на некоторой строке î = {s,...sj равна (¡A ¡''V |С| -1) / (\р\ + 1), и достигается она тогда, когда для любого f : I <= i <= . vi, j, = а, где а некоторый символ Л, и « кратно \А\М/\С\ -1. а

Лемма 2: В худшем случае процедура обработки строки s, такой что |î| > \Л\¥/\С\ -1 схемой LZM приведет построению кода LZM(s), такого что

12М($)Г\$\ =7 + \р\/(\А\м/\С[-1), аобработка строш л-, такой что М<=|Л|м/|С| - : 7, приведет к получению такого кода, что =7 +в

Лемма 3: ЛП схемы 1-7М превосходит ЛП статистической схемы нулевого порядка с кодированием по Хаффмену, при \А{=256, |С|=< для любых

Ы >= /. и '■/-:. ■ ' ; . ' ■

Лемма 4: ХП схемы Ц£М уступает ХП статистической схемы нулевого порядка по Хаффмену, при любых параметрах схемы 12М.'и

Лемма 5: ЛП схемы 12М не уступает ЛП схемы со скользящим словарем при любых равных значениях |/?| обеих схем. в

Лемма 6: ЛП схемы 12М уступает ЛП схемы с динамическим словарем при любых равных значениях [р| обеих схем, для любой строки ¿', такой что И >=\А\™/\ С\-1.в

Лемма 7: ХП схемы 12М превосходит ХП словарных схем при любых равных \р\>1. в

Лемма 1 показывает, что схема ЬИМ является "хорошей" схемой в смысле теории информации, так как лучшей производительности достигает на сообщении, энтропия которого равна нулю. Лемма 2 - определяет минимальную мощность 17!М. Леммы 3-7, • содержат результаты сравнительного анализа мощности схемы Они показывают, что схема \2.М уступает словарной схеме с динамическим словарем, но превосходит схему со скользящим словарем и статистическую - с кодированием по Хаффмену.. В то же время, обработка "плохого" сообщения приводит к получению кода большей длины, чем в случае использования статистической схемы по Хаффмену. Но получаемое "удлинение" не столь сслико, как при использовании словарных схем.

Наиболее сложной операцией во время работы компрессора ЦШ является поиск предыдущего вхождения текущей подстроки о сообщение. Очевидно, что- время, необходимое на поиск совпадения а значительной степени определяется организацией структуры словаря и методов доступа к нему. Схема организации словаря приведена на рисунке 10.

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

достоинств и недостатков. Достоинства состоят в том, что во-первых отпадает необходимость в инициализации словаря перед началом работы; во-вторых - что время поиска совпадения представляет собой 0(1)\ в-третьих - что данный подход адаптивен, так как реализуется эвристика, состоящая в том, что текущая строка "больше похожа" на своих недавних предшественников, чем на ."далеких предков". Недостатки состоят в том, что ради достижения высокого быстродействия ЦМ жертвует точностью построения модели, так как все подстроки с одинаковым значением хеш-функции для него неразличимы. Это приводит к снижению средней степени сжатия. •

НА8Н (г^ зЬ1, з1<2)

= ( ( ( ЬЗН1РТ 2 ) ХОК 31(, ) ЬБИТРГ 2 ! ХОЛ зьг

Рисунрк 10. Организация доступа к словарю р схеме 1_2М.

Сообщение

Словарь

1 /

•

1

1 Хеш Код

Т

Хеш Код

Используемая в Ц:М схема кодирования приведена на рисунке 11. Такая структура кодовых слов была получена, эмпирически, в результате экспериментов с различными типами данных и длинами сообщений. Как следствие из леммы 1, она позволяет достигать максимальной степени сжатия, равной 21. .

Рисунок 11. Кодирование в схеме ЦМ.

0 0

2 в

0 0 Все биты 0. шжт^тпттт:

2 6 а 8

0 1 !(нс \ : дс , . .. сс

2 '. 2 3 9

л

дс •

2 2 12

1 1 КНС дс ДС2

2 4 2 " 13 3

При этом используются следующие обозначения:

КНС - количество незакодированных символов

КП - количество повторов символа

Символ - повторяющийся символ сообщения ДС - длина совпадения

СС - смещение совпадающей подстроки

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

Пусть: - скорость обмена системы с устройством {будем считать, что скорость операций чтения и записи одинакова); К„ - скорость обмена ■ ОЗУ/ОЗУ в системе: Ус - пропускная способность компрессора схемы сжатия; Уи - пропускная способность декомпрессора схемы сжатия; - средняя пропускная способность схемы сжатия в обоих направлениях; г - средняя степень сжатия схемы, определяемая как среднее соотношение где ¿с размер сжатого сообщения, - размер исходного сообщения, принимающая значения в интервале ]0, 1[; Тогда

Утверждение 8: Автоматическая схема сжатия не снижает производительность обмена системы с потоковым устройством, если а)Гс>=Г4/(1--Я), (2) С'„>= Га'Я/а-Я) Я

Утверждение 9: Автоматическая схема сжатия не снижает производительность обмена системы с блочным устройством, если

У. >= УМ г + lj/.(Vm(l-2r) - V„k), где А- - коэффициент изменения содержимого блока, равный т/М, где M -размер обменного блока, m - размер измененного фрагмента, принимающий : значение в интервале./",//"»

Критерий оценки сбалансированности схемы сжатия показывает то, какими затратами системных ресурсов и вычислительной мощности достигается сжатие данных. Предлагаемая формула оценки сбалансированности приведена ниже: Q - Сач/ *B„i)i 1 где С„,.г - средняя степень сжатия, определяемая как (V - VJ / V, где У -размер сжимаемого блока, Vc - его размер после сжатия; Tln.g ■- среднее время на сжатие блока размером У\ Brd - относительный размер модели данных определяемый как VJV, где- Vm - размер модели данных для реализации данной схемы;

Размерность предложенного критерия является с', а его семантику можно определить как скорость сжатия на относительную единицу объема модели данных. В зависимости от специфики области применения, в том случае, когда параметры критерия не равноценны, они могут быть взвешены ■оценками их значимости. Диаграмма на рисунке 12 содержит результаты сравнения реализаций различных схем сжатия, показывающие, что по выбранному критерию, в случае равной значимости параметров, разработанная схема является наиболее сбалансированной.

Рисунок 12. Соавнение оассмотоенных схем сжатия по

■ 55 за- Î5 20 ; 15 10 ■ 5. предложенному критерию

; ;

..pl....

-••

hulf arith lzw12 lavis lzss tzari . •LZM

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

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

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

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

Сжимающий драйвер представляет собой самый сложный компонент ' комплекса, так как требования со стороны системы, предъявляемые к нему, наиболее высоки. Внутренняя организация драйвера изображена на рисунке 14. Интерфейс ОС представляет собой стандартный интерфейс обмена данными между драйвером и операционной системой, и позволяет эмулировать устройство большей емкости, чем физический носитель данных. Так как схема сжатия преобразует обменные блоки данных фиксированной длины в блоки переменной длины, драйвер вынужден поддерживать собственную систему размещения сжатой информации. Интерфейс утилит комплекса позволяет им получать прямой доступ к системе размещения данных и к системе доступа к устройству. Это дает возможность утилитам ■ контролировать физическое расположения информации на носителе, так как драйвер, работающий в режиме on-line, не в состоянии эффективно

располагать сжатые данные на носителе без значительного снижения быстродействия. Интерфейс доступа прикладных программ дает им возможность во время выполнения осуществлять операции компрессии / декомпрессии данных в оперативной памяти.

Рисунок 13. Место программного комплекса автоматического сжатия в структуре ОС

[Утилиты комплекса

Служебная информация

С

[ Прикладные программы |

......г-г~

| Несжатые данные |

/ / I I '

( Операционная система |

.//II ,

Несжатые данные ■ |

ПИ

Z7

Драйвер со встроенной схемой сжатия

Стандартный драйвер устройства

TT

X

С:катыо данные

XI

Несжатые данные

X "

( Внешнее устройство ■ [ Внешнее устройство J|

Рисунок 14. Внутренняя структура сжимающего драйвера

Внешние интерфейсы

. Утилиты комплекса . Операционная система Прикладные программы

Интерпретатор запросов ОС

Система размещения сжатых данных

X

Система обмена с устройством

Внутренние буферы данных |

Сжатые данные

TT

Среди аналогов разработанному комплексу можно выделить такие как Stacker компании Stac Electronics и DoubleSpace компании Microsoft. Аналогичных отечественных разработок не существует. В силу того, что

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

Рисунок 15. Сравнительный анализ характеристик комплекса

Продукт Объем ОЗУ(Кб) Сжатие до ре-компрессии Сжатие поело рекомпрессии Быстродействие

Stacker 44 1.81 . 2.10 1.37

DoubleSpace 41 1.74 2.07 1.38

Разработанный комплекс 32-40 1.71 2.03 1.31

Без встроенного сжатия 0 1 1 1 •

Практическое использование разработанного комплекса позволило выявить те области, в которых он наиболее и наименее 'эффективен. Наиболее значительные результаты в достигаются при хранении на сжатом диске таблиц реляционных баз данных, документов, растровых и векторных изображений. При этом среднее сжатие может достигать 3 раз, и не только не происходит снижения производительности системы, а наоборот она • возрастает .на 10-.15%. При хранении на сжатом диске в основном выполнимых модулей среднее сжатие составляет 1.6-1.7 раза, а время запуска программ снижается на 15-20%. В этой ситуации выигрыш от сжатия также превосходит снижение производительности. При работе с такими данными, как цифровой звук, выигрыш от сжатия перестает оправдывать затраты на его реализацию, и составляет около 10%. В среднем удваивая эффективную емкость носителя, разработанный комплекс позволяет программным путем увеличить "аппаратные" возможности вычислительного комплекса.

ВЫВОДЫ И ЗАКЛЮЧЕНИЕ

В диссертации отражены следующие научные и практические

результаты, полученные автором работы:

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

2. Разработана и предложена адаптивная схема сжатия данных без потерь Лемпель-Зив-Мастрюков (LZM), определена ее мощность, и показано, что она является "хорошей", в смысле теории информации, схемой сжатия данных. Проведен сравнительный анализ мощности схемы LZM и , известных схем. Предложена эффективная практическая реализация схемы LZM со временем выполнения одного шага сжатия 0(1).

3. Предложен критерий оценки применимости схемы сжатия для работы в автоматическом , режиме а компоненте ОС и критерий оценки сбалансированности реализации схемы сжатия. Проведено сравнение реализаций известных схем сжатия, показывающее, что предложенная реализация схемы LZM сбалансирована в наибольшей степени.

4. Разработан и реализован на ПЭВМ IBM/PC программный комплекс автоматического сжатия данных на дисковом устройстве, позволяющий в среднем удвоить эффективный объем накопителя на магнитном диске, при снижении средней производительности обмена с устройством на 2030 процентов. .

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Мастрюков Д.Л., Сжатие по Хаффмену // М., Монитор,1993, N7-8.

2. Мастрюков Д.Л., Арифметическое кодирование // М., Монитор, 1994, N1.

3. Мастрюков Д.ЛАлгоритмы группы LZ // М., Монитор, 1994, N 2. .

4. Мастрюков Д.Л., Алгоритм LZW, // М., Монитор, 1994, N 3.

5. Мастрюков Д.Л., Сжатие в драйверах устройств // М., Монитор, 1994, N4.

6. Мастрюков Д.Л., Сжатие цифрового звука Ц М., Монитор, 1994, N 5.

7. Мастрюков Д-J).. Сжатие изображений // М., Монитор, 1994, N 6.

& Mastrukov D.. Building О-О Portable Environment // Prentice Hall, USA, TOOLS'14.Proceedings, 1994.