автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.06, диссертация на тему:Методы сжатия информации при организации базы данных АСУП

Введение.

Глава I. Задача устранения информационной избыточности в базе данных АСУП.

1.1. Формализация процесса сжатия дискретной информации.

1.2. Некоторые особенности организации и методов обработки информационной базы

АСУП.

1.3. Анализ избыточности данных в информационном фонде АСУП.

1.4. Некоторые методы сжатия дискретной информации.

1.5. Постановка задач исследования.

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

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

Теоретические основы проблемы устранения информационной избыточности были заложены в конце 40-х годов в фундаментальных трудах К.-Э.Шеннона по теории информации и кибернетике. С тех пор появилось большое количество работ советских и зарубежных авторов, в которых рассматривается и решается задача сжатия дискретной- информации. В этих работах наибольшее развитие получили статистические и комбинаторные методы, а также исследованы многие вопросы, связанные с устранением избыточности кода. Разработанные алгоритмы сжимающего кодирования реализованы на программном или аппаратном уровне в некоторых практических приложениях. Однако, несмотря на значительные успехи, достигнутые в решении указанной проблемы, разработка, исследование и внедрение новых, а также усовершенствование существующих методов сжатия при организации базы данных АСУП является актуальной задачей.Это обусловлено тем, что имеющиеся теоретические разработки либо носят общий характер, либо не учитывают спещкаику информации »перерабатываемой в данном конкретном приложении. К тому же они не получили в АСУП должного практического применения.

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

Научная новизна. В работе впервые рассмотрен и решен ряд задач, связанных с устранением информационной избыточности в базе данных АСУП. В частности: исследованы вопросы эффективности применения методов сжатия информации при организации базы данных АСУП; разработаны способы повышения эффективности итерационных алгоритмов наращивания; решена задача достижения максимальной степени сжатия при использовании зонного метода; разработан один алгоритм решения задачи декомпозиции; разработан и исследован эффективный статистический метод сжатия информации, вырабатываемой неэргодическим источником сообщений.

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

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

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

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

В первой главе вводятся основные понятия и определения. Описывается формальная постановка задачи сжатия в терминах теории информации. Рассматриваются особенности организации и методов обработки базы данных АСУП. Исследуется специфика информации, содержащейся в этой базе, в том числе црисущие ей виды информационной избыточности. Сделан обзор литературы по тем методам сжатия информации, которые могут быть использованы в АСУП.

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

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

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

Основные результаты и выводы главы 4

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

1. АЙГНЕР М. Комбинаторная теория. М. : Мир, 1982. - 558 с.

2. АЙНБЕРГ В.Д., ГЕРОНИМУС 10.В. Основы программирования для Единой Системы ЭВМ. М. : Машиностроение, 1980. - 336 с.

3. АКУШСКИЙ И.Я., ЗАБОЛОЦКИЙ В.Н. О комбинаторном подходе к идее сжатия информации. Цифровая вычислительная техника и программирование, 1971, вып. 6, с. 5-17.

4. АЛЬЯНАХ И.Н. Внешние запоминающие устройства ЕС ЗВМ.-М. : Сов.радио, 1979. 208 с.

5. АНДОН Ф.И., Д0ВГ0П0ЛЫЙ В.Г., К0Н03ЕНК0 В.И. и др. Основные положения системы управления базы данных ОКА. Управляющие системы и машины, 1977, & 2, с. 44-49.

6. БАБКИН В.Ф., КРШОВ А.Б. Кодирование дискретных функций с заданной суммой значений. В кн.: Кодирование в сложных системах : Сб.научн.тр. • М., 1974, с. 184-188.

7. БАБКИН В.Ф., КРЮКОВ А.Б. Нумерация двоичных последовательностей с ограниченными длинами серий. В ich. : Кодирование в сложных системах. : Сб. научн. тр. М., 1974, с.120-184.

8. БЕЛЛМАН Р., КАЛАЕА Р. Динамическое программирование и современная теория управления. М.: Наука, 1969, с. 118.

9. БЕЛЛМАН Р., ДРЕЙФУС С. Прикладные задачи динамического программирования. М. : Наука, 1965. - 460 с.

10. БЕРЕЗЮК Н.Т., АНДРУЩЕНКО А.Г., МОЩИЦКИЙ С.С. и др. Кодирование информации (двоичные коды) : Справочник. Харьков : Высшая школа, 1978. - 252 с.

11. БЕРЛЕКЭМП Э. Алгебраическая теория кодирования. М. : Мир, 1971. - 477 с.

12. БОБКО И.М. Программа уплотнения информации при ее обработке на ЭВМ. Научные труды Новосибирского ун-та : Экономика,1965, вып. 5, с.72-79.

13. БОЙКО В.В., САВИНКОВ В.М. Проектирование информационной базы автоматизированной системы на основе СУБД. М. : Финансы и статистика, 1982. - 174 с.

14. БОНДАРЬ Е.В. Об одном методе повышения эффективности процессов сжатия текстовой информации. Программирование, 1982,3, с.80-85.

15. БОНДАРЬ Е.В. Один алгоритм решения задачи декомпозиции. -В кн. : Теоретические и прикладные задачи проектирования АСУ : Сб. науч. тр. Киев, 1983, с.70-74.

16. БОНДАРЬ Е.В. Один метод сжатия информации в АСУ. В кн. : Математические методы и модели в автоматизированных системах управления и переработки информации. : Сб. науч. тр. Киев, 1982, с.97-99.

17. БОРОВКОВ A.A. Курс теории вероятностей. М. : Наука,1972. - 287 с.

18. БРИТАВСКИЙ Г.М., ГЛЕЙБЕРМАН В.Г. Об одном подходе к представлению информации. Управляющие системы и машины, 1979, Je 2, с.34-36.

19. ВЛАДОВСКИЙ И.М. АСУ 1редприятием на базе ЕС ЭВМ. М. : Энергия, 1977. - 119 с.

20. ВОЛЪФОВИЦ Дгк. Теоремы кодирования теории информации. М.: Мир, 1967. - 248 с.

21. ГИХМАН И.И., СКОРОХОД A.B. Введение в теорию случайных процессов. 2-е изд., перераб. - М. : Наука, 1969. - 567 с.

22. ГНЕДЕНКО Б.В. Курс теории вероятностей. 5-е изд. »стереотип. - М. : Наука, 1969. - 400 с.

23. ГУРЕВИЧ В.И. Управление вводом-выводом в ЕС ЭВМ. М.: Сов. радио, 1980. - 304 с.

24. ДЕЙТ К. Введение в системы баз данных. М. : Наука, 1980.- 463 с.

25. ЖЕРМЕЙН К. Программирование на IBM/360. 4-е изд., стереотип. - М. : Мир, 1978. - 872 с.

26. ДОЛИНСМ В.Г., ПАХОМЕНКОВ Е.И. Об одном алгоритме сжатия информации в АСУ. В кн. : Автоматизация управления промышленными предприятиями : Сб. науч.тр. Киев, 1974, с.84-88.

27. ЕРЕМЕЕВ И.С. О некоторых вопросах компактирования информации. В кн. : Проектирование и внедрение новых средств вычислительной техники : Сб. науч. тр. Киев, 1975, с.36-42.

28. ЕРЕМЕЕВ И.С. Устройства сжатия информации. М. : Энергия, 1980. - 161 с.

29. ММЕРИН Д.Г., МЯСНИКОВ В.А. Автоматизированные и автоматические системы управления. 2-е изд., перераб. и доп. - М. : Энергия, 1979. - 591 с.

30. КАШ Д., ЛЕБЕН Д>х. Техника програглмирования для ms. Методология использования DL / I. М. : Финансы и статистика, 1983. - 248 с.

31. КЕЛЕХСАЕВ A.A., БЕЖЕВ А.П. Системы интеграции и обработки данных СИОДЕ и СЙ0Д2. М. : Статистика, 1977. - 208 с.

32. КЕМЕВИ Дне., СНЕЛЛ Дк. Конечные цепи Маркова. М. : Наука, 1970. - 242 с.

33. КНУТ Д. Искусство программирования для ЭВМ. Т.З М. : Мир, 1976. - 844 с.

34. КОЛМОГОРОВ А.Н. Три подхода к определению понятия "количество информации". Проблемы передачи информации, 1965, т.1, вып.1, с.13-16.

35. КОРБУТ A.A., ФИНКЕЛЬШТЕЙН Ю.Ю. Дискретное программирование.- М. : Наука, 1969. 368 с.

36. КОШАН А. Введение в прикладную комбинаторику. М. : Наука, 1975. - 480 с.

37. КОШАН А., АНРИ-ЛАБОРДЕР А. Методы и модели исследования операции. Целочисленное программирование. М.: Мир, 1977,- 432 с.

38. КУЛИК В.Т., ЦАРЕГРАДСКИЙ Л.Е. Комбинаторные алгоритмы рационального кодирования информационных массивов АСУ. Киев : Изд-во Института кибернетики АН УССР, 1971. - 30 с.

39. КУРБАКОВ К.И. Кодирование и поиск информации в автоматическом словаре. М. : Сов.радио, 1968. - 248 с.

40. ЛЕБЕДЕВ В.Н., СОКОЛОВ А.П. Введение в систему программирования ОС ЕС. М. : Статистика, 1978. - 144 с.

41. ЛЕБЕДЕВ В.Н. Введение в системы программирования.-М. : Статистика, 1975. 311 с.

42. ЛИПАЕВ В.В., ЯШКОВ С.Ф. Эффективность методов организации вычислительного процесса. в АСУ. М.: Статистика, 1975.-с. 256.

43. МАРТИН Дк. Организация баз данных в вычислительных системах.- 2-е изд., доп. М.: Мир, 1980. - 662 с.

44. МОДШ A.A. Основы разработки и развития АСУ. М.: Наука, 1981. - 279 с.

45. ОВЧАРОВ Л.А., СЕЛЕТКОВ С.Н. Автоматизированные банки данных.- М.: Финансы и статистика, 1982. 261 с.

46. ОЛЛЕ Т.В. Предложения КОДАСИЛ по управлению базами данных.- М.: Финансы и статистика, 1981. 286 с.

47. ПЕРВИН Ю.А., ШЕВЯКОВА Т.К. Динамические информационные системы на предприятии. М.: Статистика, 1975. - 232 с.

48. ПЕЕВОЗВАНСКИЙ A.A., ГАИЦГОРИ В.Г. Декомпозиция, агрегирование и приближенная оптимизация. М.: Наука, 1979. - 342 с.

49. ПУРВИН Ю.В., МИХАЙЛОВ S.A., ДЕМИДОВ И.В., ЦЫГАНКОВ Ю.И. Система управления базами данных СЕДАН. М.: Финансы и статистика, 1982. - 174 с.

50. РАДЦ У. Программирование на языке ассемблера и вычислительные системы IBM 360 и 370. М.: Мир, 1979. - 592 с.56