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

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2009
Автори:	Князева, М.А., Тимченко, В.А.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут проблем штучного інтелекту МОН України та НАН України 2009
Теми:	Прикладные интеллектуальные системы
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/8207
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Преобразование графовых структур представления информации / М.А. Князева, В.А. Тимченко // Штучний інтелект. — 2009. — № 4. — С. 425-436. — Бібліогр.: 9 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-8207
record_format	dspace
spelling	irk-123456789-82072010-05-17T12:01:37Z Преобразование графовых структур представления информации Князева, М.А. Тимченко, В.А. Прикладные интеллектуальные системы В работе изложен подход к преобразованию информации, представленной графовыми структурами. Представлена концептуальная схема преобразования информации на основе проекций графовых структур. Приведены модели, в соответствии с которыми описываются графовые структуры и проекции, которые являются спецификацией на преобразование графов. Предложенный подход реализован в прототипе, предназначенном для перевода программ с одного процедурного языка программирования на другой. Прототип поддерживает языки Pascal, С, язык моделей структурных программ и разработан в рамках системы преобразований программ. Прототип реализован в среде программирования Java. У роботі викладено підхід до перетворення інформації, представленої графовими структурами. Представлено концептуальну схему перетворення інформації на основі проекцій графових структур. Наведені моделі, відповідно до яких описуються графові структури і проекції, які є специфікацією на перетворення графів. Запропонований підхід реалізовано в прототипі, призначеному для перекладу програм з однієї процедурної мови програмування на іншу. Прототип підтримує мови Pascal, С, мову моделей структурних програм і розроблений в рамках системи перетворень програм. Прототип реалізовано в середовищі програмування Java. The paper develops and illustrates an approach to transformation of information represented as graph structures. The conceptual scheme of information transformation based on mapping of graph structures is presented. There are three levels in the scheme that allows reaching flexibility on operation with the information of different subject domains. To each level there correspond the models intended for the description of the information and the specification of ways of its transformation. The transformer can process both with structural and with textual information representations. It offers models describing graph structures and mappings which are specifications for graph transformation. This approach is implemented in the prototype that ensures program translation from one procedural programming language into another. The prototype supports such languages as Pascal, C, language of structure program models and is developed within the framework of the program transformation system. The prototype is implemented in the Java programming environment. 2009 Article Преобразование графовых структур представления информации / М.А. Князева, В.А. Тимченко // Штучний інтелект. — 2009. — № 4. — С. 425-436. — Бібліогр.: 9 назв. — рос. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/8207 004.89 ru Інститут проблем штучного інтелекту МОН України та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Прикладные интеллектуальные системы Прикладные интеллектуальные системы
spellingShingle	Прикладные интеллектуальные системы Прикладные интеллектуальные системы Князева, М.А. Тимченко, В.А. Преобразование графовых структур представления информации
description	В работе изложен подход к преобразованию информации, представленной графовыми структурами. Представлена концептуальная схема преобразования информации на основе проекций графовых структур. Приведены модели, в соответствии с которыми описываются графовые структуры и проекции, которые являются спецификацией на преобразование графов. Предложенный подход реализован в прототипе, предназначенном для перевода программ с одного процедурного языка программирования на другой. Прототип поддерживает языки Pascal, С, язык моделей структурных программ и разработан в рамках системы преобразований программ. Прототип реализован в среде программирования Java.
format	Article
author	Князева, М.А. Тимченко, В.А.
author_facet	Князева, М.А. Тимченко, В.А.
author_sort	Князева, М.А.
title	Преобразование графовых структур представления информации
title_short	Преобразование графовых структур представления информации
title_full	Преобразование графовых структур представления информации
title_fullStr	Преобразование графовых структур представления информации
title_full_unstemmed	Преобразование графовых структур представления информации
title_sort	преобразование графовых структур представления информации
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
publishDate	2009
topic_facet	Прикладные интеллектуальные системы
url	http://dspace.nbuv.gov.ua/handle/123456789/8207
citation_txt	Преобразование графовых структур представления информации / М.А. Князева, В.А. Тимченко // Штучний інтелект. — 2009. — № 4. — С. 425-436. — Бібліогр.: 9 назв. — рос.
work_keys_str_mv	AT knâzevama preobrazovaniegrafovyhstrukturpredstavleniâinformacii AT timčenkova preobrazovaniegrafovyhstrukturpredstavleniâinformacii
first_indexed	2025-07-02T10:57:39Z
last_indexed	2025-07-02T10:57:39Z
_version_	1836532482218917888
fulltext	«Штучний інтелект» 4’2009 425 8К УДК 004.89 М.А. Князева, В.А. Тимченко Институт автоматики и процессов управления ДВО РАН, г. Владивосток, Россия mak@imcs.dvgu.ru, rakot2k@mail.ru. Преобразование графовых структур представления информации В работе изложен подход к преобразованию информации, представленной графовыми структурами. Представлена концептуальная схема преобразования информации на основе проекций графовых структур. Приведены модели, в соответствии с которыми описываются графовые структуры и проекции, которые являются спецификацией на преобразование графов. Предложенный подход реализован в прототипе, предназначенном для перевода программ с одного процедурного языка программирования на другой. Прототип поддерживает языки Pascal, С, язык моделей структурных программ и разработан в рамках системы преобразований программ. Прототип реализован в среде программирования Java. Введение На сегодняшний день компьютерная обработка информации является одним из критических видов деятельности в большинстве прикладных и теоретических областей. Этот вид деятельности включает задачи по получению, инженерии, хранению, уп- равлению и использованию различных видов данных и знаний. При этом происходит постоянный обмен информацией между компьютерными системами, их компонентами, людьми, организациями. Видами информации могут быть искусственные языки (языки программирования, языки спецификаций, языки описания структур данных и т.д.), знания, данные, программы, представленные на этих языках. При передаче информации могут изменяться такие ее аспекты, как формат представ- ления (изменение структуры, модели, языка представления), интерпретация, уровень детализации. Примером может служить преобразование информации на разных этапах раз- работки информационных систем. Концептуальные модели данных, независимые от реализации, отображаются на релевантные им модели данных, ориентированные на реализацию в конкретной операционной среде. Например, семантическая модель дан- ных типа «сущность-связь» отображается на реляционную модель данных, представ- ление на языке UML − в представление на языке XML [1]. Другим ярким примером может служить по-прежнему остро востребованная за- дача трансляции компьютерных программ с одного языка представления этих программ на другой. Она возникает в таких областях, как: – разработка систем, предназначенных для анализа, оптимизации и распараллеливания программ, в особенности таких, которые работают с несколькими языками исходных текстов программ. При этом выполняется трансляция анализируемой программы на исходном языке во внутреннее представление, используемое затем для анализа и пре- образований [2], [3]; – программный реинжиниринг, который занимается в частности проблемой перево- да программ с устаревших языков на новые; Князева М.А., Тимченко В.А. «Искусственный интеллект» 4’2009 426 8К – разработка языков программирования, ориентированных на решение задач в конк- ретной предметной области (domain-specific languages, DSLs). Это, как правило, ком- пактные языки программирования, предназначенные для решения специфических для некоторой предметной области задач в противовес языкам программирования общего назначения, цель создания которых – решение вычислительных задач в любой пред- метной области [4]. Они получают все большее распространение в связи с тем, что число современных прикладных задач стремительно растет. Задача построения трансляторов всегда определяется как высокотехнологичная и времяемкая, которая может быть решена только соответствующими специалистами. Это препятствует массовой разработке средств трансляции. Многие задачи, связанные с преобразованием разных видов информации, еще на- ходятся на стадии исследования, различные исследовательские группы разрабатыва- ют методы их решения разной эффективности. Значительный вклад в исследование этой проблемы внесли В.Ш. Кауфман, A. Königs, H.-J. Kreowski, S. Kuske, A. Schürr и другие. Ввиду сложности этих задач, они в основном рассматриваются как самостоятель- ные, методы их решения разрабатываются независимо друг от друга. На стадии исс- ледований с целью проверки этих методов создаются макеты программных систем. Поскольку при создании макетов проблема их совместимости не рассматривается, раз- работчики, концентрируя свое внимание на методах решения, часто выбирают специфи- ческое представление используемой информации. Получаемые в результате компью- терные системы часто оказываются несовместимыми между собой, замыкаются на своих предметных областях, оказываются не способными взаимодействовать друг с другом для решения задач преобразования информации, возникающих на стыке пред- метных областей. Сопровождение зачастую оказывается совершенно нерентабельным по срокам и трудозатратам. В результате они не могут быть использованы для решения задач другой предметной области и задач на стыке предметных областей, вследствие чего для этого приходится разрабатывать новое программное обеспечение. Другой проблемой разрабатываемых таким образом макетов программных сис- тем является то, что большинство из них, как правило, не доводятся до уровня рас- пределенных сетевых приложений (функционирующих в среде Интранет/Интернет), а так и остаются на уровне настольных персональных версий и используются только там, где разрабатываются. Это резко сокращает доступность, масштаб практического применения и, как следствие, востребуемость таких средств, что в свою очередь пре- пятствует накоплению опыта их практического использования и тормозит темпы их дальнейшего развития. Любая информация может быть представлена в виде графовых структур (напри- мер, представление информации в виде семантических сетей), а потому преобразова- ние информации может рассматриваться как преобразование графовых структур. Графовые структуры данных являются естественным и наглядным средством представления сложных структур и процессов. Это позволяет широко использовать их в компьютерных системах при решении различных задач. Во многих из этих задач графы используются для представления данных неоднородной структуры. К таким задачам относятся представление деревьев абстрактного синтаксиса программ в трансля- торах языков программирования, описание структуры и обработки объектных моделей документов, обработка сложных структур данных предметной области в прикладных задачах и т.п. Преобразование графовых структур представления информации «Штучний інтелект» 4’2009 427 8К Большинство моделей, над которыми проводятся преобразования, представля- ются в виде графовых структур. Преобразования описываются в терминах графов и операций над ними и основываются на правилах, в результате выполнения которых порождается новый граф на основе заданного исходного. Данная работа посвящена описанию концептуальной схемы преобразования ин- формации, представленной графовыми структурами, а также описанию модели преоб- разования графовых структур и результатов экспериментального исследования прототипа программного средства при решении практических задач. Работа выполнена при финансовой поддержке ДВО РАН в рамках Программы № 2 Президиума РАН «Интеллектуальные информационные технологии, математи- ческое моделирование, системный анализ и автоматизация», проект 09-I-П2-04 «Развитие систем управления базами знаний с коллективным доступом». Концепция преобразования информации на основе проекции графовых структур Рассмотрим концептуальную схему преобразования информации, представлен- ной графовыми структурами, в которой на основе видов используемой информации выделяется три уровня (рис. 1). Третий (самый верхний) уровень объединяет модели, в соответствии с которыми формируется информация второго уровня. Второй уровень объединяет описание графовых структур и описание структурных проекций. Описание графовых структур является метаинформацией по отношению к информации первого уровня, объединяющего, в свою очередь, информацию, которая подвергается собствен- но преобразованию. Основная идея подхода состоит в том, чтобы представить исходную и целевую информацию в виде графовой структуры. На рис. 1 им соответствуют компоненты: Описание графовой структуры исходной информации, Описание графовой структуры целевой информации. Это представление включает в себя: – определение множества понятий описываемой предметной области (вершины графа). Каждое понятие, за исключением понятий, соответствующих терминальным верши- нам графа, определяется через множество некоторых других понятий, при этом подра- зумевается, что понятия, через которые определено некоторое другое понятие, входят в содержание последнего; – во множестве понятий существует некоторое выделенное понятие, называемое аксиомой, в которое не входит ни одна дуга. В одну и ту же вершину может входить несколько дуг; – определение множества направленных бинарных отношений (им соответствуют дуги графа), в которых понятия между собой состоят. Понятия связываются между собой направленными отношениями по принципу: понятие, из которого выходит ду- га, определено через понятие, в которое дуга входит; – дополнительная информация о понятии или отношении может быть посредством множества значений атрибутов, связанных с этим понятием или отношением. Множест- во связанных атрибутов может быть пустым. При работе с информацией бывает удобно иметь возможность преобразовывать ее к виду, понятному человеку, причем не в виде сети вершин, а в виде привычного текстового описания. Наряду с этой ситуацией имеет место обратная ситуация, когда по текстовому представлению информации необходимо получить ее представление в виде графовой структуры. Примером этого является преобразование текста програм- мы в ее дерево абстрактного синтаксиса. Если необходимо занести в базу графовых структур имеющуюся информацию и существует уже описание графовой структуры Князева М.А., Тимченко В.А. «Искусственный интеллект» 4’2009 428 8К этой информации, то проще построить сеть понятий, соответствующую заносимой ин- формации, автоматически, чем вручную, с помощью средства редактирования порождать эту сеть под управлением описания графовой структуры этой информации. Таким образом, необходимо иметь средства для решения этих взаимно противоположных за- дач – задачи синтеза и задачи анализа текстов. Рисунок 1 – Концептуальная схема преобразования информации, представленной графовыми структурами Чтобы иметь возможность работать с текстовым представлением информации, необходимо описать связь графовой структуры с элементами ее конкретного син- таксиса. Преобразование графовых структур представления информации «Штучний інтелект» 4’2009 429 8К Эта связь определяет содержание правильных конструкций языка текстового пред- ставления этого графа с точки зрения синтаксиса этого языка. Связь графовой структуры с ее конкретным синтаксисом содержит такие элементы языка, как пунктуационное наполнение, порядок следования слов и т.д. Данный вид информации ограничивает способ выражения в виде текста того смысла, который заложен в описании графовой структуры, поэтому далее эта связь бу- дет называться синтаксическими ограничениями. Графовые структуры описываются в соответствии с Моделью описания графовых структур. Данная модель в частности регламентирует правила задания синтаксических ограничений и используется Средством редактирования графовых структур для опи- сания графовых структур в терминах этой модели. В свою очередь, Модель описания графовых структур формируется и редактируется с помощью Средства редактиро- вания модели описания графовых структур. Описание графовой структуры информации и описание ее синтаксических огра- ничений необходимы для осуществления процедуры синтаксического анализа тексто- вого представления информации на заданном языке и формирования представления этой информации в виде графовой структуры, а также обратной процедуры – синтеза текстового представления информации по ее представлению в виде графовой структуры. Эти процедуры выполняются соответственно Средством анализа текстовых представ- лений информации и Средством синтеза текстовых представлений информации. Представление информации в виде графовой структуры (Целевой граф – Гц) яв- ляется «целевой» (это информация более низкого уровня общности, называемая «целевой информацией») графовой структурой по отношению к Описанию графовой структуры (Метаграф – Гм), представляющей собой информацию высокого уровня общности, называемую «метаинформацией». Это означает, что вершины Гц, представляющие понятия, входящие в объемы понятий, представленных вершинами из Гм, являются эк- земплярами этих вершин из графовой структуры Гм, тогда как сами вершины графовой структуры Гм являются прототипами для вершин из графовой структуры Гц. Например, граф Гм содержит вершину «имя», а граф Гц содержит вершины «Иванов», «Александ- ров». Эти последние вершины представляют понятия, входящие в объемы понятия, представленного вершиной «имя», из Гц и являются экземплярами этой вершины. Таким образом, можно говорить, что Гц описан в терминах Гм, или (что то же самое), что «метаинформация» представляет язык для описания «целевой информации». Например, пусть задан фрагмент описания графовой структуры, представляю- щий данные о пациенте (рис. 2). Рисунок 2 – Фрагмент графовой структуры, задающий описание пациента Описание конкретного пациента «Пациент 1» будет выглядеть так, как показа- но на рис. 3. Князева М.А., Тимченко В.А. «Искусственный интеллект» 4’2009 430 8К Рисунок 3 – Фрагмент графовой структуры, описывающий «Пациента 1» Задавая правила отображения этой информации в конкретную текстовую форму (синтаксические ограничения графовой структуры, задающей описание пациента), можно получить, например, представление о «Пациенте 1» в следующем виде: Иванова Елена Владимировна, жен., 27 лет. Семантика преобразования задается Описанием структурной проекции графовой структуры исходного представления информации на графовую структуру целевого представления. Описание проекции фиксирует множество соответствий между фрагмен- тами исходной и целевой графовых структур. Для описания проекций разработан язык описания структурных проекций. Структурные проекции описываются в соответствии с Моделью описания струк- турных проекций. Данная модель используется Средством редактирования структур- ных проекций для описания проекций в терминах этой модели. В свою очередь, Модель описания структурных проекций формируется и редактируется с помощью Средства редактирования модели описания структурных проекций. Преобразование информации, представленной графовыми структурами, на ос- нове заданной проекции Описания графа исходной информации на Описание графа целевой информации выполняет Средство преобразования графовых структур. Модель преобразования графовых структур на основе описания проекции Модель преобразования графовых структур на основе описания проекций GTM представляет собой пару (GDM, MDM), где GDM – модель описания графовых струк- тур, MDM – модель описания структурных проекций. Модель описания графовых структур GDM = (Concepts, Relations, Attributes, Axiom_Concept, Id_Concept, Const_Concept, Syntax_Restrictions) Concepts = {Concepti} 1 conceptscount i – конечное непустое множество понятий. Каждое понятие Concept описывается своим уникальным именем. Имя понятия представляет собой непустую последовательность символов и идентифицирует определенный класс объектов описываемой предметной области. Relations = {Relationi} 0 relationscount i – конечное, возможно пустое, множество отношений. Каждое отношение Relationi является направленным бинарным отношением (дугой), связывающим два понятия, и описывается следующим образом: Relationi = (Relation_ Name, Begin_Concept, End_Concept). Relation_Name – имя отношения, которое представляет собой непустую последователь- ность символов. Begin_Concept – имя понятия, из которого дуга исходит – понятие-начало отношения. Begin_Concept  Concepts. Преобразование графовых структур представления информации «Штучний інтелект» 4’2009 431 8К End_Concept – имя понятия, в которое дуга входит – понятие-конец отношения. End_ Concept  Concepts. Attributes = {Attributei} 0 attributescount i – конечное, возможно пустое, множество атрибутов. Каждый атрибут Attributei представляет некоторое свойство понятия и описывается следующим образом: Attributei = (Attribute_Name, Attribute_Argument, Attribute_Value). Attribute_Name – имя атрибута, представляющее собой непустую последовательность символов. Attribute_Argument = (Attribute_Argument_Type, Attribute_Argument_Value)  аргумент атрибута описывается своим типом Attribute_Argument_Type и значением Attribute_ Argument_Value. Attribute_Argument_Type = {“Понятие”, “Отношение”, “Идентификатор”, “Константа”}. Attribute_Argument_Value  Concepts  Relations  Identifiers  Constants. Identifiers – конечное, возможно пустое, множество всех идентификаторов, присутст- вующих в исходном представлении информации. Constants – конечное, возможно пустое, множество всех констант и константных зна- чений, присутствующих в представлении информации. Аргументом атрибута может быть понятие (Attribute_Argument_Type = “Понятие”), отношение (Attribute_Argument_Type = “Отношение”), идентификатор (Attribute_Argument_ Type = “Идентификатор”) или константа (Attribute_Argument_Type = “Константа”). Attribute_Value = (Attribute_Value_Type, Attribute_Value_Value)  значение атрибута опи- сывается своим типом Attribute_Value_Type и значением Attribute_Value_Value. Attribute_Value_Type = {“Понятие”, “Идентификатор”, “Константа”, “Строковое”, “Це- лое”, “Вещественное”, “Логическое”}. Attribute_Value_Value  Concepts  Relations  Identifiers  Constants  String  Integer  Real  Boolean. String – множество строк. Integer – множество целых чисел. Real – множество вещественных чисел. Boolean – множество {Истина, Ложь}. Значением атрибута может быть понятие (Attribute_Value_Type = “Понятие”), отно- шение (Attribute_Argument_Type = “Отношение”), идентификатор (Attribute_Value_ Type = “Идентификатор”), константа (Attribute_Value_Type = “Константа”), последователь- ность символов, интерпретируемых как строковая константа (Attribute_Value_Type = “Строковое”), целое число из множества целых чисел (Attribute_Value_Type = “Целое”), вещественное число из множества вещественных чисел (Attribute_Value_Type = “Ве- щественное”) или элемент множества {Истина, Ложь} (Attribute_Value_Type = “Логи- ческое”). Axiom_Concept – понятие, представляющее аксиому в описании графовой структуры информации, оно единственно, и через него не может быть выражено ни одно другое понятие, т.е. в него не входит ни одна дуга. Axiom_Concept  Concepts. Id_Concept – понятие, представляющее идентификатор в описании графовой структу- ры информации, оно единственно и не может быть выражено через другие понятия, т.е. является терминальным понятием. Id_Concept  Concepts. Const_Concept – понятие, представляющее константу в описании графовой структу- ры информации, оно единственно и не может быть выражено через другие понятия, т.е. является терминальным понятием. Const_Concept  Concepts. Князева М.А., Тимченко В.А. «Искусственный интеллект» 4’2009 432 8К Syntax_Restrictions = (Lexica, Syntax) – описание синтаксических ограничений. Оно мо- жет отсутствовать, если не требуется иметь дело с текстовым представлением инфор- мации. Lexica = {<Lexem_Typei, Definitioni>} 5 1i Syntax = {<Concepti, Definitioni >} 2 1 conceptscount i   Lexem_Typei  {“Идентификатор”, “Целое число”, “Вещественное число”, “Строко- вая константа”, “Ограничитель строковой константы”}. Concepti  Concepts \ { Id_Concept, Const_Concept} Definitioni – строка символов, включающая метасимволы и представляющая конкрет- ное лексическое или синтаксическое ограничение для конкретного понятия или вида лексемы. Приведенная выше модель синтаксических ограничений имеет свое представле- ние, в терминах которого пользователь может формально описывать язык текстового представления информации. Синтаксические ограничения языка кроме, собственно, синтаксических опреде- лений содержат еще и определения лексики. Для лексики и синтаксиса может быть определено единственное ограничение для каждого элемента. Синтаксическое определение представляет собой определение объемлющего по- нятия графовой структуры через объемлемые понятия и элементы конкретного син- таксиса языка текстового представления. Лексический словарь языка определяется фиксированным набором вершин, со- ответствующих базовым типам данных – целое, вещественное и строковое и, кроме этого, определением вида идентификатора, или имени. Терминальная вершина «определение», описывающая сорт строковое, которой соответствует лексическое или синтаксическое ограничение для понятия, представлен- ного родительской вершиной. В сети понятий, описывающей синтаксические ограни- чения для конкретного языка текстового представления вершиной, соответствующей данной вершине будет являться терминальная вершина, значение которой задает кон- кретное лексическое или синтаксическое ограничение для конкретного понятия языка или вида лексемы. Все ограничения на вид лексем КС-языка задаются с помощью регулярных вы- ражений с использованием нотации perl5 [5]. Строка, представляющая синтаксическое определение, содержит специальные метасимволы, полное описание которых приводит- ся в диссертационной работе. Модель описания структурных проекций MDM представляет собой порождающую модель, определяющую семейство исчислений. Любая порождающая модель [6], [7] состоит из языка формального задания исчислений этой модели (языка для записи правил исчислений) и универсального рецепта этой модели. Последний определяется структурой состояний порождающего процесса, способом формирования начального состояния, способом построения порождающего процесса по правилам исчисления и начальному состоянию, а также правилом остановки порождающего процесса. Любое исчисление, заданное на языке порождающей модели, определяет множество порождающих процессов генерации графовых структур. Таким образом, множество порождающих процессов, получаемых в результате выполнения универсального ре- цепта порождающей модели для каждого конкретного исчисления, рассматриваются в качестве модели всех возможных процессов генерации графовых структур. Преобразование графовых структур представления информации «Штучний інтелект» 4’2009 433 8К Определим язык формального задания правил исчисления порождающей моде- ли процессов генерации графовых структур как семерку (Concepts, Relations, Attributes, Computable, Storable, Loadable, {%$} 0 0 n i   ), где Concepts – множество понятий, Relations – множество отношений, Attributes – множество атрибутов, Computable = {Истина, Ложь}, Storable = <boolean_value, alias_name>, Loadable = <boolean_value, alias_name>, boolean_value  {Истина, Ложь}, alias_name – строка символов, представляющая псевдоним для значения атрибута, под которым нужно сохранить это значение в хеш-таблицу или по которому нужно получить это значение из хеш-таблицы. Каждое исчисление порождающей модели задается конечным непустым множест- вом записанных на этом языке порождающих правил перевода исходной графовой структуры в целевую: π = {Rulei} 1 rulescount i . Каждое правило Rulei имеет вид   , где   Concepts  Relations  Attributes,   Concepts  Relations  (Attributes  Computable  Storable  Loadable). При этом Concepts  Relations  Attributes   и для любых 1, 2  Concepts  Relations  Attributes, если правила 11, 22 входят в π, то 1  2. Для формирования правил языка порождающей модели разработан язык описания структурных проекций, на котором пользователь может формально описывать проек- ции графовых структур. Каждое соответствие определяет набор понятий, отношений и атрибутов целевой графовой структуры, сопоставленный элементу исходной графовой структуры. Специфицирован абстрактный синтаксис языка описания структурных проек- ций и описана его операционная семантика. Исследование средства преобразования графовых структур при решении практических задач Предложенный подход реализован в прототипе, предназначенном для перевода программ с одного процедурного языка программирования на другой. Прототип под- держивает языки Pascal, С, язык модели структурных программ [8], [9] и разработан в рамках системы преобразований программ в специализированном банке знаний о пре- образованиях программ. Прототип реализован в среде программирования Java в среде разработки приложений IntelliJ Idea, с использованием ресурсов многоцелевого банка знаний (http://mpkbank2.dvo.ru/mpkbank/). Основной целью экспериментов, проводимых с программным средством, является установление того, насколько возможным и целесообразным является его использо- вание при решении задач преобразования информации, представленной графовыми структурами. В качестве примера рассмотрим использование программного средства при реше- нии задач перевода компьютерных программ c одного языка представления на другой. В качестве материала для эксперимента были выбраны: Князева М.А., Тимченко В.А. «Искусственный интеллект» 4’2009 434 8К 1. Графовая структура, описывающая устройство ограниченного подмножества языка программирования Pascal. 2. Графовая структура, описывающая устройство ограниченного подмножества языка программирования C. 3. Графовая структура, описывающая устройство базового языка модели струк- турных программ. В табл. 1 приведены некоторые количественные характеристики графовых струк- тур, представляющих описания этих языков. Таблица 1 – Количественные характеристики графовых структур, представляю- щих описания этих языков Характерис- тика Вид информации Количество понятий Количество отношений Количество атрибутов Количество синтаксических ограничений 1 105 170 103 2 141 216 139 3 16 15 25 В табл. 2 сведены данные о количестве соответствий в описании проекции i-го вида информации на j-й. Таблица 2 – Количество соответствий в описании проекции i-го вида информа- ции на j-й Вид информации 1 2 3 1 58 2 79 3 В табл. 3 приведены некоторые количественные характеристики графовых структур, представляющих программы на этих языках, а также приведено среднее время (в секундах), затраченное на выполнение анализа, генерации и синтеза соответственно. Ms (Mt)  {1, 2, 3}. Cs (Ct) – количество понятий в графовой структуре, представляющей программу на исходном (целевом) языке. Rs (Rt) – количество отношений в графовой структуре, представляющей программу на исходном (целевом) языке. As (At) – количество атри- бутов в графовой структуре, представляющей программу на исходном (целевом) языке. Ta – среднее время (в секундах), затраченное на анализ текстового представле- ния программы и формирования ее структурного представления. Tg – среднее время (в секундах), затраченное на генерацию структурного пред- ставления программы на целевом языке, на основе структурного представления этой программы на исходном языке. Ts – среднее время (в секундах), затраченное на синтез текстового представле- ния программы на основе ее структурного представления. Преобразование графовых структур представления информации «Штучний інтелект» 4’2009 435 8К Таблица 3 – Количественные характеристики процесса преобразования графовых структур, представляющих программы на описанных языках Ms Cs Rs As Mt Ct Rt At Ta Tg Ts 1 298 148 3 42 22 63 0.09 0.39 1 528 263 3 61 20 87 0.125 0.36 2 274 136 3 38 20 74 0.11 0.35 2 288 143 3 51 28 78 0.114 0.353 Замеры времени проводились при следующих условиях. Аппаратное и программное обеспечение, используемое при проведении экспе- риментов: На стороне клиента: Intel Pentium4 3 GHz, 2 Гб ОЗУ. Программное обеспече- ние: ОС MS Windows XP SP3. На стороне сервера: Intel Pentium4 3 GHz, 4 Гб ОЗУ. Программное обеспече- ние: ОС MS Windows 2003 Server, СУБД MySQL. Пропускная способность сетевого соединения между сервером и клиентом: 100 Мб/с. Заключение В работе изложен подход к преобразованию информации, представленной графо- выми структурами. Представлена концептуальная схема преобразования информации, представленной графовыми структурами. На основе видов используемой информации в схеме выделено три уровня. Третий уровень объединяет модели, в соответствии с ко- торыми формируется информация второго уровня. Второй уровень объединяет описание графовых структур и описание структурных проекций. Описание графовых структур является метаинформацией по отношению к информации первого уровня, объединяю- щего, в свою очередь, информацию, которая подвергается собственно преобразованию. Приведены модели, в соответствии с которыми описываются графовые структуры и проекции, которые являются спецификацией на преобразование графов. Литература 1. Hainaut Jean-Luc. Transformation-Based Database Engineering, Transformation of knowledge, informa- tion and data: Theory and Applications / Hainaut Jean-Luc : [Patrick van Bommel]. – Information Science Publishing, 2005. – Р. 1-28. 2. Partsch H. Program transformation systems / H. Partsch, R. Steinbrüggen // Computing Surveys. – 1983. – 15(3). 3. Штейнберг Б.Я. Открытая распараллеливающая система // Математические методы распараллели- вания рекуррентных циклов для суперкомпьютеров с параллельной памятью / Б.Я. Штейнберг. – Ростов н/Д. : Изд-во Рост. ун-та, 2004. – С. 166-182. 4. van Deursen A. Domain-specific languages: an annotated bibliography / A. van Deursen, P. Klint, J. Visser // SIGPLAN Not. – 2000. – Vol. 35. – P. 26-36. 5. Регулярные выражения в Perl5 [Электронный ресурс]. – Режим доступа : http://www.perl.com/doc/ FMTEYEWTK/regexps.html. 6. Успенский В.А. Теория алгоритмов: основные открытия и приложения / В.А. Успенский, А.Л. Се- менов. – М. : Наука ; гл. ред. физ.-мат. лит., 1987. – 288 с. – (Библиотечка программиста). Князева М.А., Тимченко В.А. «Искусственный интеллект» 4’2009 436 8К 7. Клещев А.С. Семантические порождающие модели. Общая точка зрения на фреймы и продукции в экспертных системах / Клещев А.С. – Владивосток : ИАПУ ДВНЦ АН СССР, 1986. – 39 с. – (Препринт). 8. Артемьева И.Л. Модель онтологии предметной области «Оптимизация последовательных программ». Ч. 1. Термины для описания объекта оптимизации / И.Л. Артемьева, М.А. Князева, О.А. Купневич // НТИ. Сер. 2. – 2002. – № 12. – С. 23-28. 9. Артемьева И.Л. Модель онтологии предметной области «Оптимизация последовательных прог- рамм». Ч. 2. Термины для описания процесса оптимизации / И.Л. Артемьева, М.А. Князева, О.А. Купневич // НТИ. Сер. 2. – 2003. – № 1. – С. 22-29. М.О. Князєва, В.А. Тимченко Перетворення графових структур представлення інформації У роботі викладено підхід до перетворення інформації, представленої графовими структурами. Представлено концептуальну схему перетворення інформації на основі проекцій графових структур. Наведені моделі, відповідно до яких описуються графові структури і проекції, які є специфікацією на перетворення графів. Запропонований підхід реалізовано в прототипі, призначеному для перекладу програм з однієї процедурної мови програмування на іншу. Прототип підтримує мови Pascal, С, мову моделей структурних програм і розроблений в рамках системи перетворень програм. Прототип реалізовано в середовищі програмування Java. M.A. Knyazeva, V.A. Timchenko Transformation of Information Represented as Graph Structures The paper develops and illustrates an approach to transformation of information represented as graph structures. The conceptual scheme of information transformation based on mapping of graph structures is presented. There are three levels in the scheme that allows reaching flexibility on operation with the information of different subject domains. To each level there correspond the models intended for the description of the information and the specification of ways of its transformation. The transformer can process both with structural and with textual information representations. It offers models describing graph structures and mappings which are specifications for graph transformation. This approach is implemented in the prototype that ensures program translation from one procedural programming language into another. The prototype supports such languages as Pascal, C, language of structure program models and is developed within the framework of the program transformation system. The prototype is implemented in the Java programming environment. Статья поступила в редакцию 26.06.2009.

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

Репозитарії

Схожі ресурси