авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 6 | 7 || 9 | 10 |   ...   | 26 |

«Электронные библиотеки: Перспективные Методы и Технологии, Электронные коллекции English Труды RCDL 2010 ...»

-- [ Страница 8 ] --

Тестирование алгоритмов проводилось на пол- разбиении разбиении ных текстах статей журнала «Вычислительные тех- dj и di принадле нологии». Электронная версия данного журнала жат одному кла- a c содержит библиографические описания, а также стеру в автомати полные тексты статей, вышедших в период с 1996- ческом разбиении го по 2010-й годы [http://www.ict.nsc.ru/jct], всего dj и di принадле было подготовлено для эксперимента около жат разным кла- b d статей из данного источника. Некоторым статьям на стерам в автома сайте журнала, помимо стандартных атрибутов (на тическом разбие звание, автор, год издания и т. п.), приписаны соот нии ветствующие коды классификатора из «Классифи кации математических сущностей» (MSC2000).

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

ночных ключевых слов, так и двухсловных ключе- Сравнительный анализ таблиц 4 и 5 показывает вых выражений (значение параметра работы жадно- стабильно более высокую точность алгоритма кла го алгоритма, показывающего, при какой мере сход- стеризации, использующего смешанный подход для ства можно говорить, что один документ достаточ- всех значений порогового параметра жадного алго но похож на другой, выбиралось в диапазоне 0.4 – ритма. Также данный подход дает более высокие 0.6). значения коэффициента полноты. Наиболее опти Как видно из представленных результатов, кла- мальный результат с коэффициентом ошибки Error стеризация документов на основе ключевых слово- = 0.1473 достигается с использованием порогового сочетаний показывает меньшее значение ошибки по значения, равного 0.6.

Таблица 4. Меры внешнего сходства, полученные Серия: Информационные технологии. – 2009. – на основе только одиночных ключевых слов Т. 7, Вып. 4. – С. 3-14.

[2] Пескова О.В. Автоматическое формирование Анализ на основе кодов классификатора 2-го рубрикатора полнотекстовых документов// Тру уровня (вида 76Mxx) ды Десятой Всерос. науч. конф. «Электронные Мера Значение параметра (величина библиотеки: перспективные методы и техноло схожести) гии, электронные коллекции» (RCDL’2008).

0.4 0.5 0.6 Дубна, 7 – 11 октября 2008 г. – С. 39-148.

[3] Михайлов А.И., Черный А.И, Гиляревский Р.С.

Recall 0.2263 0.2394 0. Основы информатики. – М.: Наука, 1968.

Precision 0.7749 0.8201 0.8464 [4] Кормен Т., Лейзерсон Ч., Ривест Р.М. Алго ритмы: построение и анализ. – М.:МЦНМО, Error 0.2251 0.1799 0. 2001.

F1 0.3503 0.3707 0.4668 [5] Барахнин В.Б., Нехаева В.А., Федотов А.М. О задании меры сходства для кластеризации тек Таблица 5. Меры внешнего сходства, полученные стовых документов // Вестник НГУ. Серия: Ин на основе как одиночных ключевых слов, так и формационные технологии. – 2008. – Т. 6, двухсловных выражений Вып. 1. – С. 3-9.

[6] Bezdek J.C., Pal N.R. Some new indexes of cluster Анализ на основе кодов классификатора 2-го validity // IEEE Transactions On Systems, Man уровня (вида 76Mxx) And Cybernetics. – 1998. – V. 28, No 3. – P. 301 Мера Значение параметра (величина схо 315.

жести) [7] Halkidi M., Batistakis V., Vazirgiannis M. On clus 0.4 0.5 0. tering validation // J. of Intelligent Information Sys Recall 0.2771 0.3796 0.4624 tems. – 2001. – V. 17, No 2/3. – P. 107-145.

[8] Шаров С.А. Частотный словарь русского языка.

Precision 0.8268 0.8493 0. – http://www.artint.ru/projects/frqlist.asp.

Error 0.1732 0.1507 0.1473 [9] Агеев М., Кураленок И., Некрестьянов И. Офи циальные метрики РОМИП 2006 // Труды F1 0.4150 0.5247 0. РОМИП'2006. – СПб: НУ ЦСИ, 2006. – http://romip.ru/romip2006/appendix_a_metrics.pdf.

Заключение Clustering of text documents based Проведенное сравнение результатов кластериза on composite key terms ции документов, принадлежащих корпусам близких по тематике текстов, показало целесообразность V.B. Barahnin, D.A. Tkachev применения общедоступных средств морфологиче ского анализа текстов для извлечения составных The classical approach to the coordinate indexing texts ключевых термов, поскольку использование по- with a view to their subsequent clustering is to use следних для подсчета меры сходства между доку- analysis tools based on the thesaurus treated the subject ментами дает заметно лучшие результаты по срав- area. But if we talk about the processing of texts rather нению с получаемыми при использовании лишь narrow topics, in such cases requires a very detailed одиночных ключевых слов, позволяя во многих thesauri, which are (at least, widely available), not for случаях избежать ошибок ложной координации, при all subject fields. The approach is based on the extrac этом рост вычислительных затрат на обработку од- tion of key phrases without an a priori constraint is ного текста незначителен. Разумеется, полученные much more universal. However, this approach has the результаты несколько уступают тем, которые воз- problem of selection of key terms.

можны при использовании для выделения ключе- The purpose of this article is to demonstrate the вых слов и словосочетаний тезауруса предметной practical advantages of clustering documents based on области, однако, поскольку речь идет об обработке key phrases compared to the very popular clustering корпусов текстов, близких по тематике, в таких based on the analysis of only one-word key terms. At случаях потребовались бы весьма подробные тезау- the same time to highlight the key phrases used publicly русы, которые имеются (по крайней мере, в широ- available software tools that do not require special ком доступе) далеко не для всех предметных облас- computing costs.

тей. Рассматриваемый же в статье подход носит гораздо более универсальный характер. Работа выполнена при частичной финансовой поддерж ке РФФИ (проекты 08-07-00229, 09-07-00277, 10-07 Литература 00302), Президентской программы «Ведущие научные школы РФ» (грант НШ-6068.2010.9) и интеграционных [1] Федотов А.М., Барахнин В.Б. К вопросу о поис- проектов СО РАН ке документов «по аналогии» // Вестник НГУ.

Некоторые методы классификации и поиска в электронной коллекции графических документов * А.А. Рогов, К.А. Рогова, П.В. Кириков, М.Ю. Быстров Петрозаводский государственный университет rogov@psu.karelia.ru, ksushar@mail.ru, lispad@gmail.com, maksimkab@yandex.ru для хранения графических документов, с учётом их Аннотация внутренних свойств и признаков документов, назы Речь идет о нескольких подходах к класси- ваемые коллекциями графических документов. К фикации и поиску в коллекциях графиче- сожалению, на данный момент нет каких-либо уни ских документов. Большое внимание уделя- версальных средств создания электронных коллек ется разработке алгоритма поиска, основан- ций графических документов, в которых изображе ного на скелете изображения. Все разрабо- ния не только хранятся в определенном порядке, но танные методы соединены в единой систе- и классифицированы по выделенным параметрам, и ме управления коллекциями графических по ним можно осуществлять поиск. Проблемой соз документов. Она позволяет хранить раз- дания подобного рода систем является необходи личные наборы графических и текстовых мость реализации механизма поиска данных, в про параметров для каждого графического до- цессе создания которого приходится решать целый кумента с учётом их типа, выполнять клас- ряд нетривиальных задач – фильтрации, сегмента сификацию и поиск графических докумен- ции, распознавания. Существуют различные подхо тов по различным комбинациям парамет- ды и даже рабочие алгоритмы решения этих задач, ров, а также на основе сходства. Разрабаты- однако в каждом конкретном случае необходимо ваемая система имеет веб-интерфейс и дос- выбирать ту или иную методику исходя из, специ тупна только через интернет. Апробация фикации разрабатываемой системы. Важно отме всех алгоритмов проводится на тестовой тить, что зачастую существующих алгоритмов об коллекции петроглифов Северной Фенно- работки недостаточно, и приходится либо занимать скандии. ся их усовершенствованием, либо созданием новых алгоритмов.

1 Введение В статье описаны особенности создания инфор мационной системы, позволяющей создавать, Новые компьютерные технологии позволяют управлять и анализировать коллекции графических создавать информационные системы, недоступные документов, с возможностями хранения иерархии ранее. Заметим, что наиболее требовательными к документов и значений наборов признаков, а также ресурсам аппаратного обеспечения являются систе поиска. В первой части рассказывается о свойствах мы для обработки мультимедийной информации – системы и технических особенностях ее реализации, изображений, видео, трехмерной графики. С про а во второй представлены непосредственно сами грессом информационных технологий меняются и методы классификации и поиска. Несмотря на то, парадигмы, используемые для создания информа что создаваемая система предназначена в первую ционных систем: объектно-ориентированный под очередь для научных исследований, подобный спо ход становится не только популярной концепцией соб описания графических объектов позволяет при программирования, но и находит своё отражение в менять систему в различных областях, например, теории построения баз данных. Объектно для создания каталога запчастей/товаров с иллюст ориентированные структуры данных, использую рациями, произведений художников и т. д. В дан щие в качестве данных абстрактные объекты, в не ный момент прототип информационной системы которых областях позволяют более точно модели апробируется на основе коллекции графических ровать логическую структуру по сравнению с реля документов петроглифов Северной Фенноскандии 1.

ционным подходом.

Одним из частных случаев объектно-ориенти рованных структур данных являются базы данных Фенноскандия – природная страна в Европе, включаю Труды 12й Всероссийской научной конференции щая Скандинавский полуостров (Швецию и Норвегию), «Электронные библиотеки: перспективные методы и Финляндию, Кольский полуостров и часть территории технологии, электронные коллекции» – RCDL’2010, СССР к С.-З. от линии Финский залив Балтийского моря – Казань, Россия, Ладожское и Онежское озёра – Онежская губа Белого моря различных схем разметки объектов, являющихся 2 Общие характеристики разрабатывае составными частями документа, для этого хранятся мой системы относительные координаты для предоставления Разрабатываемая система логически разделена возможности выделения объектов при различных на две части – пользовательскую и административ- масштабах отображения документа. Для корректной ную. Она предназначена для размещения на веб- работы пользовательского и административного сервере и обеспечивает доступ через интернет с лю- интерфейсов при выборке данных из схем разметок бого устройства, подключенного к сети. Выделим необходима сортировка объектов по занимаемой некоторые ее возможности: создание и редактиро- ими площади на графическом документе. Чтобы вание иерархической структуры коллекций графи- уменьшить вычислительную нагрузку на сервер баз ческих документов;

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

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

описательная статистика коллек- данных 13 таблиц. Структура базы, за исключением ции;

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

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

ской части реализован при помощи HTML, c ис пользованием JS и предоставляет администратору и 3 Описание структуры данных пользователю доступ к описанному выше функцио Содержание графических документов в виде би- налу через любой веб-браузер. Серверная часть вы нарных данных, а также сопутствующая информа- полнена на основе веб-сервера Apache c применени ция об их положении в иерархии и наборы индиви- ем PHP и сервера баз данных MySQL. Система по дуальных параметров хранятся в базе данных. Ско- зволяет администратору вводить графические доку рость доступа к бинарным данным графических менты в различных форматах, автоматически, при документов в нашей реализации несколько ниже, помощи графической библиотеки GDLib, выполняя чем при использовании файловой системы для хра- их приведение к единому формату для хранения в нения документов. Такой способ был выбран ввиду базе данных. Интерфейс администратора отобража ряда причин. Время обработки (масштабирования, ет иерархию графических документов в виде дерева наложения логотипа для охраны авторских прав и и позволяет редактировать структуру, добавлять и т. д.) значительно выше времени доступа, а потому удалять документы. Для каждого из них реализова было применено кэширование с сохранением ре- на возможность вводить и изменять схему разметки, зультатов обработки в файловой системе сервера. В показывающую положение объектов внутри доку случае чтения данных из коллекции результат бе- мента. В ходе апробации возникли проблемы с уче рётся из кэша, а потому время доступа к базе дан- том объектов, накладывающихся друг на друга. Для ных не играет роли. При этом упрощаются задачи их решения внедрено несколько концептуальных и переноса системы, сохранения резервных копий, а технических решений: схемы разметки могут быть также проверка целостности базы данных. Структу- разделены на слои, позволяя администратору рабо ра базы создана таким образом, чтобы иерархия тать с каждым из накладывающихся объектов от документов не имела ограничений по числу уровней дельно, для решения технической сложности с вы и числу узлов на каждом уровне. Для этого исполь- делением накладывающихся и вложенных областей;

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

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

знаков для объекта, выбранного на схеме разметки документа.

В настоящий момент производятся разработка модуля описательной статистики, а также портиро вание для использования совместно с веб-системой модулей классификации и поиска графических до Рис. 1. Бинарное изображение с одним объектом кументов по различным комбинациям параметров, ранее реализованных на языке C, а также на основе 6 Модуль структурного метода распоз сходства текстур, цветового восприятия и т. д.

навания бинарных изображений 5 Алгоритмы обработки и поиска изоб Среди существующих методов распознавания ражений изображений можно выделить класс методов, ис Современные компьютерные технологии позво- пользующих структурный (синтаксический) подход ляют создавать информационные системы для ре- к распознаванию [4]. Структурные методы основа шения задач в различных сферах человеческой дея- ны на получении структурно-грамматических при тельности: на производстве, в медицине, образова- знаков, когда в изображении выделяются элементы нии, безопасности, научных целях и т. д. Но как бы – признаки – и вводятся правила соединения этих сильно не отличались системы по их функциональ- элементов. Признаки и правила их соединения об ному назначению, всех их объединяет одно – необ- разуют грамматику. Анализ грамматики обеспечи ходимость организации поиска, причем эта необхо- вает принятие решений при сравнении изображе димость возрастает одновременно с ростом самой ний. Такой подход обеспечивает высокое быстро системы. Для динамических систем, т. е. систем, в действие, что дает ему неоспоримое преимущество которых объем данных постоянно растет, необхо- при работе с большой коллекцией графических до димо поиск организовывать так, чтобы он был осу- кументов.

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

даты и т. д). Здесь задача поиска сводится к сравне- Пример такого изображения представлен на рис. 1.

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

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

коллекции, наиболее на него похожие. Возникает Скелет изображения – это множество точек, яв ряд трудностей и проблем, специфических для дан- ляющихся центрами окружностей максимального ной области: радиуса, вписанных в это изображение [2] (рис. 2).

• объекты предъявляются на сложном фоне;

• объекты отличаются положением в поле зрения;

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

• изображения могут отличать геометриче- Рис. 2. Скелет изображения ские преобразования, включая такие, как аффинные При получении скелета обычно возникают «шу и проективные;

мовые ветви», которые не являются существенными • объекты могут быть изображены по конту при описании общей формы фигуры (рис. 2). Если ру или целиком.

удалить «шумовые ветви» (операция регуляризации Поиск сводится к задаче поиска изображений [1]) и затем аппроксимировать скелет прямыми ли [3], которая отличается сложностью алгоритмов ниями, то можно получить скелет, изображенный на обработки данных и низкой универсальностью. Рас рис. 3. Такой скелет состоит из множества прямых смотрим более подробно один из алгоритмов струк ребер. Смежные ребра образуют между собой углы.

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

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

Рис. 3. Скелет после регуляризации • выбирается i-я ветвь скелета, которая од и аппроксимации ним концом соединена с другой ветвью, а другим Предлагаемый алгоритм распознавания сводится нет, т. е. рассматривается внешняя ветвь;

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

регуляризация скелета;

аппроксимация скелета;

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

сравнение грамматик. Рас внутри восстановленного изображения, и соответст смотрим каждый из этапов более подробно венно S0 Si для любого i;

• если S0-Si P, где P – пороговая величина, 6.1 Получение скелета изображения то ветвь i удаляется из скелета;

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

огня при «выгорании» фигуры [2]. Представим себе, что вдоль всей границы фигуры одновременно заго- 6.4 Аппроксимация скелета рается огонь, который постепенно сжигает всю фи гуру, двигаясь от границы внутрь фигуры. Предпо лагается, что огонь распространяется с постоянной скоростью. Рассмотрим точки угасания огня, т. е. те точки, в которых происходит встреча нескольких (двух или более) огненных фронтов. Каждая такая точка одинаково удалена от начального положения Рис. 6. Пример аппроксимации скелета фронтов и, следовательно, принадлежит скелету Под аппроксимацией скелета понимается преоб изображения. Множество точек угасания огня обра разование набора ребер скелета в набор прямых зуют скелет изображения.

(рис. 3). Аппроксимация происходит с использова Один из наиболее эффективных алгоритмов, нием метода последовательных приближений [10].

реализующих данную идею для дискретных фигур, При этом в случае слабой кривизны ребра скелета является алгоритм Зонга – Суня [3], пример работы оно преобразовывается в одно ребро – прямую с которого представлен на рис. 4.

теми же вершинами, иначе ребро преобразовывает ся в набор прямых. В качестве меры кривизны ребра используется величина, которая обеспечивает полу чение оптимального количества ребер (рис. 6).

Рис. 4. Построение скелета изображения с помощью 6.5. Получение грамматики алгоритма Зонга – Суня Как уже упоминалось ранее, в качестве грамма 6.2 Регуляризация скелета тики рассматриваются прямые линии скелета и углы между ними. Процесс получения грамматики можно Целью данного этапа является удаление «шумо описать следующим образом:

вых ветвей» (рис. 2).

• произвольно выбирается внешняя прямая Из понятия скелета изображения как множества скелета L0;

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

восстановить исходное изображения, если в каждой • среди прямых, которые соединены с данной точке скелета нарисовать круг соответствующего прямой, выбирается та, которая составляет наи радиуса (рис. 5). Радиус круга вычисляется как рас меньший угол относительно данной против часовой стояние от данной точки скелета до ближайшей стрелки;

рассматривается также сама данная прямая точки контура фигуры.

с углом, равным 360є;

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

• если выбранная прямая совпадает с L0 – ко нец алгоритма. Иначе переход к п. 2.

Примечание: длина прямой является относи Рис. 5. Построение скелета и восстановление тельной величиной в процентах. За 100% берется изображения из скелета диаметр минимальной окружности, описанной во- Результаты работы программы оценивались субъек круг изображения скелета. тивно авторами статьи. Точность работы алгоритма Таким образом, получаемую грамматику можно была оценена в 70%.

записать в виде {li, i }, i = 1, 2,K, 2 n, где n – количе- В табл. 1 представлена информация о скорости работы алгоритма для изображения 250*250 пиксе ство прямых скелета.

лей.

На рис. 7 представлен пример получения грам матики из скелета. Здесь стрелками обозначено на- Таблица 1. Скорость работы алгоритма правление обхода скелета, 0 – точка, в которой на Этап Время выполнения чинается обход. Полученная грамматика имеет вид:

(в миллисекундах) {29,59 | 101,08} {33,77 | 98,97} {64,95 | 360} {64,95 | Получение скелета 106,98} {38,90 | 109,11} {52,76 | 360} {52,76 | Регуляризация скелета 130,64} {20,54 | 360} {20,54 | 120,25} {38,90 | Аппроксимация скелета 154,05} {33,77 | 100,19} {19,48 | 360} {19,48 | Получение грамматики 158,73} {29,59 | 360}.

Сравнение двух грамматик 6 (для 1000 сравне ний) Как видно из таблицы, основное время занимают операции получения и регуляризации скелета. В дальнейшем планируется увеличение скорости за Рис. 7. Получение грамматики счет оптимизации исходного кода программы и по иска новых алгоритмов.

6.6 Сравнение грамматик Однако для каждой коллекции изображений Конечным этапом структурных методов поиска можно построить грамматики только 1 раз и в даль является сравнение грамматик между собой. нейшем пользоваться ими при сравнении. Сама Пусть имеется 2 грамматики длины 2n: операция сравнения грамматик занимает незначи {li, i }, i = 1, 2,K, 2 n, {ki, i }, i = 1, 2,K, 2n. тельное время. Поэтому в целом можно утверждать, что алгоритм работает достаточно быстро.

Тогда грамматики равны, если для любого Существует также возможность сравнения i = 1,2, K,2n, выполняются равенства l i = k i, i = i.

грамматик частями. Однако для этого необходимо Однако с учетом ошибок измерения на реальных заранее исключить из грамматик лишние элементы, объектах следует задавать более слабое условие при этом не разрушив целостность фигуры, описы равенства li ki P, i i P2, i = 1, 2,K, 2n, ваемой грамматикой. Исследования в данной облас ти планируется провести в ближайшее время.

где P и P2 являются пороговыми величинами.

Начало обхода у двух одинаковых объектов мо 7 Модуль классификации и поиска в жет быть различным. Тогда требуется для грамма графической коллекции на основе приз тики длиной n рассмотреть n циклических сдвигов, каждый из которых описывает исходное изображе- наков, извлеченных из изображений ние. Тогда сравнение двух грамматик представляет В данном модуле используются характеристики собой процесс сравнения всевозможных их цикли изображений, получаемые непосредственно из кар ческих сдвигов (всего сравнений n). Если хотя бы тинки. Признаками самого низкого уровня считают одна пара сравниваемых грамматик будет равна, то ся цвет и текстура рисунка [6]. За основу берется и исходные грамматики равны между собой, то цветовая модель HSV (Hue, Saturation, Value – тон, есть, если найдется такое = 1,2, K,2n, что выпол насыщенность, значение), так как она ближе к вос няются условия li k j P, i j P2, приятию человеком изображений. Координатами цвета в данной модели являются [7]:

i = 1, 2,K, 2n, где Hue – цветовой тон, (например, красный, зелё i +, если i + 2n,.

j= ный или сине-голубой);

варьируется в пределах 0 – i + n, если i + n. 360°, однако иногда приводится к диапазону 0 – 100 или 0 – 1.

6.7 Результаты работы алгоритма Saturation – насыщенность;

варьируется в преде лах 0 – 100 или 0 – 1. Чем больше этот параметр, Описанный метод структурного распознавания тем «чище» цвет, поэтому этот параметр иногда скелетов бинарных изображений был реализован в называют чистотой цвета. Чем ближе этот параметр виде приложения и протестирован на электронной к нулю, тем ближе цвет к нейтральному серому.

коллекции изображений петроглифов Северной Value (значение цвета) или Brightness – яркость.

Фенноскандии. Для тестирования были отобраны Также задаётся в пределах 0 – 100 и 0 – 1.

200 черно-белых изображений петроглифов. Для Модель была создана Элви Реем Смитом в каждого из них была построена грамматика, и затем году. Она является нелинейным преобразованием все грамматики попарно сравнивались между собой.

модели RGB.

[3] Рогов А.А., Рогова К.А., Кириков П.В., Быст 7.1 Признаки цвета ров М.Ю. Информационная система для созда Разделим все цветовое пространство на 18 от ния и управления электронными коллекциями резков по тону, 3 – по насыщенности и 3 – по значе графических документов // Электронные биб нию. Используется два типа признаков. Первый тип лиотеки: перспективные методы и технологии, – стандартные гистограммы для всего изображения.

электронные коллекции: Труды XI Всерос. науч.

Для второго типа все изображение делится на пря конф. RCDL’2009 (Петрозаводск, Россия, 17 – моугольники от 2*2 до 16*16. Для каждого блока 21 сентября 2009 г.). – Петрозаводск: КарНЦ вычисляется наиболее часто встречающийся цвет.

РАН, 2009. – С. 433-438.

Он хранится как бинарный признак в зависимости [4] Фу К. Структурные методы в распознавании от интервала попадания. Эта операция проделыва образов. – М.: Мир, 1977.

ется для каждого компонента цвета. Таким образом, [5] Zhang T.Y., Suen C.Y. A fast parallel algorithm for получаем 55080 (340 блоков*18*3*3) возможных thinning digital patterns // Commun. ACM. – 1984.

признаков для блока и 162 (18*3*3) цветовые гисто – V. 27, No 3. – P. 236-239.

граммы для изображения в целом [8].

[6] Westerveld T. Image retrieval: content versus con text// Content-Based Multimedia Information Ac 7.2 Признаки текстуры cess, RIAO 2000 – C.I.D.-C.A.S.I.S., 2000. – По определению, текстура – пространственно P. 276-284.

растянутый образец, построенный повторяющимися [7] Kolenda T., Hansen L.K., Larsen J., Winther O.

аналогичными элементами, которые называются Independent component analysis for understanding элементы текстуры [6]. В данном случае использу- multimedia content// Proc. of IEEE Workshop on ется набор фильтров Габора, где каждый фильтр Neural Networks for Signal Processing XII, Pis дает специфическую текстуру, частоту и направле- cataway, New Jersey, 2002. IEEE Press. Martigny, ние. Изначально фильтры Габора имеют возмож- Valais, Switzerland, Sept. 4 – 6, 2002. – P. 757 ность определения текстуры. Для реализации алго- 766.

ритмов используются фильтры при разных длинах [8] http://ru.wikipedia.org/wiki/HSV_(цветовая_моде волн и ориентациях [8]. Кроме того, аналогично ль).

выделению признаков цвета из изображения, рису- [9] Movellan J.R.. Tutorial on Gabor filters. – http:// нок разбивается на блоки (2*2, 4*3). На основе mplab.ucsd.edu/tutorials/gabor.pdf.

фильтрации для каждого блока, так же, как и для [10] Дегтярева А., Вежневец В. Line fitting, или ме изображения в целом, получаются признаки. Под- тоды аппроксимации набора точек прямой // робное описание фильтров Габора приведено в [9]. Компьютерная графика и мультимедиа. – 2003.

– №1(3). – http://cgm.computergraphics.ru/ 7.3 Методы классификации и поиска content/view/41.

На основе полученных признаков и их комбина Some classification and search methods in ций производится поиск изображений в графиче ской коллекции. Кроме того, проводится классифи- graphic document electronic collection кация изображений в графической базе данных. Для A.A. Rogov, K.A. Rogova, P.V. Kirikov, решения этих задач планируется использовать ста M.Yu. Bystrov тистические методы, такие, как факторный анализ или канонический корреляционный анализ. В на- We present some approaches to classifying and search стоящий момент проводятся тестирования методов. ing in graphic documents collections. Special attention we give to a search algorithm, based on image skeleton.

8 Заключение All developed methods are composed in a single system for management of graphic documents collections. This Перечисленные подходы и методы не являются system allows to storage different sets of graphic and исчерпывающими для разрабатываемой системы, то textual parameters for each depiction based on its type, есть существуют различные другие методы обра to carry classification and retrieval documents by a vari ботки и анализа изображений, которые можно ис ety of parameters combinations or by their similarity.

пользовать для решения поставленных задач.

The system has a web-interface and access is provided through Internet.

Литература All methods are approved on a test collection of petroglyphs depictions from Northern Fennoscandia.

[1] Домахина Л.Г. Регуляризация скелета для зада чи сравнения формы // Математические методы * Работа выполнена при финансовой поддержке РГНФ, распознавания образов: доклады XIV Всерос.

(проект 08-01-12116) конф. – М., 2009. – С. 342-346.

[2] Местецкий Л.М. Непрерывная морфология би нарных изображений. Фигуры, скелеты, цирку ляры. – М.: Физматлит, 2009.

Особенности алгебраического подхода к формированию онтологий © Е.М. Бениаминов, В.А. Лапшин, Д.В. Перов Российский государственный гуманитарный университет, г. Москва mefrill@ yandex.ru гий. Операции представляют в онтологии как отно Аннотация шения между объектами, так и средства построения В работе описывается алгебраический под- новых понятий (типов) из уже существующих.

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

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

сываемый в работе подход реализован в Полученное множество классов эквивалентности проекте ЭЗОП (http://www.ezop–project.ru). является внутренним (машинным) представлением онтологии и может быть использовано для вычис 1 Введение лений.

Каждый класс эквивалентности в описанной Большинство популярных инструментов по выше конструкции содержит бесконечное множест строения онтологий использует в качестве основно во термов. Оперировать такими множествами не го формализма моделирования те или иные логики возможно, поэтому для каждого класса выбирается исчисления предикатов [2]. Так, в языке OWL [5], его представитель или дескриптор. Пусть, напри который на данный момент является «de facto»

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

гий, используется формализм логики предикатов «сложение» +:INT,INTINT первого порядка с элементами языка второго поряд и ка (различными встроенными в язык ограничениями «вычитание» –:INT,INTINT.

на вид предикатов онтологии). В данной работе описывается другой формализм, на основе которого Тогда константа 5: INT будет дескриптором клас можно формировать онтологии, а именно: алгеб са, содержащего термы +(2,3), –(+(2,7),4) и т. п. Ка раический подход к формированию онтологий ждый терм здесь представляет арифметическое вы [9, 11].

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

мируются на основе множества имен типов и имен В алгебраическом подходе, как и в логическом, операций, называемого сигнатурой. Сигнатуры онтологии представляют собой теории, но в алгеб обычно формируются пользователями системы, раическом подходе пользователь может определять предоставляющей сервис по формированию онтоло свои операции, которые из одних понятий (типов) и отображений между ними (предполагается, что опе Труды 12й Всероссийской научной конференции рации удовлетворяют некоторым условиям, которые «Электронные библиотеки: перспективные методы также задаются пользователем в виде равенств) и технологии, электронные коллекции» – строит новые понятия и отображения. Типы сигна RCDL’2010, Казань, Россия, туры – это типы (классы) онтологии, а операции могут представлять соотношения между объектами После того, как введены сигнатурные символы типов или быть конструкторами новых объектов. На операций и классов, можно определить соотноше операции (т. е. на соотношения между объектами ния равенства. Мы определим только некоторые из онтологии) налагаются ограничения посредством возможных соотношений, этого кажется вполне соотношений в виде равенств. На основе такого достаточным для иллюстрации:

описания можно производить вычисления (находить Дедушка(X)={Отец(Отец(X));

Отец(Мать(X))}, дескрипторы классов) стандартным способом, ис- Бабушка(X)={Мать(Отец(X));

Мать(Мать(X))}, пользуя правила переписывания, задаваемые соот- Отец(Брат-по-отцу(X))=Отец(X), ношениями–равенствами, или используя операции Отец(Родная-сестра(X))=Отец(X), вычисления, специально заданные для некоторых Мать(Родная-сестра(X))=Мать(X).

сигнатур. Например, можно было бы для имен опе- Введенные соотношения очевидны и выражают раций «сложение» и «вычитание» задать их семан- известные факты относительно родственных отно тику (вычисление дескриптора терма) обычным вы- шений. Подклассы Дедушка и Бабушка задаются числением арифметического выражения, как это перечислением их элементов, а остальные родст делается на калькуляторе. венные подклассы – условиями в виде равенств.

Имена операций в сигнатуре синтаксически Заметим, что в операциях используются подстанов можно рассматривать как правила контекстно- ки типов вместо их подтипов. Например, операция свободной порождающей грамматики Хомского [6]. Отец берет в качестве единственного параметра тип Например, операцию «сложения» +:INT,INTINT Человек, но в соотношениях ему этой операции пе можно задать как INT+(INT,INT). Это правило редаются типы Мужчина и Женщина.

контекстно-свободной грамматики можно записать Введем теперь константы (объекты классов) как в инфиксном виде. В этом случае получим правило операции без параметров:

INTINT+INT. Здесь символ «+» выступает в каче- Иван : Мужчина, стве терминала контекстно-свободной грамматики, Василий : Мужчина, а имя типа INT – как нетерминальный символ. Владимир : Мужчина, Такие инфиксные записи имен операций со Константин : Мужчина, строками внутри будем называть шаблонами. Каж- Марья : Женщина, дому имени операции можно поставить в соответст- Татьяна : Женщина, вие один или более шаблонов и, обратно, каждому Анастасия : Женщина.

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

который более синтаксически близок к содержанию Отец(Иван) = Василий, описываемой онтологии, чем имена операций, запи- Мать(Татьяна) = Марья, санные в префиксном виде. Мать(Анастасия) = Марья, Брат-по-отцу(Владимир) = Константин, 2 Иллюстративный пример Родная-сестра(Владимир) = Анастасия.

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

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

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

Мужчина и Женщина. Типы Мужчина и Женщина Отец(Отец(Владимир)) являются подтипами (подклассами) типа Человек.

и Отношение тип – подтип обозначим с помощью Отец(Мать(Владимир)).

символа «», т. е. имеем:

Но, так как выполняется Анастасия=Родная Мужчина Человек, сестра(Владимир), то в онтологии вычисляемого Женщина Человек.

выражения Мать(Владимир), Мать(Анастасия) и Ввиду того, что отец и мать у каждого человека Марья – синонимы, среди которых в качестве пред определяются однозначно, эти отношения можно ставителя (дескриптора) выделяется простейшее:

представить в виду функциональных символов:

Марья. Отсюда выражение для второго дедушки Отец : Человек Мужчина, Отец(Мать(Владимир)) синонимично выражению Мать : Человек Женщина.

Отец(Мария), которое и выдается как более корот Пусть X – переменная типа Человек, тогда опре кое.

делим параметрически родственные классы как Конечно, определенные в примере соотношения подклассы класса Человек следующим образом:

достаточно примитивны. Но вполне можно опреде Дедушка(X : Человек) Мужчина, лить онтологию булевой алгебры и использовать ее Бабушка(X : Человек) Женщина, операции для задания логики более сложных соот Брат-по-отцу(X : Человек) Мужчина, ношений. Булеву алгебру можно определить в от Родная-сестра(X : Человек) Женщина.

дельной онтологии и просто подгружать к онтоло- элементов. В онтологии наименьший тип (класс) гии семейных отношений как внешний модуль. Мо- обычно называют «ничто», а наибольший носит дульность онтологий, формируемых на основе ал- название «объект» (thing). Отношение иерархии гебраического подхода, реализуется просто, это яв- формирует дерево, если для каждого типа разреша ляется одним из его преимуществ. ется иметь не более одного родителя (в этом случае На практике в качестве базовых онтологий (он- наибольшей нижней гранью любых двух элементов тологий ядра) сначала определяют различные мате- является наименьший элемент), и образует направ матические понятия: множества и операции на них, ленный ациклический граф, если разрешено множе числа и булевы типы. Только после этого вводят ственное наследование типов.

Имена операций имеют вид :s1s2.. sns, операции как элементы специального типа «Опера ция». Соотношения вида тип – подтип обычно так- т. е. вместе с именем операции указываются типы ее же определяют с помощью специально введенной аргументов и тип результата.

операции, не используя для этого структуру решет- -алгебра для сигнатуры =(S,OP) – это семей ки на множестве типов сигнатуры алгебры, которая ство A множеств As, заданных для каждого сорта s представляет данную онтологию.

Далее мы рассмотрим введенные выше понятия более формально. S и называемых носителями алгебры A, а также 3 Абстрактные алгебраические типы В алгебраическом подходе для представления семейство отображений :As1As2…Asn As, понятий используются так называемые многосорт- заданных для каждого имени операции в сигнату ные алгебры [1, 8]. Для определения многосортной ре =(S,OP). Иначе говоря, на семействе множеств, алгебры сначала задается ее сигнатура как пара представляющих в -алгебре типы, имена которых =(S,OP), состоящая из множества S имен типов заданы в множестве S, задаются отображения, име (сортов) и множества имен операций OP. на и типы которых заданы в множестве. Каждая Обычно на множестве S не задается никаких от- такая -алгебра представляет собой модель вычис ношений, что, в общем, не отражает того, что типы ления, заданную на именах типов и операций, пере в онтологии в подавляющем большинстве случаев численных в сигнатуре.

образуют иерархию. Поэтому часто на множестве S Пусть X обозначает некоторое множество (мно определяется отношение частичного порядка так, жество переменных), элементы которого типизиро чтобы это множество образовывало решетку. Ре- ваны типами из множества S. Тогда термом сигна шеткой называется алгебраическая структура, за- туры называется выражение вида (T1, T1,…, Tn), данная на частично-упорядоченном множестве та ким образом, что выполняются следующие условия:

где – это имя операции, а T1, T1,…, Tn – это • для любых двух элементов s1, s2 S имеется их либо переменные соответствующих типов, либо термы, сформированные из имен операций данной сигнатуры тем же способом. Например, пусть +:INTINTINT – это операция из сигнатуры непосредственный родительский элемент sp S, =(S,OP) и a, b, c X – переменные. Тогда выраже представляющий собой наименьшую верхнюю грань этих элементов;

ние +(a,b) образует терм. Вместо параметров можно поставить имя операции «+», т. к. тип ее результата • для любых двух элементов s1, s2 S имеется их совпадает с типами параметров. Например, выраже ние +(+(a,b),c) также образует терм. Множество термов, образованных на основе операций данной -алгебры с переменными X, обозначается как T(X). В качестве переменных можно использовать непосредственных дочерний элемент sc S, константы, образуемые из имен операций с местно стью ноль, т. е. операций вида :s с пустым спи представляющий собой наибольшую нижнюю ском параметров. Множество всевозможных тер грань этих элементов. мов, образованных из констант и имен операций для Обычно используют т. н. полные решетки, т. е. данной сигнатуры, обозначается T.

такие решетки, у которых существуют наибольший Множество термов T(X) представляет собой и наименьший элементы для любого множества алгебру, т. е. имеет алгебраическую структуру. Дей Тогда в качестве дескриптора можно использовать сам вычисляемый терм.

ствительно, каждому имени типа s S в сигнатуре Нахождение дескриптора терма можно прово дить на основе правил переписывания, но можно реализовать отдельную семантику для некоторых =(S,OP) можно сопоставить множество термов, чья операций. Например, для операции сигнатура имени операции имеет тип s в качестве *:INTINTINT можно ввести семантику простым результата. Например, типу INT из примера выше процессорным вычислением произведения двух будут соответствовать термы вида +(a,b), +(+(a,b),c), чисел. Вычисление производится по древовидному +(+(a,b),+(c,b)) и т. д. Семантика операций также представлению терма путем обхода в глубину слева прозрачна: каждому имени операции :s1s2.. направо. Таким образом, для терма *(+(3,2),4) сна чала будут вычислены термы *(+(3,2) и 4, а затем sns и каждой n-ке термов t1, t1,…, tn типов s1, задействована внешняя процедура, которая вычис s1,…, sn, соответственно, дается в качестве значения лит результат сложения 5 и 4, и этот результат будет терм типа s вида (t1, t1,…, tn). Например, для опе возвращен в качестве дескриптора терма *(+(3,2),4).

рации *:INTINTINT термам +(a,b) и Алгебраический подход к спецификации доста +(+(a,b),+(b,c)) дается в соответствие терм точно хорошо изучен. Например, язык алгебраиче *(+(a,b),+(+(a,b),+(c,b))). ских спецификаций CASL [7] разработан специаль Для наложения ограничений на операции - но созданной для этой цели группой CoFI [4]. Этот алгебры используются соотношения в виде ра- язык используется преимущественно для моделиро венств. Точнее, равенство – это тройка вида вания программных модулей, но известны работы, (X,T1,T2), где T1 и T2 – термы, образованные из посвященные использованию языка CASL для мо операций -алгебры и переменных из X. Например, делирования онтологий [11].

({a},+(a,b),+(b,a)) выражает свойство коммутатив 4 Описание синтаксиса языка онтоло ности операции +. Часто равенства записывают про гии шаблонами сто в виде T1= T2, а множество переменных опреде ляется из контекста. Например, равенство Термы представляющей онтологию конечной ({a},+(a,b),+(b,a)) можно записать просто аппроксимации инициальной -алгебры формиру +(a,b)=+(b,a). ются на основе операций сигнатуры =(S,OP). Опе Множество термов T, где в качестве перемен- рации сигнатуры записываются в префиксном виде, ных используются константы (т.


е. символы опера- но можно ввести инфиксную запись операций. На ций, список аргументов которых пуст. Например, пример, терм операции +:INTINTINT вида +(3,5) константа 5 определяется как операция 5:INT), можно записать в виде 3+5. Каждая такая инфикс образуют т. н. алгебру замкнутых термов. Множе- ная запись представляет собой правило контекстно ство T можно факторизовать по отношению экви- свободной порождающей грамматики [6], в левой части которого стоит символ сорта результата опе валентности, задаваемому соотношениями равенст рации. Инфиксную запись операции, в которой ва. Полученное множество также образует алгебру i кроме параметров могут быть строки символов, бу и называется инициальной -алгеброй. Классы эк дем называть шаблоном.

вивалентности этой алгебры – это бесконечные Шаблоны позволяют расширять синтаксис языка множества термов. На практике используется ко представления онтологии. Синтаксически шаблон нечное приближение классов эквивалентности ини представляет собой строку, в которой могут быть циальной -алгебры, в котором каждый класс со «дырки», которые имеют типы. Также шаблон име держит только конечное множество термов. Такое ет тип результата. Таким образом, каждый шаблон приближение называется конечной аппроксимацией представляет операцию в сигнатуре -алгебры, инициальной -алгебры.

представляющей данную онтологию. Добавление Каждому классу эквивалентности инициальной синтаксических шаблонов расширяет множество алгебры обычно дается в соответствие его предста имен операций -алгебры онтологии и позволяет витель или «дескриптор». Чаще всего дескриптор расширить синтаксис языка представления онтоло представляет собой самый короткий терм данного гии.

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

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

между «дырками» могут рассматриваться как тер Вычисление можно производить переписыванием миналы. Например, инфиксная запись операции термов, если рассматривать соотношения эквива +:INTINTINT – это правило INTINT ’+’ INT, лентности как задание правил переписывания. Ко где INT – это нетерминальный символ, а ’+’ пред нечно, в этом случае не гарантируется, что дескрип ставляет собой терминал грамматики.

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

таксические» типы, которые необходимы только для того, чтобы управлять процессом синтаксиче- учебного процесса» и различные его подтипы. В ского анализа. Например, можно задать грамматику ЭЗОП отношение тип – подтип задается не с помо арифметических выражений следующим образом. щью рассмотренного выше механизма определения Сигнатура =(S,OP) состоит из типов INT, PLUS и решетки типов сигнатуры, а с помощью специально MUL с операциями +:MULPLUSPLUS и определенной для этих целей операции. Иначе го *:INTMULMUL. Также сделаем тип PLUS под- воря, типы сигнатуры рассматриваются как простое типом типа INT, а тип MUL – подтипом типа PLUS. множество без какой-либо алгебраической структу Каждое такое отношение тип – подтип генерирует ры, а отношение тип – подтип моделируется по правило вида тип подтип. Добавим также тип средством введения в сигнатуру соответствующей NUM для выделения констант и сделаем его подти- операции. Каждый раз, когда в тексте онтологии пом типа MUL. Таким образом, для данной сигна- встречается выражение «[A] – область», в сигнатуру туры можно определить следующую грамматику онтологии добавляется тип A, а также в конечную шаблонов: аппроксимацию инициальной алгебры онтологии PLUS MUL ’+’ PLUS добавляется терм вида «элемент(A,область)». Опе MUL NUM ’*’ MUL рация «элемент» используется для моделирования INT PLUS отношения «элемент области».

PLUS MUL Для задания отношения тип – подтип использу MUL NUM ется шаблон вида:

Предположим теперь, что в сигнатуре =(S,OP) Подобласти @A : @Type-list.

заданы константы 1:NUM, 2:NUM и 3:NUM. Здесь символ @ используется для выделения имен Тогда выражение 1+2*3 будет преобразовано в терм типов в шаблоне. Вместо типа Type-list можно +(1,*(2,3)). вставлять различные конструкции, задаваемые шаб лонами с типом результата Type-list. В этом шабло 5 Определение шаблонов в системе не не только вводятся подтипы типа A, но также ЭЗОП имена типов в списке добавляются в сигнатуру он тологии, если они еще не были объявлены как типы.

В системе ЭЗОП [3] реализованы описанные Чтобы выделить имя такого еще необъявленного выше принципы моделирования онтологий с помо типа, используются квадратные скобки.

щью алгебраического подхода. ЭЗОП также под Другой пример представляет собой простейшую держивает введение новых операций и типов в сиг онтологию равномерного движения.

натуру, представляющую описание мира модели Путь, скорость, время: real.

руемой онтологии. Операции вводятся с помощью Путь = скорость*время.

шаблонов. Рассмотрим примеры описания онтоло Время = путь/скорость.

гии в системе ЭЗОП.

Скорость = путь/время.

Сначала рассмотрим простой пример таксоно Введем шаблон «@Тело равномерно движется со мии помещений учебного учреждения. В этом при скоростью @V»

мере не вводится шаблонов, задаются только типы и с переменными: «Тело: new;

V: real_выражение»

их иерархия.

и переменной результата «x: команда»;

[помещения учебного процесса –] область.

Пояснения: [Вводится объект @Тело, равномер но движущийся со скоростью @V] Подобласти помещения учебного процесса:

Условие применения шаблона:

[учебное помещение], [] [служебное помещение].

Действие шаблона:

[x=пустая команда;

Подобласти учебное помещение:

тело - объект понятия «равномерное движение»;

[аудитория], тело’s скорость = V].

[учебный класс], [помещение лаборатории].

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

спецификациях переменные рассматриваются как [помещение деканата], константы (операции с пустым списком парамет [помещение кафедры], ров), которые могут быть использованы в соотно помещение лаборатории.

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

левой стороны стоят термы из переменных, а с пра [помещение учебной части], вой – термы, обозначающие имена арифметических [помещение бухгалтерии].

операций.

Следующая синтаксическая конструкция вводит В ЭЗОП каждый тип является элементом типа новый шаблон. Введение нового шаблона произво «область», верно и обратное. Поэтому выражение дится с помощью специального шаблона:

вида «A – область» задает A как тип сигнатуры. В примере выше задаются базовый тип «помещения Основное отличие алгебраического и логическо Введем шаблон «текст вводимого шаблона» с го подходов к формированию онтологий от состоит переменными «текст объявления переменных» и в том, что типы теорий, которыми представляются переменной результата «текст объявления пере онтологии в этих подходах, различны. В алгебраи менной результата»

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

применение шаблона Теории с выделенным отношением равенства Действие шаблона: семантика шаблона используются в логике и базах данных, где пред В данном случае вводится шаблон для описания ставляют их алгебраические модели. В соответствии онтологий равномерного движения. В этом шаблоне с общим алгебраическим подходом онтологии, в имеются две «дырки»: Тело и V. Скорость задается которой определяются сигнатура и аксиомы теории, вещественным числом, а Тело задает каждый раз соответствует алгебра, которая строится как множе при использовании данного шаблона новую кон- ство всех правильно построенных выражений в сиг станту (тип Тело объявлен как new). Тип результата натуре онтологии, профакторизованное по отноше шаблона – это команда, что означает выполнение нию логической эквивалентности этих выражений, некоторых действий при нахождении дескриптора следующей из аксиом-равенств, введенных в онто класса эквивалентности терма, задаваемого шабло- логии. В логике обычно интересуются только выра ном. Действия задаются в разделе Действие шаб- жениями, принимающими истинностные значения лона. В нашем случае константа, введенная на мес- (формулами). Основные вопросы логики – истинна те «дырки» Тело, задается как объект типа «равно- ли данная формула. В базах данных основной во мерное движение» (онтологии также рассматрива- прос: найти область истинности данной формулы ются как типы сигнатуры). В этом случае значения (запроса) в заданном состоянии базы данных.

переменных путь, скорость и время будут привя- Базе данных с заданным состоянием соответст заны к новому объекту. вует полная теория. Онтологиям в общем случае Онтологию равномерного движения можно ис- соответствуют неполные теории, но и при работе с пользовать в других онтологиях. Рассмотрим, на- ними пользователю хочется, чтобы система умела пример, учебную задачу на равномерное движение. отвечать на вопросы, чему равно данное выражение или при каких значения переменных истинна данная Пешеход равномерно движется со скоростью 5.

формула. Алгебраический подход к онтологиям Пешеход's время =2.

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


делирования процессов построения ответов на дан Велосипедист's время = пешеход's время.

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

введенный в другой онтологии, то в новую онтоло- В алгебраическом подходе к спецификациям хо гию загружается та онтология, в которой этот шаб- рошо разработана теория совместного использова лон был определен, и вводятся соотношения, связы- ния различных модулей спецификаций. Модули вающие понятия новой и старой онтологий в соот- естественным образом реализуются как набор опре ветствии с действием используемого шаблона. В деленных типов и операций, который может быть данном случае используется шаблон «@Тело рав- легко загружен и использован в другой специфика номерно движется со скоростью @V» из онтоло- ции при необходимости. При этом, конечно, необ гии равномерного движения, поэтому подгружают- ходимо, чтобы используемая спецификация могла ся все понятия и соотношения из этой онтологии. быть интегрирована в исходную на основе неких Конструкция вида «X’s время = число» задает зна- общих определений (языка ядра системы).

чение времени для объекта X. В системе не реали- В теории алгебраических спецификаций разра зована морфология, поэтому используется англоя- ботан специальный формализм, позволяющий объе зычная конструкция. динять спецификации друг с другом. Англоязычный Этот пример иллюстрирует одно из преиму- термин для этого формализма – Instition [9, 10]. In ществ алгебраического подхода: модульность опре- stition можно использовать для интеграции онтоло делений. Использование языковых шаблонов позво- гий, которые формируются на основе алгебраиче ляет автоматически загружать онтологии, шаблоны ского подхода. Теория Instition хорошо разработана которых используются в данной онтологии. и используется во многих системах алгебраических К онтологии задачи на равномерное движение спецификаций. Например, основания языка алгеб уже можно задавать вопросы. Например, можно раических спецификаций CASL [7] определяются с задать вопрос: помощью формализма Instition.

Велосипедист's путь?

Литература На что система даст ответ: 60.

[1] Бениаминов Е.М. Алгебраические методы в 6 Сравнение алгебраического и логичес теории баз данных и представлении знаний. – кого подходов формирования онтологий М.: Научный мир, 2003.

[2] Лапшин В.А. Онтологии в компьютерных сис темах. – М.: Научный мир, 2010.

[3] Сайт проекта ЭЗОП. – http://www.ezop project.ru.

[4] Страница группы CoFI. – http://www.informatik.

uni-bremen.de/cofi/wiki/ index.php/CoFI.

[5] Страница описания языка OWL. – http://www.

w3.org/TR/owl-features.

[6] Хопкрофт Дж.Э., Мотвани Р., Ульман Дж.Д.

Введение в теорию автоматов, языков и вычис лений, 2-е изд. – М.: Изд-во «Вильямс», 2002.

[7] Bidoit M., Mosses P. CASL User manual. Intro duction to using the common algebraic specifica tion language. – Series: Lecture Notes in Computer Science, 2004. – V. 2900.

[8] Goguen J., Malcolm G. Algebraic semantics of imperative programs. – MIT Press, 1996.

[9] Goguen J. Data, schema, ontology, and logic inte gration // Proc. CombLog'04 Workshop, Lisbon, Portugal, July 2004.

[10] Goguen J., Burstall R. Institutions:

Abstract

model theory for specification and programming // J. of the ACM. – 1992. – V. 39, No 1.

[11] Luttich K., Mossakowski T. Specification of on tologies in CASL // A. Varzi, L. Vieu eds., Formal Ontology in Information Systems. – Proc. of the Third Int. Conf. (FOIS-2004): IOS Press, Amster dam, 2004. – V. 114. – P. 140-150.

Specifics of an algebraic approach to ontology description E.M. Beniaminov, V.A. Lapshin, D.V. Perov In the text algebraic approach to ontology forming is described. The traditional methods of ontology forming are based on some modifications of predicate calculus' language. The algebraic approach has it own specifics that are discussed in the work. One of such specifics is the possibility to extend dynamically the language of ontology forming by user defined syntax. In the text principles of open language implementation for ontol ogy forming are described. Also, approaches to ontol ogy concepts definition basing on concept extension and precision are discussed. The described approach is implemented in project EZOP (http://www.ezop project.ru).

Работа выполнена при финансовой поддержке РФФИ (проект 09-07-00079) i Ввиду того, что эквивалентные термы обязательно име ют один и тот же тип, можно сопоставить каждому типу сигнатуры множество классов эквивалентности термов этого типа. Нетрудно показать, что отображение, которое мы определили выше для термов над множеством пере менных, работает и здесь и корректно преобразует разные классы эквивалентности друг в друга Взаимное отображение канонической информационной модели и языка OWL © С.А. Ступников, Н.А. Скворцов Институт проблем информатики РАН, г. Москва ssa@ipi.ac.ru, nskv@ipi.ac.ru Создание предметного посредника состоит из Аннотация двух фаз. На фазе консолидации происходит кон В статье рассматриваются основные аспек- цептуальное моделирование предметной области ты взаимного отображения канонической посредника силами некоторого экспертного сооб информационной модели и отличительных щества. Во время операционной фазы провайдеры конструкций языка OWL 2. Построенное информационных ресурсов регистрируют ресурсы в отображение позволяет использовать для посреднике, т. е. представляют спецификации ре решения задач вывода в онтологиях кано- сурсов в терминах концептуальной модели посред нической модели автоматические системы ника.

вывода для дескриптивных логик. Тем са- Одно из центральных мест в технологии посред мым достигается верификация концепту- ников занимает понятие канонической информаци ального моделирования предметных по- онной модели, служащей общим языком, унифици средников и интеграции в посредниках не- рующим разнообразные модели ресурсов. В данной однородных информационных ресурсов. статье в качестве канонической модели рассматри вается язык СИНТЕЗ [2], нацеленный на разработку 1 Введение предметных посредников для решения задач в сре дах неоднородных ресурсов. Применение техноло Развитие разнообразных информационных мо гии посредников с использованием языка СИНТЕЗ делей в современном мире, а также быстрое увели как канонической модели для решения научных чение числа компонентов и сервисов, представлен задач рассматривается в работах [12, 13].

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

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

неоднородных ресурсов являются предметные по При регистрации ресурсов важным моментом явля средники [1, 14] – специальный вид программного ется согласование (интеграция) онтологии посред обеспечения, образующий промежуточный слой ника и онтологий ресурсов [3].

между пользователем (приложением) и ресурсами.

В процессе концептуального проектирования и При разработке посредников предпочтительным интеграции онтологий возникает ряд задач, для ре является движимый приложениями подход. Описа шения которых необходимы методы формального ние предметной области приложения в таком под определения и инструментальные средства верифи ходе образуется независимо от ресурсов (в терми кации онтологий. К таким задачам относятся дока нах понятий, структур данных, функций, процес зательство непротиворечивости онтологий и погло сов), а затем релевантные приложению ресурсы щения одного понятия другим, определение полной отображаются в это описание. Преимуществами иерархии понятий и т. д. Автоматическое решение подхода являются масштабируемость по отноше подобных задач возможно в рамках дескриптивных нию к числу ресурсов, возможность достижения логик [4] при помощи специализированных инстру семантической интеграции ресурсов в контексте ментальных средств – систем вывода (например, конкретного приложения и доказательной иденти Pellet [5]).

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

моделирования и интеграции онтологий в предмет ных посредниках, является построение взаимного отображения канонической информационной моде Труды 12й Всероссийской научной конференции ли (языка СИНТЕЗ) и онтологической модели, слу «Электронные библиотеки: перспективные методы и жащей входным языком для систем вывода.

технологии, электронные коллекции» – RCDL’2010, Казань, Россия, Целью данной статьи является построение кор- классами. Явно разграничивая объявление типа и ректного взаимного отображения канонической мо- объявление коллекции (класса), язык СИНТЕЗ под дели и языка OWL 2 [6], расширяющее и уточняю- черкивает роль коллекции как представителя мно щее ранее проведенные исследования по отображе- жества объектов и роль типа как спецификации нию канонической модели и языка OWL [8]. структуры и поведения объектов, связанных с кол Статья организована следующим образом. В лекцией. Определения классов также могут вклю разделе 2 кратко описаны конструкции языка чать инварианты.

СИНТЕЗ, использующиеся для моделирования он- Коллекции могут связываться друг с другом от тологий. В разделе 3 на примерах рассмотрены ос- ношением обобщения-специализации (класс– новные детали взаимного отображения канониче- подкласс). Суперкласс включает в себя подкласс как ской модели и языка OWL 2. В разделе 4 рассмот- множество;

тип экземпляра суперкласса является рены интерпретации и модели онтологий языка супертипом типа экземпляра подкласса.

СИНТЕЗ, а также сводимость задач вывода в языке Атрибуты объектов в языке рассматриваются, в СИНТЕЗ. В разделе 5 доказана корректность ото- свою очередь, как объекты метаклассов ассоциаций, бражения канонической модели и языка OWL 2. устанавливающие соответствие между набором Предполагается, что читатель знаком с языком объектов в области определения ассоциации и на OWL 2 [6, 7, 9, 11]. бором объектов в области значений ассоциации.

Для определения формул используется язык ло гических формул многосортного объектного исчис 2 Каноническая информационная мо ления – типизированный вариант логики предика дель – язык СИНТЕЗ тов первого порядка.

Язык СИНТЕЗ представляет собой комбиниро ванную слабоструктурированную и объектную мо- 3 Взаимное отображение канонической дель данных. Слабоструктурированные (самоопи информационной модели и языка OWL сывающие) данные представлены фреймами [2].

Отображение онтологий. Онтология, представ Фреймы используются для описания любого объек ляемая в языке СИНТЕЗ онтологическим модулем та, включая объекты самого языка, такие как спе (например, Staff – описание персонала компании), цификации типов, классов, функций, утверждений.

отображается в одноименную онтологию OWL.

Фрейм можно рассматривать как множество атри бутов, называемых слотами. Каждый слот может СИНТЕЗ OWL иметь множество значений. Информация, характе- { Staff;

Ontology( Staff ризующая слот как целое, может быть представлена in: module, ontology;

… в метаслоте. Слоты разделяются знаком точка с … ) запятой, сам фрейм заключается в фигурные скобки. } Имя слота и множество его значений разделяются Заметим, что конструкции OWL в данной статье двоеточием, значения одного слота разделяются представлены в функциональном синтаксисе [9], запятыми. позволяющем компактно описывать структуру он Единицей определения канонической модели яв- тологий.

ляется модуль. Каждый модуль задает обобщенное Отображение классов. Класс (например, em представление информационных ресурсов, либо ployee) и тип его экземпляров (Employee) языка является модулем спецификации предметной облас- СИНТЕЗ представляются в OWL единой конструк ти или концептуального проекта информационной цией класса.

системы. СИНТЕЗ OWL Типизированные данные должны соответство- { employee;

in: class;

Class( employee ) вать абстрактным типам данных (АТД), описы- instance_section: Employee;

вающих состояние и поведение своих экземпляров в …} терминах атрибутов и методов типа. В определе- { Employee;

in: type;

… } ния типов могут быть включены инварианты типов Отображение свойств объектов. Свойства объ (ограничения, выраженные в виде замкнутой логи- ектов представляются в языке СИНТЕЗ при помощи ческой формулы). Помимо АТД, язык содержит метаклассов ассоциаций (например, WorksOn), за также обширную коллекцию встроенных типов дающих связь между объектами из области опреде данных. Отношение подтипа над множеством абст- ления ассоциации (класс employee) и объектами их рактных типов данных формирует решётку с Taval области значения ассоциации (класс project). Атри (общий супертип) в корне и типом Tnone (общий бут АТД (например, worksOn типа Employee) может подтип) внизу решётки. Значение подтипа может быть объявлен принадлежащим некоторому мета использоваться всюду, где ожидается значение су- классу ассоциаций. Такие свойства представляются пертипа;

подтип наследует элементы спецификации в OWL конструкцией ObjectProperty (если область супертипа;

допускается множественное наследова- значения ассоциации – коллекция объектов) или ние спецификаций подтипом. DataProperty (если область значения ассоциации – Однородные совокупности объектов предметной множество значений встроенного типа real, string и области представляются в канонической модели т. д., например, атрибут salary типа Empolyee). Ат рибуты, тип которых не является типом множества Отображение самоограничений. Пример инва (например, salary), имеют в языке СИНТЕЗ карди- рианта класса языка СИНТЕЗ (topManager), описы нальность 1 по умолчанию. В OWL кардинальность вающего ситуацию, когда объект согласно некото атрибута указывается явно (в случае атрибута salary рому свойству (boss) соотносится сам с собой (топ при помощи конструкции DataExactCardinality). менеджер является своим собственным начальни ком), приведен ниже. В OWL данная ситуация опи СИНТЕЗ OWL сывается конструкцией ObjectHasSelf.

{ WorksOn;

ObjectProperty( СИНТЕЗ OWL in: association, metaclass;

worksOn) instance_section: { all m/TopManager ( SubClassOf( ObjectPropertyDomain( domain: employee;

is_in(topManager, m) - topManager worksOn employee) range: project;

is_in(m.boss, m) ) ObjectHasSelf(boss) ) ObjectPropertyRange( };

worksOn project) Здесь all обозначает квантор всеобщности, знак / } – типизацию переменной типом, предикат is_in – { Employee;

in: type;

принадлежность элемента множеству, знак – – ло worksOn: {set;

DataProperty(salary) гическую импликацию.

type_of_element: Project;

};

DataPropertyDomain( Отображение ограничений на размер области и metaslot in: WorksOn;

end salary employee) класс значений свойств. Ниже приводится пример DataPropertyRange( инварианта класса (employee), утверждающий, что salary: integer;

salary xsd:integer) среди начальников (свойство boss) любого служа } SubClassOf(employee щего должен быть, по крайней мере, один топ DataExactCardinality ( менеджер. В OWL данная ситуация представляется 1 salary) ) конструкцией ObjectMinCardinality.

Отображение отношений между классами. От- СИНТЕЗ OWL ношение класс – подкласс в простых случаях (на- all e/Employee ( SubClassOf( Employee пример, manager – подкласс employee) представля- is_in(employee, e) - ObjectMinCardinality( ется в языке СИНТЕЗ в слоте superclass соответст- cardinal({m/Manager | 1 boss topManager) ) вующего подкласса. Более сложные отношения ме- is_in(e.boss, m) & жду классами (например, manager areaManager is_in(topManager, m)}) topManager) представляются инвариантами классов = 1 ) (managerCompleteness). В OWL отношения между Здесь функция cardinal вычисляет мощность мно классами представляются при помощи аксиом клас- жества.

сов. Отображение рефлексивных, иррефлексивных и СИНТЕЗ OWL асимметричных свойств. Для представления свойств специального вида в языке СИНТЕЗ опре { manager;

in: class;

SubClassOf( manager деляются соответствующие метаклассы ассоциаций.

superclass: employee;

employee) Так, для представления рефлексивных свойств оп instance_section: { ределяется метакласс ассоциаций reflexive:

managerCompleteness: { SubClassOf( manager in: invariant;

ObjectUnionOf( { reflexive;

in: association, metaclass;

{ manager = areaManager instance_section: { union(areaManager, topManager reflexivity: { in: invariant;

topManager) } ) all x ( (is_in(this.domain, x) - is_in(this, [x, x])) };

) & (is_in(this.range, x) - is_in(this, [x, x])) ) };

} }}} Отображение фактов. Факты (утверждения о Здесь this обозначает класс ассоциаций, принадле значениях свойств объектов) представляются в язы жащий метаклассу reflexive, domain обозначает об ке СИНТЕЗ константами объектных типов. В OWL ласть определения класса ассоциаций, range – об факты представляются утверждениями о существо ласть значения, [a, b] обозначает пару объектов, вании индивида (NamedIndividual), о принадлежно участвующих в ассоциации. Метакласс каждого сти индивида классу (ClassAssertion), о значениях рефлексивного свойства становится подклассом свойств (DataPropertyAssertion, ObjectPropertyAsser reflexive (например, SameSalary). В OWL рефлек tion) и т. д.

сивность отражается при помощи конструкции Re СИНТЕЗ OWL flexiveObjectProperty.

{ JohnJohnson;

NamedIndividual( СИНТЕЗ OWL in: employee;

JohnJohnson ) { SameSalary;

ReflexiveObjectProperty( salary: 3200;

ClassAssertion( in: association, metaclass;

sameSalary boss: JackJackson;

employee JohnJohnson) superclass: reflexive;

) } DataPropertyAssertion( } salary JohnJohnson 3200 ) Аналогично отображаются иррефлексивные и ObjectPropertyAssertion( асимметричные свойства.

boss JohnJohnson JackJackson ) Отображение непересекающихся свойств. Ниже значений встроенного типа данных;

для каж дого свойства dp выполнено (dp)DP I D;

рассмотрен пример инварианта класса (employee), • •I – функция интерпретации объектов;

для описывающего непересекающиеся свойства (hire Date и fireDate). В OWL непересекающиеся свойст- каждого объекта o выполнено (o)I I;

ва представляются конструкциями DisjointObject- • •DT – функция интерпретации встроенных ти Properties и DisjointDataProperties. пов данных;

для каждого типа dt выполнено СИНТЕЗ OWL (dt)DT D;

all e/Employee( DisjointDataProperties( • •LT – функция интерпретации литералов;

для is_in(employee, e) - hireDate fireDate каждого литерала l типа данных dt выполнено e.hireDate e.fireDate ) ) (l)LT (dt)DT.

Отображение иерархии композиций свойств. Интерпретация I удовлетворяет онтологии O Ниже рассмотрен пример композиции свойств (lo- (является моделью О), если все конструкции онто catedIn и partOf), являющейся подсвойством неко- логии удовлетворяют соответствующим условиям, торого свойства (locatedIn). Если город с находится приведенным в нижеследующих таблицах. Для уп в регионе r и регион r является частью региона s, то рощения приведены лишь конкретные конструкции, с находится в s. Иерархия композиций свойств вы- рассмотренные в примерах раздела 3.



Pages:     | 1 |   ...   | 6 | 7 || 9 | 10 |   ...   | 26 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.