Содержание к диссертации
Введение
Глава I. Задача устранения информационной избыточности в базе данных АСУП
1.1. Формализация процесса сжатия дискретной информации 8
1.2. Некоторые особенности организации и методов обработки информационной базы АСУП 19
1.3. Анализ избыточности данных в информационном фонде АСУП. 28
1.4. Некоторые методы сжатия дискретной информации 36
1.5. Постановка задач исследования 47
Основные результаты и выводы главы 1 49
Глава 2. Разработка, исследование и способы повышения эффективности некоторых статистических методов сжатия информации
2.1. Способы повышения эффективности реализации итерационных алгоритмов наращивания ..51
2.2. Построение оптимального выходного представления для зонного сжимающего кодирования 63
2.3. Разработка и исследование динамического посимвольного метода сжатия 80
Основные результаты и выводы главы 2 93
Глава 3. Сравнительный анализ и выбор эффективных методов устранения информационной избыточности в базе данных АСУП
3.1. Анализ эффективности применения методов сжатия информации при организации базы данных АСЛ 95
3.2. Выбор методов сжимающего кодирования 105
Основные выводы и результаты главы 3 112
Глава 4. Пакет прикладных программ сжатия информации при организации базы данных АСУ
4.1. Структура пакета 115
4.2. Особенности программной стыковки ППП сжатия с операционной системой АСУП ..119
Основные результаты и выводы главы 4 125
Заключение 126
Список основной использованной литературы 128
Приложение. Документы по внедрению 138
- Некоторые особенности организации и методов обработки информационной базы АСУП
- Способы повышения эффективности реализации итерационных алгоритмов наращивания
- Анализ эффективности применения методов сжатия информации при организации базы данных АСЛ
- Особенности программной стыковки ППП сжатия с операционной системой АСУП
Введение к работе
диссертационная работа посвящена разработке, исследованию и применению методов устранения информационной избыточности в базах данных автоматизированных систем управления предприятиями (АСУП). В ней рассмотрены как теоретические, так и прикладЕше аспекты данного вопроса.
Актуальность проблемы. В настоящее время в народное хозяйство внедрено большое количество АСУП, главной целью которых является автоматизация и совершенствование информационных процессов на производстве. Возрастающие требования к эффективности функционирования АСУП, значительное увеличение объемов хранимой и передаваемой по каналам связи информации ведут к постановке новых задач, требующих своего решения. К их числу можно отнести задачу сжатия информации, успешное решение которой позволяет повышать эффективность реализации информационных процессов.
Теоретические основы проблемы устранения информационной избыточности были заложены в конце 40-х годов в фундаментальных трудах К.-Э.Шеннона по теории информации и кибернетике. С тех пор появилось большое количество работ советских и зарубежных авторов, в которых рассматривается и решается задача сжатия дискретной- информации. В этих работах наибольшее развитие получили статистические и комбинаторные методы, а также исследованы многие вопросы, связанные с устранением избыточности кода. Разработанные алгоритмы сжимающего кодирования реализованы на программном или аппаратном уровне в некоторых практических приложениях. Однако, несмотря на значительные успехи, достигнутые в решении указанной проблемы, разработка, исследование и внедрение новых, а также усовершенствование существующих методов сжатия при организации базы данных АСУП является актуальной задачей. Это обусловлено тем, что имеющиеся теоретические разработки либо носят общий характер, либо не учитывают специфику информации, перерабатываемой в данном конкретном приложении. К тому же они не получили в АСУП должного практического применения.
диссертация направлена на дальнейшее развитие и конкретизацию методов сжатия дискретной информации применительно к базам данных АСУП. Основными целями работы являются:
разработка, исследование и выбор наиболее эффективных методов сжатия, учитывающих специфику хранящейся в базе данных АСУП информации;
создание и внедрение в условиях функционирования реальных АСУП программного аппарата, реализующего разработанные алгоритмы.
Научная новизна. В работе впервые рассмотрен и решен ряд задач, связанных с устранением информационной избыточности в базе данных АСУП. В частности:
исследованы вопросы эффективности применения методов сжатия информации при организации базы данных АСУП;
разработаны способы повышения эффективности итерационных алгоритмов наращивания;
решена задача достижения максимальной степени сжатия при использовании зонного метода;
разработан один алгоритм решения задачи декомпозиции; разработан и исследован эффективный статистический метод сжатия информации, вырабатываемой неэргодическим источником сообщений.
Общая методика исследования. Математическим аппаратом, используемым в данной диссертации, являются теоретиковероятностные и оптимизационные методы. Практическая ценность полученных результатов. Применение результатов работы позволяет добиться значительной экономии памяти ЭЗМ, выделяемой под базу данных, а также сокращения времени поиска элементов базы и их передачи по каналам связи при обслуживании абонентов в АСУЇЇ.
Автор защищает:
результаты качественного и количественного анализа информационной избыточности в базах данных АСЛІ;
способы повышения эффективности блочного и зонного снимающих кодов;
динамический посимвольный метод скатил информации;
методы полного устранения избыточности кода в базах данных АСУП;
методику выбора множества наиболее эффективных алгоритмов сжимающего кодирования структурных элементов баз данных АСУП;
принципы построения и методику применения программного аппарата, осуществляющего автоматическое сжатие информации.
Диссертационная работа состоит из четырех глав, заключения, приложений и списка основной использованной литературы.
В первой глазе вводятся основные понятия и определения. Описывается формальная постановка задачи скатил в терминах теории информации. Рассматриваются особенности организации и методов обработки базы данных АСУП. Исследуется специфика ішформации, содержащейся в этой базе, в том числе присущие ей виды информационной избыточности. Сделан обзор литературы по тем методам сжатия информации, которые могут быть использованы в АСУП.
Во второй главе разработаны способы повышения эффективности двух статистических методов сжатия. Для обоих методов удается увеличить достигаемую степень сжатия. Кроме того для одного из них значительно уменьшается время машинной реализации. Предлагаются алгоритмы решения опттлизавдонных задач, возникающих при формализации содержательных постановок. Разработан и исследован оригинальный статистический метод сжатия.
В третьей главе исследуются вопросы эффективности применения методов устранения информационной избыточности в базе данных АСУЇЇ. Проводится сравнительный анализ этих методов и определяются наиболее эффективные из них.
В заключительной четвертой главе рассматриваются различные аспекты практической реализации. Описаны структура созданного программного аппарата, выполняющего автоматическое сжатие данных, и особенности его стыковки с операционной системой АСУЇІ. Особое внимание уделяется зопросшл стыковки с операционной системой ЕС ЭВМ и специальным математическим обеспечением отечественных систем управления базами данных.
Некоторые особенности организации и методов обработки информационной базы АСУП
Использование современного технического обеспечения позволяет моделировать в АСУП производственно-хозяйственную деятельность предприятия при помощи информационных процессов [49,75J . Состояние и динамика производственных объектов, являющихся источниками сообщений, отражаются соответственно нормативно-справочными и оперативными планово-учетными данными. Эти данные используются при построении адекватной динамической информационной модели предприятия, которая физически размещается и хранится в памяти ЭВМ. В ходе выполнения прикладных программ АСУП осуществляется процесс обработки информационной модели, являющийся машинным моделированием процесса управления предприятием.
Функционирование прикладных программ происходит под управлением операционной системы (ОС) применяемой ЭВМ. В настоящее время автоматизированные системы управления предприятиями создаются преимущественно на базе семейства ЭЦВМ третьего поколения типа ЕС ЭВМ [2,21 ] . При этом машинная ОС дополняется комплексом прикладных программ, реализующих наиболее общие алгоритмы обработки данных. Такой комплекс, являющийся развитием машинной ОС называется системной ОС. Рассмотренные два вида операционных систем в совокупности образуют ОС АСУП, Прикладной програтлмист в процессе создания программ, реализующих алгоритмы решения задач управления, включает в них обращения к элементам ОС АСУП. При этом задаются значения необходимых параметров настройки.
Логическая организация информационной модели, т.е. ее организация в представлении прикладных программ, базируется на иерархической структуре. Элементами различных уровней иерархии являются следующие информационные объекты, каждый из которых определен на символах вторичного алфавита и соответствует одному или некоторой совокупности сообщений.
Минимальная семантическая единица данных, соответствующая отдельной характеристике производственного объекта, называется элементарным реквизитом. Группа элементарных реквизитов, имеющая самостоятельное смысловое значение, называется составным реквизитом. Между элементами множеств возможных реквизитов и сообщений устанавливается взаимно однозначное соответствие. Каждое сообщение характеризуется наименованием и значением, которые, также, определяют соответствующий реквизит.
Поименованная последовательность значений элементарных или составных реквизитов называется записью. Наименования и порядок следования реквизитов в записи определяют ее тип. Все записи одного типа могут иметь одинаковые или различные длины. В соответствии с этим различают записи фиксированной и нефиксированной длины. Таким образом, однотипные записи имеют одинаковую структуру, но могут иметь различные длины. Большинство информационных объектов, подвергающихся логической обработке в АСУП, и соответствующих им сообщений имеют фиксированную длину. Это упрощает обрабатывающие алгоритмы, однако часто связано с введением дополнительной информационной избыточности.
Поименованная совокупность всех записей заданных типов,объединенных общим способом их использования, называется массивом. Массив, состоящий только из однотипных записей, называется однородным. В противном случае массив называется неоднородным. Записи внутри массива обычно упорядочиваются по одному или нескольким признакам. В качестве признаков упорядочения используются значения ключей записи, представляющих собой отдельные реквизиты или упорядоченные группы реквизитов. Ключ называется первичным, если его значение однозначно идентифицирует запись. В противном случае ключ называется вторичным. Каждое упорядочение определяет логическую последовательность записей.
Поименованная совокупность массивов, имеющих общую область приложения, называется информационным фондом. Обработка информационного фонда производится в соответствии со служебными описаниями, которые содержат информацию о наименованиях, типах,структурах, формах представления, способах размещения в памяти ЭВМ и взаимосвязях структурных элементов данных. Различают описания реквизита, записи, мае сива и информационного фонда.
Результат объединения информационного фонда с соответствующими ему служебными описаниями называется базой данных. Информационной моделью предприятия является база данных АСУП.
Логическая структура произвольной базы данных определяется характером задач, решаемых в конкретной информационной системе. Физическая организация базы, т.е. форма реального существования данных, отражая логическую организацию, зависит от характеристик используемого технического обеспечения и особенностей ОС. Основным критерием выбора формы физического хранения данных является эффективность использования памяти SBM. Поэтому способы логической и физической организаций базы могут существенно различаться между собой. _ База данных АСУП физически хранится на магнитных внешних запоминающих устройствах (В 3 У) [4 ] . В настоящее время в качестве внешних магнитных носителей информации наиболее широко применяются сменные магнитные диски (М Д) с перемещающимися головками. Накопители на МД являются запоминающими устройствами с прямым доступом. Благодаря этому достоинству МД постепенно вытеснили магнитные ленты (.МД). Накопители на МЛ, являясь устройствами с последовательным доступом, применяются в основном для вспомогательных целей.
Для описания формы физического хранения данных во внешней памяти ЭВМ введем несколько определений. Единица обмена данными между ЭВМ и ВЗУ, которая может быть считана в рабочую память ЭВМ или записана на ВЗУ одной машинной командой ввода-вывода,называется блоком или физической записью. В блоке обычно содержатся несколько логических записей.
Совокупность блоков, расположенных на внешнем носителе последовательно в порядке возрастания физических адресов их начала, называется экстентом. Местоположение блоков и экстентов во внешней памяти однозначно определяется их физическим адресом и длиной.
Поименованная совокупность блоков и некоторых вспомагатель-ных данных, которые необходимы при осуществлении поиска записей во внешней памяти, называется файлом. Файл может занимать несколько экстентов.
Способы повышения эффективности реализации итерационных алгоритмов наращивания
В большинстве статистических методов сжатия, таких, например, как методы наращивания и зонного кодирования, окончательное выходное представление выбирается до начала кодирования входного ряда. Следовательно при использовании таких методов предполагается, что входной ряд вырабатывается эргодическим источником информации. Воспользуемся построенной в разделе І.І математической моделью марковского эргодического источника, представляющей собой конечную цепь Маркова, для повышения эффективности процесса построения выходного представления методом наращивания [14] . Решение задачи укрупнения состояний цепи [34] позволяет учитывать зависимости высоких порядков между символами.
Для применения двух схем наращивания, описанных в разделе 1.3 , к математической модели марковского эргодического источника необходимо определить операции "кодирование" и "выбор множества выгодных входных групп" на матрице переходных вероятностей Р . Введем несколько обозначений. Индекс Г ( Г = /,/?) у всех переменных будет указывать на номер итерации. Символы обо-значим через ( і = 1, nt ), а выходные коды через т{рі=0,л%.\ ГПг $-/) Через /? , очевидно, обозначено общее количество итераций, осуществляемое в процессе наращивания, а через /7 и ( 77/-+1) - мощности входного и выходного алфавитов соответственно. Общее количество входных групп на каждой итерации ограничено сверху величиной .
На Г -ой итерации каждый выходной код Km замещает соответствующую входную группу, состоящую из Z./77 символов и являющуюся \_Sce}ci:7Trn Подпоследовательность последних ( Q +1) символов группы обозначим через l JceJe = Lm-g, Относительную частоту появления входной группы {Sceff "fyL/n в0 входном ряду обозначим через 00 (Km ), а в закодированном входном ряду на /"" -ой итерации - через (Хг (Лт ). Значения величин (2{ Ос) и матрицу Р Р = ЦОс/1 пгхnf считаем известными до начала первой итерации. Тогда значения СХ, (Лщ ) определяются по формуле (Lm-f) Определим операцию "кодирование" на матрице Р. Предположим, что на Г -ой итерации определено множество входных групп и те перь, используя его, необходимо закодировать входной ряд при помощи упрощенного алгоритма. Задача состоит в определении отно сительных частот появления входных групп в закодированном вход ном ряду, значения которых O l&m ) равны разности между отно сительной частотой появления группы t Steje = f, Lm во вход ном ряду и суммой относительных частот появления в закодирован ном входном ряду двух следующих ситуаций. I. Данная входная группа является составной частью некоторой более длинной входной группы при условии, что последняя появилась в закодированном входном ряду; в этой ситуации выделим два случая: а) данная входная группа является начальной последователь ностью более длинной группы; б) в противном случае. П. Последовательность, состоящая из нескольких, например, ( 0-+I), начальных символов данной входной группы, (но не вся группа), является конечной подпоследовательностью некоторой входной группы, (но не совпадает с ней) при условии, что последняя появилась в закодированном входном ряду. Таким образом, можно записать: (/77 = О, ґґіг ), которую необходимо решить для определения результатов кодирования. Заметим, что входные группы, состоящие из одного символа не могут удовлетворять условиям ситуаций (I) и (П) ни для какой входной группы, поэтому, считая, что множество одиночных символов соответствует первым /7г кодам, будем сначала решать систему из (/77г -Лг+I) последних уравнений (2.2) с ( nrfr-Pr+I) неизвестными С/ (Km ) (/77= ПізШг), а затем найдем относительные частоты появления символов в закодированном входном ряду по формуле Операцию "выбор множества выгодных входных групп" на матрице Р определим сначала для использования в первом алгоритме наращивания. Предположим, что после кодирования на ( г -I) итерации нам известны относительные частоты появления входных групп в закодированном входном ряду. Задача заключается в определении относительных частот появления в этом ряду каждой нарощенной группы. Затем выбирается множество наиболее выгодных нарощенных и входных групп, используя в качестве критерия выгоды частоту появления группы. Относительная частота появления нарощенной группыд,m tt /\ 7?g /после кодирования равна ее относительной частоте появления во входном ряду при условии появления кода
Анализ эффективности применения методов сжатия информации при организации базы данных АСЛ
В предыдущем разделе показано, что эффективность применения методов сжатия информации при организации базы данных АСУП определяется выигрышем в затратах машинного времени. Положительная составляющая этого выигрыша независимо от используемых способов обработки и хранения данных возрастает по линейному закону при увеличении коэффициента сжатия П , а отрицательную составляю-щую определяют дополнительные затраты машинного времени /ск , необходимые для программной реализации алгоритмов сжимающего кодирования и декодирования. Следовательно существуют два основных независимых критерия эффективности методов сжатия информации: максимум выигрыша в затратах внешней памяти {Ліох n ) и минимум дополнительных затрат машинного времени {/7?сг? /ак . В данном разделе на основе использования этих критериев проводит.-ся сравнительный анализ методов устранения информационной избыточности в базе данных АСУП. В результате анализа определяется множество наиболее эффективных методов.
Как уже отмечалось, алгоритмы сжимающего кодирования имеют ограниченные области применения. В свою очередь для устранения каждого вида информационной избыточности может использоваться ограниченная совокупность алгоритмов. Поэтому будем проводить сравнительный анализ методов сжатия отдельно для каждой такой их совокупности, которая соответствует одному из рассмотренных в разделе 3.1 видов избыточности. Если при этом один из методов окажется оптимальным одновременно по двум основным критериям эффективности или единственно возможным, то его и только его необходимо принять в качестве наиболее эффективного для рассматриваемой совокупности. В противном случае к множеству наиболее эффективных могут быть отнесены несколько методов, а выбор оптимального из них зависит от конкретных особенностей избыточности, обработки и хранения данных.
В базе данных АСУП могут существовать два вида синтактической информационной избыточности, определяемые глобальными свойствами источников сообщении. Первым из них является дублирование структурных элементов базы. При использовании концепции БД одноименные реквизиты физически содержатся только в однотипных записях. Это позволяет почти полностью устранить дублирование. Однако в различных однотипных записях могут повторяться значения реквизитов, не являющихся первичными ключам. Такая ситуация характерна для алфавитно-цифровых и цифровых реквизитов. Если значение некоторого реквизита повторяется в нескольких последовательно обрабатываемых записях базы, причем иной последовательности их обработки не существует, то для устранения дублирования это значение можно физически хранить только в первой записи. В остальных записях достаточно установить значение однобитового переключателя, указывающее на физическое отсутствие реквизита. Описанный метод называется глобальной сверткой [52] ив ряде случаев может быть эффективно использован при сжатии данных содержащихся в последовательном или индекснопоследовательном файле.
Наличие второго из упомянутых выше видов информационной избыточности обусловливается тем, что мощность множества возможных значений для большинства наименований алфавитно-цифровых и цифровых реквизитов невелика. Универсальным методом устранения такой избыточности является построение таблицы соответствия в виде словаря. При этом основу кодирования и декодирования составляет процедура поиска в словаре, выполнение которой может быть связано с большими затратами времени. Поэтому словарный подход целесообразно применять для сжатия только алфавитно-цифровой информации после проведения соответствующего исследования вопросов эффективности.
Для сжатия словарей или в том случае, когда реализация словарного подхода неэффективна, могут быть использованы статистические методы сжимающего кодирования, учитывающие локальные свойства источников алфавитно-цифровых сообщений. Наиболее эффективным среди таких методов с точки зрения возможной достигаемой степени сжатия является блочное кодирование. Как было показано выше, построение выходного представления для блочного кодирования целесообразно осуществлять при помощи одной из итерационных схем наращивания, используя математическую модель марковского эргоди-ческого источника сообщений. Максимальное значение мощности выходного алфавита необходимо выбрать равным 256, а длины входных групп можно ограничить сверху 6-7 символами. При этом ожидаемые значения коэффициента сжатия будут лежать в интервале 0,4 7 0,5. Для ускорения машинной реализации алгоритмов сжатия необходимо расположить входные группы в выходном представлении в лексикографической последовательности.
На каждом шаге блочного кодирования выходной код замещает целую группу символов. Несмотря на это, з дельные затраты машинного времени на один байт входного ряда tc c при программной реализации упрощенного алгоритма блочного сжатия могут быть зна-чительно больше, чем удельные затраты Сеж и ь-елг соответственно для таких посимвольных методов, как зонный и динамический . коды. По аналогии с тем, как это делалось в разделе 2.1, можно сравнить блочный, зонный и динамический посимвольный методы сжатия по второму критерию эффективности, разложив соответствующие алгоритмы на элементарные машинные команды. В результате нетрудно получить следующие сравнительные оценки.
Особенности программной стыковки ППП сжатия с операционной системой АСУП
В предыдущих главах рассмотрены теоретические аспекты задачи сжатия информации при организации базы данных АСУП. В результате проведенных исследований определено множество наиболее эффективных методов сжимающего кодирования. Заключительная глава настоящей диссертационной работы посвящена изучению прикладішх вопросов, связанных с практическим применением этих методов. В данном разделе описана структура созданного программного аппарата, реализующего алгоритмы сжимающего кодирования и соответствующего декодирования, а в следующем разделе - особенности стыковки этого аппарата с ОС АСУП.
Сжатие информации в АСУП можно рассматривать как одну из процедур системного обслуживания [62 ] . Программная реализация таких процедур в настоящее время выносится на стандартный зфовень и следовательно не должна зависеть от функциональных задач.Поэтому созданный программный аппарат, предназначенный для осуществления автоматического сжатия данных в АСУП, реализован в виде специализированного пакета прикладных программ (ПШ), написанных на языке Ассемблера.
ППП сжатия информации построен на основе использования принципа модульности. Каждый из рассмотренных в разделе 3.2 алгоритмов сжимающего кодирования или соответствующего декодирования реализуется в отдельном программном модуле. Кодирующие и декодирующие модули взаимно независимы и обмен информацией между ними отсутствует. Для их объединения в единый ППП создан корневой модуль SGCOd , выполняющий диспетчерские функции.
Пакет имеет единственную точку входа для пользователей. Она совпадает с началом модуля SGCOd . Предполагается, что пользователи обращаются к ППП сжатия в тех случаях, когда необходимо осуществить кодирование или декодирование одной записи базы. При этом запись рассматривается в пакете как последовательность входных рядов, для сжатия которых используются различные методы. Такие входные ряды могут состоять из нескольких реквизитов. В ряде случаев, например при корректировке отдельных реквизитов, нет необходимости кодировать или декодировать всю запись. Поэтому в зависимости от особенностей текущей операции обмена данными между ЭВМ и ВЗУ для каждого типа записи в ПШ может обрабатываться одно из нескольких возможных сочетаний входных рядов. Для всех таких сочетаний должны быть определены идентификаторы. В простейшем случае обрабатывается вся запись.
Применению пакета в условиях решения конкретных функциональных задач АСУП должно предшествовать формирование значений двух наборов внутренних параметров. Первый набор состоит из различных используемых выходных представлений, а второй - из макетов обработки записей базы. Макеты взаимно однозначно соответствуют всевозможным сочетаниям обрабатываемых в ШШ входных рядов для всех типов записей базы и представляют собой последовательности величин, определяющих характер обработки. Такими величинами, в частности, являются: длины записи и всех ее входных рядов, в том числе необрабатываемых, а таюке символические адреса точек входа в кодирующие и декодирующие модули, при помощи которых должны обрабатываться эти входные ряды, коэффициенты повторного использования модулей и адреса соответствующих выходных представлений. Значение коэффициента повторного использования превышает І в тех случаях, когда несколько последовательных входных рядов должны быть обработаны при помощи одного модуля. Как при кодировании, так и при декодировании записи используется один и тот же макет. Каждый из описанных наборов параметров может быть оформлен в виде одного или нескольких модулей.
Для выполнения оперативной настройки пакета на определенный режим функционирования при каждом обращении пользователя должны быть заданы значения следующих четырех входных параметров: адрес поля в рабочей памяти ЭВМ, в котором размещена подлежащая обработке запись, а также идентификаторы типа этой записи, вида ее обработки (кодирование или декодирование) и сочетания входных рядов. После того, как корневой модуль получает управление по значениям первого и третьего входных идентификаторов отыскивается макет обработки, соответствующий переданной записи. Затем в зависимости от значения идентификатора вида обработки SGCOd последовательно передает управление кодирующим или декодирующим модулям, в которых обрабатываются входные или выходные ряды. В SGCOL задаются значения следующих входных параметров для каждого обрабатывающего модуля: адрес и длина кодируемого входного или декодируемого выходного рядов, а также символический адрес используемого выходного представления. Выходными параметрами при возврате управления в корневой модуль являются обработанный ряд и его длина.
Некоторые записи или их части в течение определенных периодов времени многократно считываются из базы данных и затем содержательно обрабатываются ни разу при этом не обновляясь.
