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

АКАДЕМИЯ НАУК СССР СИБИРСКОЕ' ОТДЕЛЕНИЕ

ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

На правах рукописи МЕРКУЛОВ АЛЕКСАНДР НИКОЛАЕВИЧ

УДК 681.3.06

ИССЛЕДОВАНИЕ И РАЗРАБОТКА АЛГОРИТМИЧЕСКИХ МЕТОДОВ СЖАТИЯ ДАННЫХ

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

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

Новосибирск - 1980

Работа выполнена в Вычислительном центре Сибирского отделения АН СССР.

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

- член-корреспондент АПН, доктор технических наук, профессор И. М. Бобко

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

доктор технических наук, профессор Е Б. Мироносецкий

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

кандидат физико-математических наук, .. доцент И. В. Поттосин

научно-производственное объединение "Система"

^^ащита диссертации состоится " СЬь^шА 1990 г. в часов на заседании специализированного совета К002.10.02 по присуждению ученой степени кандидата наук в Вычислительном центре СО АН СССР по адресу: Новосибирск,90, проспект академика Лаврентьева, б.

С диссертацией,можно ознакомиться в •читальном зале отделения ПШТБ СО АН СССР (пр. Ак. Лаврентьева,6)

Автореферат разослан " " _ iggo г.

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

—Гв. Замулин

■• Актуальность темы. В диссертационной работе рассматрива-ются:Вопросы повышения эффективности организации хранения $щц}А на внешних запоминающих устройствах( ВЗУ) путем исполь-"зования встроенных алгоритмических методов сдагия данных.

Проблема уменьшения объема данных без потери их семантического наполнения ставится давно, но имеет разную интерпретацию в зависимости от области приложения. В работах Да. Мартина, Т.Тиори, ДлсФрай, И.М.Еобко, А. Сименски и других авторов рассмотрены различные алгоритмические методы сжатия данных и некоторые вопросы их применения.

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

С появлением новых классов ЭШ (персональных и супермини-ЭВМ) вполне обоснована мысль, что актуальность .этой проблемы, если не сошла на нет, то значительно потеряла смысл в связи с увеличением мощностей ВЗУ. Однако, значение этой проблемы не ослабевает при создании информационных систем производственного назначения.

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

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

В-третьих, диспропорция между быстродействием процессора

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

Кроме того, для сетевых архитектур компактность данных прямо и сильно влияет на эффективность сети, а для промышленной информатики эту эффективность следует поднять на несколько порядков.

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

Цель работы. Целью диссертационной работы является:

- анализ эффективности алгоритмических методов сжатия данн:

- реализация программных компонент средств сжатия данных на базе ЭВМ типа СМ-4.

Основные задачи, решаемые в работе:

- анализ подходов к минимизации объемов баз данных(БД);

- уточнение понятия алгоритмических методов сжатия данных, исходя из общего определения;

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

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

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

- апробация результатов исследования при разработке подсистемы сжатия данных на базе ЭВМ типа СМ-4.

Научная новизна, в работе содержатся следующие результаты, представляющие научный интерес:

- обобщены и проанализированы особенности подходов, су-

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

- уточнено понятие алгоритмических методов сжатия данных: выявлены их специфические особенности, их роль, место среди других методов и в системном программном обеспечении информационных систем;

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

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

- разработана методика исследования методов сютия;

- произведена параметризация и аналитическая оценка алгоритмических методов сжатия данных;

- предложена и реализована архитектура встроенной системы сжатия данных;

- построен программный аппарат для моделирования и оценки методов сжатия данных по критерию времени и произведены модельные испытания подсистемы сжатия данных по этому критерию;

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

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

Практическая реализация в составе Базовых Средств для

в

построения Пакетов Прикладных программ для сетей мини- и микро-ЭВМ типа СМ-4 (БСПП), подтвердила'правильность предложенной общей архитектуры, состава и функций подсистемы сжатия данных.

Результаты внедрения. Предложенная архитектура подсистемы сжатия данных была реализована в составе БСПП.

Работы проводились в ВЦ СО АН СССР и в ИВЭП СО АН СССР по планам АН СССР на 1986-1990 гг. (тема "Разработка принципов построения ПО АСУП на базе локальных сетей мини- и микро-ЭВМ, их реализация и внедрение на базе действующих систем". Пост. ГКНТ и АН СССР от 30.10.85 555 по проблеме 0.80.02. задание 3.35.13.02), а также по хоздоговорам и договорам о научно-техническом сотрудничестве ВЦ СО АН с НЗХК (г. Новосибирска), ПО "ОЭМЗ"(г. Омск), ВНШГГарматура (г. Алма-Ата), НПО "Электроника" (г. Воронеж), НПО "Полет" (г. Челябинск).

Публикации. По результатам диссертации опубликовано 11 работ (И8 них 5 в соавторстве).

Структура и содержание работы. Диссертация состоит из 4 глав, заключения и четырех приложений.

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

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

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

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

так как машинные процедуры преобразования данных требуют определенных затрат процессорного времени.

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

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

Таким образом, в результате анализа возможных критериев, показано, что обгемный критерий может быть принят за основ- ■ нйй.

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

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

этих служебных данных.

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

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

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

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

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

работы.

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

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

В одном из подходов предлагается различать 2 вида избыточности - избыточность содержания и избыточность формы. Избыточность содержания связана с тем, что в конкретном приложении не все элементы данных имеют значение. Избыточность формы возникает из-за неоптимального способа записи. В соответствии с этими видами избыточности методы сжатия делятся на семантические и синтаксические.

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

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

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

Автором предлагается собственная классификация. По ней все методы разбиваются на 3 класса в соответствии с теми объектами данных, для которых они применяются (запись файла, реквизит записи, символ реквизита).

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

Методы сжатия реквизитов рассматривают реквизит как целое, не меняя представления составляющих его символов и сос-

тава реквизитов в записи.

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

Такой подход ПОЗВОЛИЛ:

- однозначно' разбить методы по классам;

- обеспечить однородность параметризации критериев для методов, относящихся к одному классу,

- сузить задачу сравнения эффективности методов для каждого класса до самостоятельной задачи поиска наиболее эффективного представителя класса, что существенно сократило время исследования без потери адекватности результата,

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

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

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

1. Коэффициент сжатия файла от применения метода какого-либо класса;

2. Коэффициент сжатия БД от применения метода какого-либо класса.

Кроме того, представляют интерес интегральные коэффициенты сжатия, показывающие эффект применения нескольких методов сжатия одновременно для тех хе интегрированных обьектов данных (файла и базы данных):

1. Интегральный коэффициент сжатия файла от применения комплекса методов;

2. Интегральный коэффициент сжатия БД от применения комплекса методов.

В работе определены основные этапы исследования:

- на основе анализа литературы выявляется набор алгоритмических методов сжатия данных;

- для кадцого метода рассматривается алгоритм его работы и при необходимости производится его улучшение или модификация с целью повышения возможного эначения основного критерия;

- определяется аналитическая зависимость для коэффициента сжатия. Это может быть как детерминированная, так и стохастическая зависимость;

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

- в каждом классе методов производится ранжирование методов по значению основного критерия с цэлъю выделения наилучшего метода, либо отсечения худших;

■ - на основе информации о реальной БД вычисляются значения четырех модификаций основного критерия, по которым выделяются лучшие методы в каждом классе. Только по этим четырем показателям мозшо адекватно произвести реальную оценку эффективности методов;

- при одинаковой практической эффективности различных методов производится сравнение методов по критериям второго порядка ( стоимости работы, сложности алгоритма, массовости применения).

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

- анализатора БД; . - программ первоначального сжатия и восстановления данных; . - процедур реализации алгоритмов сжатия, включенных в средства манипулирования данными.

Третья глава отражает ход проведения исследований в соот-■ ветствии с наложенной методикой. В процессе анализа литературы были выбраны 15 базисных методов сжатия данных. Для ря-, да методов предложена модификация. Каздый параграф главы содержит 'анализ одного класса методов вместе с предварительным ранжированием этих методов по основному критерию. . Были исследованы следующие методы сжатия.

Методы, ориентированные на запись:

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

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

3. Метод ключевых форматов. Этот метод основывается на переходе от позиционного к ключевому формату представления реквизитов в записях.. Все реквизиты последовательно нумеруются ив запись включаются только реквизиты с "непустыми" значениями вместе со своими номерами.

Методы/ ориентированные на реквизит:

1. Метод хранения отклонений. Если какой-либо реквизит в записях файла упорядочен по возрастанию или убыванию ёначе-

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

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

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

Методы изменения представления символов:

1. Методы перекодирования "символ - символ". Практически все современные ЭВМ имеют 8-ми битовое представление символов, позволяющее, следовательно, закодировать 256 различных символов. Из них используется только половина возможных битовых комбинаций, поэтому для представления 1 символа достаточно 7 бит. Если же отказаться от заглавных либо строчных букв или спецсимволов, то достаточно даже 6 бит на 1 символ. Существуют коды (телеграфный с преключающими регистрами) с длиной 5 бит на 1 символ.

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

3: В последнее время появились другие коды переменной длины ( интервальный код, on-line коды, обощенный код Шенно-

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

4. Метод перекодирования "цепочка символов - символ". Трудности оперирования с кодами переменной длины, значительное услолшение программирования, привели к созданию эффекти: ных методов перекодирования с кодами длиной в 1 байт.

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

- при возрастании размеров перекодировочных таблиц относительная доля эффекта от перекодирования цепочек большой длины довольно резко падает. Поэтому количество цепочек, ка правило, значительно меньше 128;

- наиболее целесообразно выделять цепочки длиной от 2 до 4 символов.

Для каждого метода получена аналитическая или эмпирическая оценка эффктивности по основному критерию.

Для полученных оценок аналитически или моделированием не ЭВМ были определены области изменения параметров, где наибе лее эффективно применение каждого метода. Оказалось, что д: интересных на практике диапазонов изменения параметров опт» * мальньй (с точки зрения критерия сжатия) метод для каждого класса выделяется однозначно, а именно:

- для сжатия записей - метод маскирования реквизитов;

- для сжатия реквизитов - метод усечения пробелов и нуле

- для символов - метод перекодирования цепочки символов символ.

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

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

//

тия данных сделаны исходя из конкретной операционной среды

I

|

ЭВМ класса СМ-4, операционная система ОС РВ версии 3.О и ыше) и прикладной области (информационно системы производ-твенного назначения). Однако методика носит достаточно об-ий характер и поэтому может быть применена для определения остава методов сжатия и их эффективности в комплексах сжа-ия, имеющих другие области применения и другую операционную реду.

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

Результаты исследований бьши положены в основу реализации Ьдсистемы Сжатия Данных (ПОД), как компоненты Средств Дос-упа к Данным С СДД), которые функционально играют роль СУБД

I вот

СДД и встроенная в, нее ПОД разрабатывалась по заданию 1.35.13.02 Программы 0.80.02 ГКНТ СССР силами лаборатории втодов адаптации АСУ Вычислительного центра СО АН СССР и, ! частности, автором работы, и в настоящее время находится. I эксплуатации на нескольких предприятих страны.

Основное требование БСПП - обеспечение максимальной эф-вктивности и независимости создаваемых ППП от особенностей :онкретного применения.

СДД - это средства описания, организации и ведения БД в ;иде системы алгоритмически связанных файлов. В СДД выделяйся следующие компоненты:

- сервисные программы для работы с метаданными системы, (ля загрузки БД и получения справок по содержимому БД;

-подпрограммы собственно выполняющие все операции по ра-юте с данными;

- инструмент программиста - макрокоманды, которые осущес-■вляют обращение к подпрограммам.

Работа СДД основана на использовании внешних для программ »писаний данных, в силу чего она обеспечивает программирована процессов обработки данных только с использованием логи-[еских имен и, соответственно, обеспечивает независимость [рограмм от значности реквизитов и форматов их хранения, от ¡труктуры записи файла, от типа организации и внешних харак-

.териотик файла. СДД обеспечивает высокую скорость обработки данных.

В СДД реализованы оригинальные механизмы организации распределенных БД: файлы, имеющие разные физические имена в БД, могут иметь одинаковые логические имена. Поэтому введено понятие реализации файла. Реализация файла идентифицируется дополнительными параметрами, называемы;.'.!; дескрипторами. Совокупность файлов, имеющих одинаковые наборы дескрипторов с одинаковыми значениями, образуют подбазу. Для обращения к файлам подбазы достаточно указать набор значений дескрипторов.

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

Основная часть подпрограмм СДД оформлена в виде перемещаемых, позиционно независимых модулей, объединенных в ядро, резидентное в оперативной памяти. Подпрограммы, размещенные в ядре, используются всеми выполняемыми программами без ■дублирования. Незначительная часть подпрограмм СДД (объемом, в среднем, 2-3 килобайта ) прикомпановываегся к каддой программе.

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

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

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

объему на три группы: до 10 Кбайт, от 10 до 100 Кбайт и свыше 100 Кбайт. При этом файлы первой группы- в основном вспомогательные и рабочие файлы - составляют около 70-75Z от количества всех файлов и только около 5% от объема БД. Файлы второй группы составляют около 20-25% от количества всех файлов и такую же долю объема БД. Файлы третьей группы составляют около 75% от объема БД и только несколько процентов - по количеству. Таким образом, для того чтобы иметь представительную статистику о БД, достаточно проанализировать 5-15% всех файлов БД, наиболее значимых по объему.

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

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

Для баз данных предприятий, на которых функционируют сис-?емы обработки данных, построенные на разработанных средст-!ах, определены значения интегральных критериев. Для всех Файлов, имеющих объем от 50 Кбайт и выше, при использовании юмплекса методов сжатия достигается сжатие в 1,5-4 раза. )бъем баз данных сокращается на 30-35%.

С помощью модельных испытаний ПОД было проведено исследо-¡ание влияния сжатия на скрость обработки данных с целью оп~ ©деления пороговых значений параметров, где применение сжа-ия может привести к снижению этой скорости. Выяснено, что:

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

увеличена в 2 и более pas в зависимости от длины ваписи, количества реквизитов и их длины в записи, вероятности появления "пустых" значений. Однако при некоторых значениях этих параметров производительность может существенно уменьшаться;

- затраты времени на сжатие/восстановление данных значительны при малых длинах реквизитов (от 1 до 6 байтов), которые наиболее часто встречайте2 в реальных БД, и при относительно невысокой доле имеющих значение реквизитов в записи.

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

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

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

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

4. Предложена методика исследования методов сжатия данны и произведен аналитический и статистический анализ методов различных классов. В соответствии с этой методикой и введенной системой критериев определены наиболее эффективные методы сжатия.

5. Разработаны и предложены модификации алгоритмов метод ежггия, оринтированые на реквизит и символ.

6. Разработана Система Доступа к Данным, выполняющая фук кции СУБД, и Подсистема Сжатия Данных, входящая в СДД и поз воляющая на 30-75% уменьшить объем файлов в системах промыт

ленной информатики.

7. Произведен статистический анализ нескольких баз данных • большого объема, который позволил выявить закономерности для значений параметров, существенных для построения систем сжатия данных, ее эффективности по объемным и временным крите- ' жям.

8. Построен программный аппарат для моделирования и оцен- ■ си методов сжатия данных по критерию времени и произведены юдельные испытания подсистемы сжатия данных по этому крите-

)ИЮ.

Апробация работы. Результаты диссертации докладывались на:

- Есесоюзной конференции "Интегрированные АСУ предприяти-[ми", Новосибирск, 1985 г.;

- Болгаро-советском научно-техническом семинаре "Проблемы СУ на машиностроительных предприятиях ".София, 1905 г. ;

- Научно-практическом совещании "Опыт и перспективы при-внения микро- и мини-ЭВМ в управлении, проектировании и ор-анизации АРМ специалистов", Барнаул, 1986 г. ;

- Всесоюзном совещании и Второй всесоюзной школе-семинаре о интегрированным системам управления, Суздаль, 1986 г.;

- Всесоюзном семинаре "Состояние и перспективы развития УВД ЕС, СМ и ПЭВМ", Омск, 1937 г. ;

- Совещании "Комплексный подход к созданию многоуровневой ОУ в Алтайском крае", Барнаул, 1987 г.;

- научных семинарах отдела АСУ и лаборатории методов цаптации АСУ Вычислительного центра СО АН СССР, лаборатории ^орматики и ВТ Института водных и экологических проблем СО 3 СССР."

По теме диссертации опубликованы следующие работы:

1. Маруеин В. В., Меркулов А. Н., Меркулова Г. Н. Исследова-1е эффективности некоторых методов адресации при прямом ме->де доступа// Системы и методы анализа данных.- Новоси-фСК, 1934. - С. 148-160.

Бобко И. М. , Меркулов А. Н. Об оценке эффективности применил методов сжатия данных// Иерархические системы управляя и их адаптация. - Новосибирск, 1984. - С. 46-54.

3. Меркулов А. Н. Исследование одного клаооа методов организации связей в базах данных// Иерархические системы управления и ик адаптация. - Новосибирск, 1984. - С. 55-64.

4. Меркулов А. Е Использование сжатия для больших баз данных в АСУП// Интегрированные АСУ предприятиями. - Новосибирск, 1985. - С. 119-121.

5. Меркулов А. Н. Принципы построения систем сжатия данных// Вопросы промышленной информатики.- Новосибирск, 1986. -С. 153-156.

6. Бобко И. Ы. , Марусин В. В., Меркулов А. Н. Методы и организация сжатия данных в АСУП. - Новосибирск, 1986. - 33 с.-

(Препринт/ АН СССР. Сиб. отд-ние, ВЦ; 684).

7. Меркулов А. а Сравнительные характеристики некоторых систем обработки данных для СМ-4// Тез. сов. "Опыт и перспективы применения микро- и мини-ЭВМ в управлении, проекти-рованиии и организации АРМ специалистов". - Барнаул,1986. -С. 11-13.

8. Меркулов А. Н. Об эффективности применения сжатия в базах данных АСУП// Тез. сов. "Опыт и перспективы применения микро- и мини-ЭВМ в управлении, проектированиии и организацго АРМ специалистов". - Барнаул, 1986. - С. 20-22.

9. Системные средства ППП "Сигма Ц-СМ"/ Бобко И. М. , Мару-син В. В., Широкова С. Л. и др. / Алгоритмы и программы. Информационный бюллетень.- М. ,1986.- N4(73).- 43 с.

10. Меркулов А. Н. Исследование зависимости времени доступа от использования сжатия данных// Совершенствование систем управления предприятиями, - Новосибирск, 1987.- С. 114-120.

11. Карпан В. В., Марусин В. В., Меркулов А. Н. Сравнительный анализ систем обработки данных в АСУ на мини-ЭВМ -Новосибирск, 1987. -20 е. - (Препринт/ АН СССР. Сиб. отд-ние, ВЦ;

724).