«2 ТРУДЫ ИНФОРМАЦИОННЫЕ Кольского научного центра РАН ТЕХНОЛОГИИ 5/2013 (18) выпуск 4 СОДЕРЖАНИЕ Стр. Введение.. 9 В.А. Путилов Средства информационного мониторинга и А.В. Маслобоев моделирования глобальной безопасности ...»

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

Основная идея разработки ОВУ состоит в том, что если при рассмотрении понятийных систем различных предметных областей постепенно повышать уровень абстракции, то на определенном шаге останется лишь небольшой инвариантный по отношению к ним набор понятий [18]. Это обуславливается тем, что в каждой предметной области мы имеем дело, по сути, с различными разновидностями объектов, процессов, свойств, отношений, пространств, временных промежутков, ролей, функций и т.д. Таким образом, онтология верхнего уровня определяет понятийную систему наиболее общих понятий и отношений. Необходимо заметить, что она также задает возможный взгляд на реальность, из которого следуют определенные способы описания знаний о предметных областях. В этой связи можно использовать онтологии верхнего уровня в качестве источников правил компоновки КФ. Заметим также, что ОВУ обычно являются результатом работы групп специалистов в области лингвистики, когнитологии, философии, концептуального и семиотического моделирования. Из этого обстоятельства следует, что применение ОВУ в качестве основ при разработке онтологий предметных областей дает возможность представлять специфические понятия привычным для специалистов в различных областях знаний способом. Соответственно формулировка правил формирования КФ на основе результатов анализа подходов к представлению понятий в ОВУ, позволит гарантировать некоторую общепринятость таких правил и как следствие привычность КФ.

Формирование когнитивных фреймов Введем формальное представление понятия «Когнитивный фрейм» в следующем виде:

где СT является содержимым фрейма – некоторым фрагментом онтологии, VS – способ визуального представления содержимого.

Заметим, что в предыдущей работе [11] была представлена технология создания для OWL-онтологии ее упрощенной модификации – онтологии пользовательского представления (ОПП), направленной на непосредственную графическую визуализацию. В качестве основы ОПП используется модель SKOS [19], которая ориентирована на описание концептуальных схем, тезаурусов и семантических сетей. Язык SKOS проще, чем язык OWL и описанная с его помощью ОПП легко может быть визуализирована в виде графовой структуры. С учетом данного обстоятельства будем рассматривать содержимое КФ как некоторый фрагмент ОПП, то есть некоторый подграф, вершинами которого являются понятия, а дугами представлены отношения между ними.

При этом из множества понятий выделяется целевое понятие, смысл которого должен передать фрейм. В качестве способа визуализации на данном этапе исследования была выбрана графовая структура (node-link diagram).

Для определения алгоритмов формирования содержимого КФ введем понятие «n-окрестность понятия t по некоторому отношению R», которым будем обозначать множество понятий, связанных отношением R через n промежуточных понятий. Обозначим множество всех видов отношений в Тогда окрестность определяется индуктивно следующим образом:

где LRm (t ) - n-ая окрестность понятия t по отношению вида Rm, oj и ki – понятия онтологии.

Общий вид содержимого КФ обозначим следующим образом:

t – целевое понятие КФ, Z – множество отношений между понятиями КФ.

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

Далее рассмотрим общие элементы, используемые в существующих онтологиях верхнего уровня, таких как DOLCE [20], BFO [21], GFO [22], CYC [23], SUMO [24], и вопрос формирования КФ на их основе. На данном этапе исследования были рассмотрены следующие общие отношения онтологий верхнего уровня:

- наследование указывает на то, что некоторое понятие (субконцепт) является разновидностью другого (суперконцепта). В таком случае субконцепт наследует отношения его суперконцепта;

- меронимия – отношение между понятием, обозначающим целое, и понятиями, обозначающими части этого целого;

- зависимость указывает на то, что существование одного понятия зависит от существования другого.

Большинство других отношений в онтологиях предметных областей можно рассматривать как разновидности представленных. Формирование содержимого КФ на основе общих отношений между понятиями позволит разбить визуальную информацию по принадлежности к различным ракурсам рассмотрения понятий и, тем самым, позволит избавить пользователя от дополнительных ментальных операций. «Общепринятость» отношений, в свою очередь, позволит гарантировать представление в рамках КФ знакомой пользователю точки зрение на понятие.

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

';

Шаг 2. Если | En Lnh 1 (t ) | LM, где LM - предельное количество элементов во фрейме, то En1 En Ln1 (t ), завершается, иначе n n 1 и переходим к шагу 2.

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

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

Следующим важным отношением, используемым при описании понятий различных предметных областей, является отношение партономии или отношение «часть - целое». Однако в отличие от отношения наследования ответ на вопрос о формировании содержимого КФ, соответствующего партономии не столь очевиден. Это связанно с наличием разновидностей партономических отношений [26], таких как: функциональная часть – цельный объект (педальвелосипед), элемент - коллекция (корабль - флот), порция - масса (кусок глины глина), материал - объект (сталь - машина), этап - процесс (сдача экзаменовобучение), место - территория (Красная площадь - Москва).

В ряде случаев это может приводить к парадоксам транзитивности.

Примером может быть такой вывод: если «Концерт имеет - часть Дирижер», «Дирижер имеет - часть Рука», то «Концерт имеет - часть Рука». Разумеется, что наличие таких парадоксов КФ негативно отразиться на его понимании.

Для решения данной проблемы можно предложить несколько правил установления транзитивности:

1. Учитывать транзитивность лишь по одной разновидности партономических отношений;

2. Рассматривать транзитивность партономии только между объектами имеющими одного предка [27];

3. Учитывать транзитивность лишь между базовыми разновидностями партономических отношений [28], такими как «функциональная часть – цельный объект», «порция - масса», «этап - процесс», «место - территория».

С учетом того обстоятельства, что как правило в онтологиях разновидности партономии явно не представлены, наиболее целесообразным с точки зрения универсальности применения является правило 2. Это предполагает добавление дополнительного условия при внесении понятий-частей в содержимое КФ на 2 шаге алгоритма его компоновки. Оно будет заключаться в требовании наличия некоторого одинакового числа супер-классов у целевого и добавляемого понятия. Количество одинаковых супер-классов определяется в зависимости от верхней части иерархии классов конкретной онтологии или выбранной в качестве ее основы онтологии верхнего уровня. Например, в случае использования онтологии верхнего уровня BFO это число будет не менее 4, в этом случае получится избежать установления ошибочной транзитивности партономии между понятиями «Continuant» и «Occurrent», а также их подклассами.

Таким образом, алгоритм формирования КФ по отношению партономии будет иметь вид:

супер-понятий для t и oi, LC – требуемое число одинаковых супер-понятий, то иначе En1 En.

Шаг 3. Если En1 En, то O En1, Z Qn1 и работа алгоритма завершается, иначе n n 1 и переходим к шагу 2.

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

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

В основном в онтологиях верхнего уровня представлены следующие виды зависимости:

общая (generic) и специфическая/жесткая (specific/rigid) зависимость.

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

Специфическая указывает на зависимость от существования конкретного экземпляра класса (зависимость существования человека от его мозга);

концептуальная зависимость [29, 30] зависимость определенного качества от сущности, которая его несет. Например, качество «иметь цвет»

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

постоянная (сonstant) и временная (temporal) зависимость. Постоянная зависимость проявляется постоянно между сущностями, а временная указывает на необходимость существования одной сущности перед появлением другой;

внешняя зависимость [31] противопоставляется внутренней, определяет зависимость от внешних, то есть не являющихся частями или качествами, сущностей.

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

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

Поэтому правило единого предка здесь не подходит.

Обозначим D {R1,...Rn } H множество всех видов отношений зависимости в онтологии. В этом случае в алгоритме компоновки КФ, соответствующего данному отношению, на 1-м шаге включаются понятия, связанные любым видом отношений зависимости с целевым непосредственно.

На 2-м шаге добавляются их понятия-соседи, связанные с ними тем же типом отношений зависимости.

Формально можно представить алгоритм следующим образом:

иначе En1 En.

завершается, иначе n n 1 и переходим к шагу 2.

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

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

Рис. 2. Анализ и представление сложных OWL-аксиом в ОПП Таким образом, можно рассматривать OWL-аксиому как совокупность понятий-субаксиом, связанных с целевым отношением «related». Их визуализация будет осуществляться в рамках специальных КФ. Помимо понятийсубаксиом, в специальные КФ будут включаться понятия, связанные с целевым отношениями, не отнесенные к рассмотренным ранее общим типам. При этом во избежание «перегрузки» КФ на первом шаге будут включены понятия-соседи только целевого понятия, а не наследованные от супер-понятий. Последние будут добавлены на следующих шагах, если это возможно. То есть на каждом шаге будет рассматриваться супер-понятие более высокого уровня иерархии.

Формально алгоритм формирования содержимого специального фрейма имеет следующий вид:

отношений с понятием-субаксиомой SR H, тий-субаксиом, связанных с целевым опосредованно, J P(t ) \ P(uk ), P(t ) - множество понятий, связанных c поняuk SC( t ) тием t специфическими отношениями, SC(t) – множество супер-понятий для t, где LM - предельное количество элементов во фрейме, bn – супер-понятие целевого t с n-го ближайшего уровня иерархии, то En1 En J n1, Шаг 3. Если En1 En, то O En1 и Z Qn1 работа алгоритма завершается, иначе n n 1 и переходим к шагу 2.

Заключение В данной работе рассмотрена проблема визуализации OWL-онтологий для облегчения понимания пользователем представленных в ней знаний о предметной области. Для решения данной задачи предлагается выделять в онтологии фрагменты и визуализировать их в рамках специальных структур – когнитивных фреймов. Формирование данных структур осуществляется с помощью алгоритмов, принимающих во внимание межпонятийные отношения, определенные в онтологиях верхнего уровня, а потому инвариантные к предметным областям и, так или иначе, присутствующие в большинстве прикладных онтологий. Это позволяет задавать КФ, отражающие типовые точки зрения на понятия, и тем самым обеспечивать их привычность для пользователя.

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

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

Литература 1. Bernardo C., Ian H., Boris M., Parsia B., Peter F. P., Sattler U. OWL 2: The next step for OWL. J. Web Sem. 6(4), 2008. –Р.309-322.

2. Horridge M., Drummond N., Goodwin J., Rector A., Stevens R., Wang H. The Manchester OWL Syntax // Proceeding of the 2006 OWL Experiences and Directions Workshop (OWLED), V.216, Athens, 2006.

3. Bergh J.R., Ontology comprehension /University of Stellenbosch, Master Thesis, 2010.

4. Bauer J. Model exploration to support understanding of ontologies // Master’s thesis, Technische Universitt Dresden, 2009.

5. Ellson J., Gansner E.R., Koutsofios L., North S., Woodhull G. Graphviz. Open source graph drawing tools proceedings // Graph Drawing. – 2002. – P.483-484.

6. Katifori А., Halatsis C., Lepouras G., Vassilakis C., Giannopoulou E. // Ontology visua-lization methods – A survey. ACM computing surveys, 39(4):10, 2007.

7. H. Alani TGVizTab: An Ontology Visualisation Extension for Protege, Knowledge Capture 03 - Workshop on Visualizing Information in Knowledge Engineering Sanibel Island, FL: ACM, 2003. – P.2-7.

8. Bosca D. Bonino P. Pellegrino. OntoSphere: More than a 3D ontology visualization tool. In SWAP, the 2nd Italian semantic web workshop, 2005.

9. Averbukh V.L. Toward formal de_nition of conception adequacy in visualization// Proc. 1997 IEEE Symp. on Visual Languages, Sept. 23-26, 1997. Isle of Capri,Italy. S. l.: IEEE Comput. Soc, 1997. -P.46-47.

10. Валькман, Ю.Р. Когнитивные графические метафоры: когда, зачем, почему и как мы их используем / Ю.Р. Валькман // Знания–Диалог–Решение (KDS– 95): труды Междунар. конференции, г. Ялта, 1995. -С.261–272.

11. Ломов, П.А., Преобразование OWL-онтологии для визуализации и использования в качестве основы пользовательского интерфейса / П.А. Ломов, М.Г. Шишаев, В.В. Диковицкий // Онтология проектирования. – Самара:

Новая техника, 2012. - №3. -C.49-61. ISSN 2223- 12. Минский, М. Фреймы для представления знаний /М. Минский: Пер с англ./ под ред. Ф.М. Кулакова. – М.: Энергия, 1979. – 151 с.

13. Miller G.A. «The magical number seven, plus or minus two: Some limits on our capacity for processing information». Psychological Review 63 (2), 1956.

14. Зюбин, В.Е. Графические и текстовые формы спецификации сложных управляющих алгоритмов: непримиримая оппозиция или кооперация? / В.Е. Зюбин // сб. тр. VII Междунар. конференции по электронным публикациям "EL-Pub2003". - Новосибирск, Академгородок, 2003. -C.8-10.

15. Болдырев, Н.Н. Когнитивная семантика: Курс лекций по английской филологии / Н.Н. Болдырев. -Тамбов: Изд-во Тамбовского унив., 2000. -123 с.

16. Johnson-Laird P.N. Mental Models: Towards a cognitive science of language, inference and consciousness / Cambridge, VA: Harvard Univ.Press, 1983.–246 p.

17. Психология общения. Энциклопедический словарь /под общ. ред. А.А.

Бодалева. – М.: Изд-во «Когито-Центр», 2011. -600 c.

18. Hoehndorf R. What is an upper level ontology?

- Режим доступа: http://ontogenesis.knowledgeblog.org/ 19. Jupp S., Bechhofer S., Stevens R. SKOS with OWL: Don't be Full-ish! // In proceeding of the Fifth OWLED Workshop on OWL: Experiences and Directions, Karlsruhe, Germany, October 26-27, 2008. – Режим доступа:

http://www.webont.org/owled/2008/papers/owled2008eu_submission_22.pdf 20. Masolo C., Borgo S., Gangemi A., Guarino N., Oltramari A., Shneider L.

WonderWeb. Final Report // Deliverable D18, 2003.

21. Grenon P. Spatio-temporality in Basic Formal Ontology: SNAP and SPAN, Upper-Level Ontology, and Framework for Formalization: Part I. IFOMIS Report 05/2003 // Institute for Formal Ontology and Medical Information Science (IFOMIS), University of Leipzig, Leipzig, Germany, 2003.

22. Herre H. General Formal Ontology (GFO): A Foundational Ontology for Conceptual Modelling // In Theory and Applications of Ontology: Computer Applications, 2010. -P.297-345.

23. Cyc Ontology Guide: Introduction. –Режим доступа: http://www.cyc.com/cyc-2intro-public.html.

24. Niles I., Pease A. Towards a Standard Upper Ontology. In Welty, C., Smith, B.

(eds.) Proceedings of the 2nd International Conference on Formal Ontology in Information Systems (FOIS-2001) / Ogunquit, Maine, October 17-19, 2001.

25. Gerstl P., Pribennow S. A conceptual theory of part-whole relations and its applications / Data and Knowledge Engineering, 1996. -V.20. -P.305-322.

26. Cruse D. Lexical Semantics. Cambridge: University Press, 1986.

27. Motschnig-Pitrik, R., Kaasboll, J.: Part-Whole Relationship Categories and their Application in Object-Oriented Analysis / IEEE TSE, 1999. -V.11(5)/-P.779-797.

28. Masolo C., Borgo S., Gangemi A., Guarino N., Oltramari A., Shneider L.

/WonderWeb. Final Report. Deliverable D18, 2003.

29. Gangemi A., Navigli R., Velardi P. The OntoWordNet project: extension and axiomatisation of conceptual relations in wordnet /International Conference on On-tologies, Databases and Applications of Semantics (ODBASE), Catania (Italy), 2003.

30. Guarino N., Welty C. A Formal Ontology of Properties. In Knowledge Engineering and Knowledge Management: Methods, Models and Tools / 12th International Conference, EKAW 2000, Springer Verlag, 2000. –Р.97-112.

Сведения об авторах Шишаев Максим Геннадьевич – д.т.н., заведующий лабораторией, е-mail: [email protected] Maksim G. Shishaev - Dr. of Sci (Tech), Head of laboratory Ломов Павел Андреевич – к.т.н., научный сотрудник, е-mail: [email protected] Pavel A. Lomov – Ph.D. (Tech. Sci.), Researcher УДК 004. М.Г. Шишаев, П.А. Ломов, В.В. Диковицкий ФГБУН Институт информатики и математического моделирования технологических процессов

КНЦ РАН

Кольский филиал ПетрГУ

ФОРМАЛИЗАЦИЯ ЗАДАЧИ ПОСТРОЕНИЯ КОГНИТИВНЫХ

ПОЛЬЗОВАТЕЛЬСКИХ ИНТЕРФЕЙСОВ МУЛЬТИПРЕДМЕТНЫХ

ИНФОРМАЦИОННЫХ РЕСУРСОВ

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

Ключевые слова:

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

FORMALIZATION PROBLEM OF CONSTRUCTING COGNITIVE USER

INTERFACES FOR MULTIDOMAIN INFORMATION RESOURCES

Abstract The paper considers the formulation of the problem of constructing cognitive interfaces multidomain information systems. The estimation of the quality of the interface, based on according semantic structure navigation links and mental model Key words:

оntology, user interface, multidomain resources.

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

Примерами мультипредметных информационных ресурсов являются новостные сайты, а также ресурсы, предоставляющие справочную информацию Работа выполнена в рамках проекта №2.8 программы фундаментальных исследований ОНИТ РАН «Интеллектуальные информационные технологии, системный анализ и автоматизация», при поддержке РФФИ (грант № 13-07-01016 «Методы динамического синтеза когнитивных интерфейсов мультипредметных информационных систем»).

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

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

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

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

Модель ресурса и категории пользователей Будем понимать под ресурсом коллекцию документов, содержимое которых (контент) оперирует в смысле синтаксиса языка документа некоторым множеством понятий, складывающихся тем или иным образом в логическую систему. Логическая система образуется заданием на данном множестве понятий C различных семантических связей L, определяющих допустимые с точки зрения создателя документа способы взаимной интерпретации понятий из С:

где C - множество понятий (концептов), L - множество отношений над понятиями.

Подобную систему в современной ИТ-науке принято называть онтологией [1]. Назовем систему, описывающую контент информационного ресурса онтологией ресурса. Обратим внимание, что отношения на множестве понятий онтологии могут быть как симметричными, так и асимметричными. Наиболее распространенным примером симметричного отношения является отношение ассоциации. Например, в онтологии могут быть определены понятия «регион» и «административно-территориальная единица», связанные данным отношением.

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

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

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

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

Например, в ментальной модели человека категории «управленец» экземпляр понятия «Регион РФ (область, край, республика)» будет идентифицироваться значениями атрибутов, характеризующих структуру экономики и политическую ситуацию на территории. В то же время для пользователя категории «турист»

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

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

атрибуты для категории Рис. 1. Идентифицирующие атрибуты понятия «Мурманская область»

Пусть C- некоторое множество понятий, U – множество пользователей.

Множество атрибутов концепта с будем обозначать следующим образом:

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

где u - отношение, задающее значимость атрибутов для пользователя u; a u b означает, что «для пользователя u a не менее значим, чем b».

Также можно определить группу пользователей, имеющих схожие представления о понятиях из некоторого множества C. Назовем подобную группу пользовательской категорией k-го порядка на множестве концептов С и определим ее следующим образом:

То есть, для всех пользователей из категории U C совпадают k наиболее значимых (идентифицирующих) атрибутов для всех концептов из множества C.

В более мягкой форме (без требования совпадения порядка атрибутов по значимости) это условие выглядит следующим образом:

Можно заметить, что при k const пользовательские категории, сформированные в соответствии с условием (1) или (2), образуют разбиение исходного множества пользователей на непересекающиеся подмножества:

Несмотря на схожесть формулировок условий (1) и (2), их свойства существенно отличаются. Так, в случае использования условия (1) размер пользовательских категорий для некоторого фиксированного концепта с будет невозрастающей функцией от k с нижней гранью равной 1 и областью значений [1, U ]. В то же время, для условия (2) размер категорий может свободно изменяться в пределах от 1 до U и достигать максимума, равного U, при Модель навигационного интерфейса Пользовательский интерфейс ресурса имеет две основных составляющих – это внешнее оформление (дизайн) и навигационная структура. Если качество первого компонента является исключительно субъективной категорией и вряд ли может быть оценено формально, то для оценки качества навигационной структуры ресурса можно использовать степень ее соответствия ментальной модели пользователя. При этом должна рассматриваться семантика навигационной структуры (семантическая структура интерфейса). Чем более схожими являются семантическая структура интерфейса и ментальная модель пользователя, тем более удобным и понятным для конечного пользователя будет интерфейс. Последний в этом случае будет способен «предугадывать» образ мыслей пользователя и визуализировать фрагмент понятийной системы ожидаемым для него способом. Будем далее именовать меру соответствия семантической структуры интерфейса ментальной модели пользователя когнитивностью интерфейса. Далее рассматривается формализованное описание навигационной структуры и основанная на нем количественная оценка когнитивности пользовательского интерфейса.

Итак, пользовательский интерфейс представляет собой пару:

где I – множество информационных элементов; s – навигационная структура.

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

l {Gil } - множество разделов l-го уровня навигационной структуры;

Gil - i-я группа информационных элементов l-го уровня навигационной структуры;

P l { pil } - множество классификационных признаков, используемых для формирования групп ИЭ на l-м уровне навигационной структуры.

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

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

Сделаем следующее предположение: если для формирования навигационной структуры на некотором уровне иерархии используются идентифицирующие атрибуты, то пользователь с высокой долей уверенности сможет определить, в какой группе находится искомый информационный элемент. Обозначим через wu (a) [0,1] нормированный вес атрибута а в ментальной модели пользователя u. Тогда, с учетом указанного предположения:

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

Поскольку при таком определении значение функции p u (Gil ) не зависит от группирования информационных элементов как такового, а зависит лишь от уровня навигационной структуры, будем далее использовать редуцированную запись p u (l ).

Пусть навигационная структура интерфейса имеет глубину l уровней.

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

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

С учетом сказанного, оптимальная для пользователя u структура интерфейса есть решение следующей задачи с ограничениями:

здесь l( s ) - количество уровней в навигационной структуре s; g (s) - максимальный размер группы информационных элементов l( s ) -го в навигационной структуре s; K – когнитивная константа, определяющая максимальное число одновременно предъявляемых пользователю информационных элементов для их эффективного восприятия; K’ – когнитивная константа, определяющая максимальное число уровней навигационной структуры, в рамках которых поиск информации для пользователя остается комфортным.

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

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

Литература 1. Онтологии в системах искусственного интеллекта: способы построения и организации / А.В. Смирнов и др. // Новости искусственного интеллекта.

-2002. - Ч.1. -№1. -С.3–13.

2. Koffka, K. Principles of Gestalt psychology /К. Koffka. -New-York., Routledge, 1935. - 720 p.

3. Салвенди, Г. Человеческий фактор /Г. Салвенди. - М: Мир, 1991.

ISBN 5-03-001710-0.

4. Ковалёв, С.С., Шишаев, М.Г. Современные методы кластеризации в контексте задачи идентификации рассылок почтового спама /С.С. Ковалев, М.Г. Шишаев / Труды Кольского научного центра РАН. Информационные технологии. - Апатиты: Изд-во КНЦ РАН. –4/2012(11). – Вып.3. -С.89-99.

Сведения об авторах Шишаев Максим Геннадьевич – д.т.н., заведующий лабораторией, е-mail: [email protected] Maksim G. Shishaev – Dr. of Sci (Tech), Head of laboratory Ломов Павел Андреевич – к.т.н., научный сотрудник, е-mail: [email protected] Pavel A. Lomov – Ph.D. (Tech. Sci.), Researcher Диковицкий Владимир Витальевич – младший научный сотрудник, е-mail: [email protected] Vladimir V. Dikovitsky – Junior researcher УДК 004.7, 004. П.А. Коробейников, М.Г. Шишаев ФГБУН Институт информатики и математического моделирования технологических процессов

КНЦ РАН

ИССЛЕДОВАНИЕ СЕМАНТИЧЕСКОЙ СТРУКТУРЫ НАВИГАЦИОННЫХ

ИНТЕРФЕЙСОВ ТИПОВЫХ ВЕБ-РЕСУРСОВ

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

Ключевые слова:

семантическая связь, веб-ресурс, навигационный интерфейс.

P.A. Korobeynikov, M.G. Shishaev

STUDY OF SEMANTIC STRUCTURE OF REFERENCE INTERFACE FOR TYPICAL

WEB RESOURCES

Abstract The article presents the results of a study of the semantic structure of a reference interface for typical web resources. It is shown that the reference interface for resources of various thematic categories is based on semantic relations of one or two dominant types. It is concluded that development of technology for automated generation of reference interfaces adapted to the mental models of users has good Key words:

semantic link, web-resource, reference interface.

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

Привычным способом структуризации знаний для человека является построение разного рода классификаций, основанных на том или ином признаке, и организующих информацию в иерархическую или подобную структуру. Понимание Работа выполнена в рамках проекта №2.8 программы фундаментальных исследований ОНИТ РАН «Интеллектуальные информационные технологии, системный анализ и автоматизация», при поддержке РФФИ (грант № 13-07-01016 «Методы динамического синтеза когнитивных интерфейсов мультипредметных информационных систем»).

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

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

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

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

Active relation. Семантическое отношение между двумя понятиями, одно из которых выражает выполнение действия, затрагивающего другое понятие;

Associative relation. Отношение, которое определяется психологически. Пример: понятие A ментально связано с понятием B. Часто, ассоциативные связи – это просто неклассифицированные отношения;

“Instance of” relation. Отношение определяет семантическую связь между общим понятием и отдельными случаями общего понятия. Пример:

Москва – случай (instance) общего понятия “столица”;

Locative relation. Семантическое отношение, в котором понятие указывает на местоположение объекта, определяемого другим понятием;

“Part of” relation. Является меронимией, то есть отношением между целым и его частями.

Следующие три семантические связи являются частными случаями отношения “гипоним - гипероним” (иерархическая зависимость):

“Kind of” relation. Пример: А – вид B;

“Narrower than” relation. Пример: понятие A более узкое, чем понятие B;

“Broader than” relation. Пример: понятие A шире понятия B.

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

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

Количества семантических связей в навигационной структуре веб-ресурсов Ресурс/ Тип связи Яндекс.Новости:

http://news.yandex.ru/ NEWSru.com:

http://newsru.com/ Новости@Mail.Ru:

http://news.mail.ru/ Авто@Mail.Ru:

http://auto.mail.ru/ Авторамблер:

http://autorambler.ru/ СПОРТ-ЭКСПРЕСС:

http://www.sport-express.ru/ Советский Спорт:

http://www.sovsport.ru/ Чемпионат.com:

com/ Sports.ru:http://www.sports.

Мурманский ГТУ:

http://www.mstu.edu.ru/ КФ ПетрГУ:

http://www.arcticsu.ru/ Сбербанк России:

http://sberbank.ru/ РОСНЕФТЬ:

http://www.rosneft.ru/ ОАО НОВАТЭК:

http://www.novatek.ru/ ОАО "Ростелеком":

http://www.rostelecom.ru/ Процентное распределение количества связей по типам в каждой из пяти тематических категорий веб-ресурсов изображено на рис. 1.

Рис. 1. Диаграмма распределения типов семантических связей Доля каждой семантической связи в навигационной структуре веб-ресурсов различных тематических категорий представлена на рис. 2.

В результате исследования подтвердилось предположение о том, что в навигационной структуре ресурсов разных категорий имеет место доминирование семантических связей одного-двух типов. Причем для разных категорий веб-ресурсов доминирующие связи различны. Так, для новостных ресурсов доминируют связи типа “is part of” и “is kind of”, для ресурсов автомобильной тематики преобладают “is kind of” и ассоциативные связи, для спортивных ресурсов доминирующими оказались связи “is part of” и ассоциативные. В структуре корпоративных ресурсов и ресурсов образовательных учреждений преобладают ассоциативные связи.

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

Рис. 2. Доля каждого типа связей в веб-ресурсах исследуемых Для новостных ресурсов это концепты соответствующие связям “is kind of”, которые обозначают новостные разделы ресурса, например, «политика», «экономика», «технологии» и т.д. На ресурсах автомобильной тематики разделы определяются понятиями соответствующими наименованию производителя автомобилей, например, «BMW», «Ford», «ВАЗ», и т.д. Разделам спортивной тематики соответствуют концепты определяющие виды спорта, такие как «футбол», «хоккей», «баскетбол» и т.д. Ресурсы образо-вательных учреждений имеют следующие типичные разделы: «Новости», «Информация о ВУЗе», «Абитуриенту», «Сотруднику», «Учебная деятельность», «Факультеты (Структура)», «Наука», «Контактная информация». На корпоративных ресурсах наблюдается существенно меньшее количество типо-вых разделов: «О компании», «Инвесторам и акционерам», «Пресс-центр», «Работа в компании».

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

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

Сведения об авторах Шишаев Максим Геннадьевич – д.т.н., заведующий лабораторией, е-mail: [email protected] Maksim G. Shishaev - Dr. of Sci (Tech), Head of laboratory Коробейников Павел Александрович – аспирант е-mail: [email protected] Pavel A. Korobeynikov – Post-graduate УДК 004. А.А. Рыженко, Р.Ш. Хабибулин Академия Государственной противопожарной службы МЧС России, г. Москва

РАСПРЕДЕЛЕННАЯ СИСТЕМА ИНДИВИДУАЛЬНОГО ОПОВЕЩЕНИЯ

В СЛУЧАЕ ЧС НА КРУПНЫХ ПРОМЫШЛЕННЫХ ПЛОЩАДКАХ

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

Ключевые слова:

модель, информационная система, система оповещения.

A.A. Ryzhenko, R.Sh. Khabibulin

DISTRIBUTED SYSTEM OF INDIVIDUAL NOTIFICATION IN CASE OF

EMERGENCY SITUATIONS AT THE LARGE INDUSTRIAL SITES

Abstract The article presents the model and the version of the interface of distributed information system of general and individual alerts for example, stationary and mobile objects at the large industrial sites.

Key words:

model, the information system, the system alerts.

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

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

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

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

В идеале основным каналом диспетчерской системы на площадках должна являться сеть промышленного Ethernet (Industrial Ethernet) на базе волоконно-оптического кабеля. В этом случае радиосеть служит полноценным резервным каналом, на который в случае нештатной ситуации должны переключаться все пользователи – как «подземные» контроллеры, так и абоненты. Сеть обеспечивает стационарную и мобильную телефонную связь. В качестве мобильных абонентских устройств могут применяться телефоны Wi-Fi, телефоны GSM с Wi-Fi модулями и т. д. Для оснащения телефонной связью транспортных машин применяются стационарные абонентские устройства, дополнительно оснащенные адаптерами сети Wi-Fi (рис. 1).

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

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

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

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

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

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

голосовая связь через проводные и беспроводные телефоны;

громкоговорящее оповещение через громкоговорители и беспроводные телефоны;

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

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

Голосовая связь обеспечивается с проводных телефонов и с радиотелефонов технологии DECT. Оповещение осуществляется через подсистему громкоговорящей связи и через радиотелефоны технологии DECT в режиме громкой связи.

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

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

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

Архитектура реализуемого проектного решения В настоящее время, в связи с разработкой и широким внедрением поддержки качества обслуживания QoS, протокола передачи трафика реального времени (RTP, cRTP) в сетях связи на базе протокола IP, а также протоколов управления мультисервисным (голос/видео/данные) трафиком, таких как, H.323, SIP, MGCP и др., появилась возможность создания интегрированных мультисервисных корпоративных сетей связи предприятия.

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

Рис. 3. Диаграмма кооперации элементов вычислительной сети ИТС включает сетевое оборудование – маршуртизаторы и коммутаторы IP c поддержкой качества обслуживания и передачи трафика реального времени, каналообразующее оборудование; ИТС обеспечивает передачу и доведение до пользователя всех мультисервисных услуг.

Рис. 4. Диаграмма кооперации в процессе мониторинга состояния Программная составляющая, примеры интерфейса В качестве заключения приводится пример интерфейса разрабатываемого приложения. Система представляет распределенное приложение с гибким интерфейсом. Ведется хранение данных на базе сервера MS SQL.

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

Рис. 5. Пример интерфейса «Режим создания схем телефонной сети»

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

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

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

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

Литература 1. Топольский, Н.Г. Модель автоматизированной системы пожарной безопасности промышленного объекта с термоэлектрозондированием электрооборудования и линейно-кабельных сооружений / Н.Г. Топольский, В.В. Белозеров, Нгуен Туан Ань // Технологии техносферной безопасности: интернет-журнал. – 2011. – Вып. №2 (36). – 6 с.

– Режим доступа: http://ipb.mos.ru/ttb Сведения об авторах Рыженко Алексей Алексеевич – к.т.н., научный сотрудник, е-mail: [email protected] Alexey A. Ryzhenko – Ph.D. (Tech. Sci.), Senior researcher Хабибулин Ренат Шамильевич - к.т.н., доцент, заведующий департамента по информационным технологиям, е-mail: [email protected] Renat Sh. Khabibulin - Ph.D. (Tech. Sci.), Associate professor, Head of department of IT УДК 004. А.А. Зуенко ФГБУН Институт информатики и математического моделирования технологических процессов

КНЦ РАН

Кольский филиал ПетрГУ

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

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

Ключевые слова:

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

A.A. Zuenko

ACCELERATED ALGORITHMS OF LOGICAL INFERENCE ON CONSTRAINTS

Abstract In the paper we propose a method of acceleration algorithms applied to solving constraint satisfaction problems. A lot of these problems could be reduced to finding of satisfying substitutions for a finite predicate. The method is based on the orthogonalization of the disjunctive normal form of finite predicate and uses heuristics Keywords:

n-tuple algebra, logical-semantic analysis, constraints рrogramming, сonstraint satisfaction Введение В современном программировании можно выделить несколько основных парадигм: императивное или алгоритмическое программирование, логическое программирование, функциональное программирование и др. Важное место в этом ряду занимает программирование в ограничениях (constraint programming) [1].

Программирование в ограничениях как самостоятельное научное направление сложилось в конце 60-х – начале 70-х годов прошлого века.

Примечательно, что первыми приложениями были задачи обработки изображений и параметрического моделирования пространственно-двумерных сцен. С тех пор направление существенно эволюционировало, охватывая новые классы задач, начиная от решения судоку и ребусов и заканчивая решением Работа выполнена при финансовой поддержке РФФИ (проекты №№ 11-08-00641, 12-07-00550-а, 12-07-00689-а, 13-07-00318-а), ОНИТ РАН (проект 2.3 в рамках текущей Программы фундаментальных научных исследований) и Президиума РАН (проект 4. Программы № 16).

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

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

Для ускорения вычислительных процедур могут быть использованы различные методы, в частности эвристические. В данной работе рассмотрен алгоритм ортогонализации, помогающей снизить трудоемкость алгоритмов логического анализа. Был использован математический аппарат – алгебра кортежей (АК), который относится к классу булевых алгебр [3, 4] и позволяет реализовать алгебраический подход к логическому анализу в системах искусственного интеллекта [5, 6, 7, 8].

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

Задача удовлетворения ограничений (сonstraint satisfaction problem, CSP) может быть определена множеством переменных X1, X2,…, Xn и множеством ограничений С1, С2, …, Cm [1]. Каждая переменная Xi имеет непустую область определения Di. Каждое ограничение Сi затрагивает некоторое подмножество переменных и задает допустимые комбинации значений для этого подмножества. Решением задачи CSP называется такое присваивание значений всем переменным {X1=v1, …, Xn=vn }, которое удовлетворяет всем ограничениям.

Многие задачи CSP характеризуются тем, что в них используются переменные, которые являются дискретными и имеют конечные области определения. К числу таких задач относится задача раскраски карты (раскраски графа). Также к категории задач с конечными областями относятся булевы задачи CSP, в которых переменные принимать значения либо истина, либо ложь.

Булевы задачи включают в качестве частных случаев некоторые NP-полные задачи, такие как 3SAT [1].

Часто CSP решаются с помощью графов ограничений [1]. В настоящей работе рассматривается применение матрицеподобных вычислений в тех задачах программирования ограничений, где переменные дискретны и определены на конечных множествах значений (конечных доменах). По сути, решение CSP в этом случае сводится к определению множества выполняющих подстановок конъюнктивной нормальной формы (КНФ), но не булевой функции, а конечного предиката. Матрицеподобное представление таких КНФ и специализированные методы ускорения вычислительных процедур [3, 4] позволяют на практике получать требуемые решения за приемлемое время.

В АК конечные предикаты можно сжато представить с помощью двух типов структур: C-систем и D-систем. Они формируются в виде матриц из подмножеств доменов атрибутов, называемых компонентами. В их число входят две фиктивные компоненты: полная компонента (обозначается «») – это множество, равное домену соответствующего (по месту ее расположения в кортеже) атрибута; пустое множество –. В виде D-систем удобно КНФ конечных предикатов, а в виде С-систем – их дизъюнктивные нормальные формы (ДНФ). В АК процесс поиска выполняющих подстановок некоторой КНФ сводится к преобразованию D-систем в C-системы.

Преобразование АК-объектов в альтернативные классы Алгоритм преобразования D-системы в C-систему является комбинаторным по вычислительной сложности.

Утверждение 1. Каждый C-кортеж (D-кортеж) P преобразуется в эквивалентную ему диагональную D-систему (C-систему).

Алгоритмы преобразования C-кортежей и D-кортежей в альтернативные классы не требуют для своей реализации алгоритмов экспоненциальной сложности. Трудоемкость алгоритмов существенно возрастает при преобразовании в альтернативные классы C-систем и D-систем.

Утверждение 2. D-система P, содержащая m D-кортежей, эквивалентна C-системе, которая равна пересечению m C-систем, полученных с помощью преобразования каждого D-кортежа из P в C-систему.

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

Утверждение 3. C-система P, содержащая m C-кортежей, эквивалентна D-системе, которая равна объединению m D-систем, полученных с помощью преобразования каждого C-кортежа из P в D-систему.

в C-систему. Преобразуя каждый D-кортеж в C-систему, получим промежуточный результат:

Вычислим пересечение первых двух C-систем (получающиеся при этом пустые C-кортежи, которые затем удаляются из C-системы, здесь и далее для экономии места не показаны):

Теперь найдем пересечение полученной C-системы с оставшейся:

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

Ортогонализация При анализе определенных C-систем можно увидеть, что некоторые пары содержащихся в них C-кортежей имеют непустое пересечение. Иногда это сильно усложняет расчеты. Например, возможны ситуации, когда требуется вычислить общее число элементарных кортежей, содержащихся в таких C-системах – приходиться учитывать все возможные пересечения пар, троек и так далее C-кортежей. Те же трудности возникают, если исследуются метрические свойства АК-объектов, например, их вероятностное представление.

Ортого-нализация как раз и предназначена для преодоления этих трудностей.

Кроме того, ортогонализация дает эффективные средства уменьшения трудоемкости алгоритмов преобразования АК-объектов в альтернативные классы, и, в частности, D-систем в C-системы.

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

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

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

Дизъюнкция H1 H2... Hk эквивалентна ортогональной ДНФ вида C-система называется ортогональной, если пересечение любой пары содержащихся в ней различных C-кортежей равно пустому C-кортежу.

Утверждение 4. D-кортеж вида ]Q1 Q2... Qm-1 Qm[, где Qi – произвольные компоненты, преобразуется в эквивалентную ему ортогональную C-систему:

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

Рассмотрим пример. Пусть в схеме отношений [XYZ], где X = Y = Z = {a,b,c,d}, задан D-кортеж ]{a,c} {d} {b,d}[. Тогда при преобразовании его в ортогональную C-систему получим следующие равенства:

причем вторая C-система ортогональна.

Утверждение 5. Ортогонализация произвольных АК-объектов сводится к ортогонализации эквивалентных им D-систем (преобразованию D-систем в ортогональные C-системы). Для этого требуется:

1) выразить исходный АК-объект как D-систему;

2) представить D-систему как пересечение D-кортежей;

3) каждый D-кортеж преобразовать в ортогональную C-систему;

4) выполнить пересечение промежуточных ортогональных C-систем.

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

Рассмотрим пример ортогонализации для D-системы:

При преобразовании D-кортежей в эквивалентные им ортогональные С-системы получим:

Вычислим промежуточные результаты (пустые С-кортежи не показаны):

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

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

Если в промежуточном АК-объекте переставить местами C-кортежи, то эквивалентность не нарушится, но при ортогонализации после перестановки будет получено другое изображение того же D-кортежа. В итоге для D-кортежа ]A B C[формируется совокупность следующих равенств:

Таким образом, если задан D-кортеж, в котором содержится k непустых компонент, то алгоритм, описывающий получение из этого D-кортежа всех возможных эквивалентных ему ортогональных C-систем, состоит из трех шагов:

1) перевести D-кортеж в С-систему P c k C-кортежами;

2) выбрать произвольную перестановку С-кортежей в P (число таких перестановок равно k) и записать P в порядке, соответствующем этой перестановке;

3) для каждой неполной компоненты Pij (i – номер строки, j – номер столбца) преобразованной C-системы P заменить все фиктивные компоненты Pmi (m>i), находящиеся ниже Pij, ее дополнениями Pij.

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

Для иллюстрации повторим ранее выполненное преобразование D-системы P в С-систему, но при этом D-кортежи преобразуем в ортогональные С-системы иначе:

ровку ее столбцов и строк так, чтобы сгруппировать непустые компоненты в верхнем левом “миноре” логической матрицы кортежи с ненулевыми компонентами. Для этого переставим строки 1 и 3 местами.

С-системы. Получаем:

4. Вычислим пересечение первых двух C-систем (получающиеся при этом пустые С-кортежи, которые затем удаляются из С-системы, здесь не показаны):

{a, c} {a, b, c} {a, c} Теперь найдем пересечение полученной С-системы с оставшейся:

{a, c} {a, b, c} {a, c} Нетрудно убедиться, что итоговая С-система, содержащая четыре С-кортежа, ортогональна, а по составу элементарных кортежей эквивалентна ранее полученной С-системе, содержащей семь С-кортежей. Из примера видно, что суть метода сводится к тому, чтобы максимально увеличить число пустых кортежей, образующихся на первых и промежуточных этапах вычисления, путем соответствующего выбора вариантов ортогонализации D-кортежей в исходной D-системе – за счет этого существенно уменьшается число вариантов, подлежащих дальнейшей обработке.

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

Литература 1. Рассел, С. Искусственный интеллект: современный подход. 2-е изд. / С.

Рассел, П. Норвиг // пер. с англ.; ред. К.А. Птицына. – М.: Изд. дом «Вильямс», 2006. -1408 с.

2. Ченцов, А.Г. Экстремальные задачи маршрутизации: теория и приложения /А.Г. Ченцов // Шестая Всероссийская мультиконференция по проблемам управления, г. Геленджик, с. Дивноморское, 30 сентября – 5 октября 2013 г.:

материалы мультиконференции: в 4 т. – Ростов-на-Дону: Изд-во Южного федерального университета, 2013. -Т.3. – C.213-220.

3. Кулик, Б.А. Алгебраический подход к интеллектуальной обработке данных и знаний / Б.А. Кулик, А.А. Зуенко, А.Я. Фридман – СПб.: Изд-во Политехн.

ун-та, 2010. – 235 с.

4. Зуенко, А.А. Матрицеподобные вычисления в задачах удовлетворения ограничений /А.А. Зуенко // Шестая Всероссийская мультиконференция по проблемам управления, г. Геленджик, с. Дивноморское, 30 сентября – 5 октября 2013 г.: материалы мультиконференции: в 4 т. – Ростов-на-Дону:

Изд-во Южного федерального университета, 2013. -Т.1. – C.30- 5. Зуенко, А.А. Реализация комбинированных методов логико-семантического анализа с использованием алгебры кортежей / А.А. Зуенко, Б.А. Кулик, А.Я.

Фридман // Тринадцатая национальная конференция по искусственному интеллекту с международным участием, г. Белгород, 16-20 октября 2012г.:

труды конференции. - Белгород: Изд-во БГТУ, 2012. -Т.2. - С.67-75.

6. Зуенко, А.А. Булевы алгебры как средство интеллектуального анализа систем рассуждений / А.А. Зуенко, А.Я. Фридман, Б.А. Кулик // Интеллектуальный анализ информации ИАИ-2012: сборник трудов XII Международной научной конф. имени Т.А. Таран, г. Киев, 16-18 мая 2012 г.: / гл. ред. С.В. Сирота.

- К.: Просвiта, 2012. – C.70-78.

7. Boris Kulik, Alexander Fridman, Alexander Zuenko. N-tuple Algebra: Providing Clarity by Combining Logical Inference with Defeasible Reasoning // Cybernetics and Systems 2012: Proceedings of Twentieth European Meeting on Cybernetics and Systems Research (EMCSR 2012), 10-13 April, 2012, Vienna, Austria.

- P.315-318.

8. Kulik, B. Logical Analysis of Intelligence Systems by Algebraic Method /B. Kulik, A. Fridman, A. Zuenko // Cybernetics and Systems 2010: Proceedings of Twentieth European Meeting on Cybernetics and Systems Research (EMCSR 2010) Vienna, Austria, 2010. – P.198-203.

Сведения об авторе Зуенко Александр Анатольевич - к.т.н, научный сотрудник, е-mail: [email protected] Alexander A. Zouenko - Ph.D. (Tech. Sci.), Researcher УДК 004. А.А. Зуенко, А.А. Алмаматов ФГБУН Институт информатики и математического моделирования технологических процессов

КНЦ РАН

Кольский филиал ПетрГУ

ПОИСКОВЫЕ ЗАПРОСЫ НА ОСНОВЕ ОПЕРАЦИЙ С ЛОГИЧЕСКИМИ

ВЕКТОРАМИ

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

Ключевые слова:

поисковый запрос, логические векторы, регулярные выражения.

A.A. Zuenko, A.A. Almamatov

RETRIEVAL REQUESTS USING OPERATIONS ON BOOLEAN VECTORS

Abstract An original algorithm for searching in natural language texts based on the algebraic representation of the source text and search operations is proposed. The algorithm uses search patterns for flexible setting various search conditions. The patterns are translated into a sets of algebraic operations on boolean vectors.

Key words:

retrieval request, boolean vectors, regular expressions.

Введение В настоящее время существует множество алгоритмов поиска подстроки в строке: Бойера-Мура, Чжу – Такаоки, Бойера – Мура – Хорспула, Кнута – Морриса – Пратта, Рабина – Карпа и т.д.

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

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

POSIX – (Portable Operating System Interface for Unix – переносимый интерфейс операционных систем Unix;

Работа выполнена при финансовой поддержке РФФИ (проекты №№ 11-08-00641, 12-07-00550-а, 12-07-00689-а, 13-07-00318-а), ОНИТ РАН (проект 2.3 в рамках текущей Программы фундаментальных научных исследований) и Президиума РАН (проект 4. Программы № 16).

PCRE – Perl Compatible Regular Expressions – регулярные выражения, совместимые с языком Perl.

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

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

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

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

Формирование поисковых шаблонов Запрос формируется в виде строки текста, содержащей в себе последовательность символов, классов символов, заданных вариантов, wildcard и т.д.

чение пробельные символы (пробел, табуляция, возврат каретки, новая строка) все, кроме пробельных символов символы пунктуации («.», «,», «!», «», «», «») символ, являющийся повторением предыдущего. Может использоваться как форма записи повторений символов, а также в сложных «ИЛИ» или «И» выражениях При необходимости возможно задание некоторого множества символов/классов, а также поиска всего, кроме заданных символов. Для этого нужно множество заданных символов вписать в квадратные скобки. Если необходимо искать все, кроме заданных символов, нужно после открывающейся скобки поставить символ «^».

[abcd] [^abcd] [abcdefgh\d] [^\s\p] Также возможно задание выражения «ИЛИ» вместо некоторого символа в запросе. По принципу работы оно эквивалентно предыдущей функции с той лишь разницей, что между всем, заданным внутри функции, выполняется функция «И». Отрицание выражения с помощью «^» также возможно.

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

Запись Эквивалентная запись Трактовка Теперь прейдем к описанию базового алгоритма поиска на основе операций с логическими векторами.

Базовый алгоритм поиска подстроки на основе операций с логическими векторами Пусть используемый алфавит состоит из N литер. Позиции в тексте отдельной литеры могут быть заданы характеристическим вектором, размерность которого равна длине самого текста L. Каждый элемент характеристического вектора принимает значение 1 или 0 в зависимости от того, присутствует или нет данная литера в тексте в данной позиции. Текст представлен в памяти машины в виде N логических векторов длиной L.

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

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

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

V[а] : V[г]: V[д]: V[о]: V[р]: V[“ “]: Запись V[s] обозначает булев вектор, соответствующий символу s. Для простоты далее будем использовать следующую сокращенную запись:

пробел: Начнем процедуру поиска слова "род". Первый логический вектор для литеры "р" оставим без изменений. Второй логический вектор для литеры "о" сдвинем на один разряд влево, а логический вектор для литеры "д" сдвинем на два разряда влево. Результат будет определяться произведением этих векторов.

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

где i – номер позиции символа, SHL – функция побитового сдвига вектора влево на заданное количество позиций.

В итоге получим следующие логические векторы:

SHL(V[р],0): SHL(V[о],1): SHL(V[д],2): Логическое умножение этих векторов дает вектор: 10000000000100, в котором единицы указывают позиции, где находится начало искомого слова.

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

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

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

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

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

Пример 2. Пусть дан текст: abcdbabccabd. Тогда карта будет выглядеть:

a: b: c: d: Необходимо найти последовательность символов «abcd» или «abcc»(обе имеются в тексте). Тогда можно задать вектор последнего символа как результат выполнения операции OR между векторами символов «c» и «d»:

d: c: с_or_d: Процесс поиска можно представить как:

SHL(V[a],0) AND SHL(V[b],1) AND SHL(V[c],2) AND SHL(V[с_or_d],3), где SHL(V[a],0): SHL(V[b],1): SHL(V[c],2): SHL(V[с_or_d],3): Результат поиска: Теперь рассмотрим многовариантный поиск, задаваемый через отрицание. Отрицание также может быть использовано в поиске текста, например, когда необходимо в качестве символа разрешить все, кроме символа/нескольких символов.

Пример 3. Предположим, что в тексте: abcdbabccabd, необходимо найти все последовательности abc, после которых идет не-d. В таком случае класс символов «не-d» будет задаваться через отрицание d:

d: not-d: Процесс поиска можно представить как:

SHL(V[a],0) AND SHL(V[b],1) AND SHL(V[c],2) AND SHL(V [not_d],3), где SHL(V[a],0): SHL(V[b],1): SHL(V[c],2): SHL(V[not_d],3): Результат поиска: 000001000000.

Заключение Таким образом, была рассмотрена модификация метода биассоциативного поиска текста на случай, когда для задания запросов могут быть использованы регулярные выражения. Алгоритм поиска может быть также применен за пределами задачи поиска текста. Вместо текста может быть всё, что представимо в виде последовательности битов. Например, в качестве последовательности может использоваться набор последовательно поступающих во времени векторов значений входных воздействий некоторой системы, а также выходных значений и внутренних состояний.

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

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

Литература 1. Кулик, Б.А. Алгебраический подход к интеллектуальной обработке данных и знаний / Б.А. Кулик, А.А. Зуенко, А.Я. Фридман. – СПб.: Изд-во Политехн.

ун-та, 2010. – 235 с.

2. Кулик, Б.А. Система поиска слов в произвольном тексте / Б.А. Кулик // Программирование. -1987.- № 1. -C.49-50.

Сведения об авторах Зуенко Александр Анатольевич - к.т.н, научный сотрудник, е-mail: [email protected] Alexander A. Zouenko - Ph.D. (Tech. Sci.), Researcher Алмаматов Александр Анатольевич – стажер-исследователь, Alexander A. Almamatov – Probationer-researcher УДК 004. А.А. Зуенко ФГБУН Институт информатики и математического моделирования технологических процессов

КНЦ РАН

Кольский филиал ПетрГУ

ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ ЛОГИКО-ВЕРОЯТНОСТНОГО

АНАЛИЗА НА ОСНОВЕ МАТРИЧНЫХ И МЕТРИЧЕСКИХ СВОЙСТВ

АК-ОБЪЕКТОВ Аннотация В статье рассматривается разработанный автором модуль расчета надежности структурно сложных систем. Методы логико-вероятностного анализа программно реализованы с применением структур алгебры кортежей. Модуль может быть использован как самостоятельное приложение, а также выполнять роль сервера при распределенных вычислениях.

Ключевые слова:

алгебра кортежей, логико-вероятностный анализ, СOM-интерфейсы.

A.A. Zuenko

PROGRAM IMPLEMENTATION OF LOGICAL AND PROBABILISTIC ANALYSIS

BASED ON MATRIX AND METRIC PROPERTIES OF THE NTA-OBJECTS

Abstract In the article implementation of a program module developed for logic and probabilistic analysis is considered. Methods of logic and probabilistic analysis are programmed using n-tuple algebra’s structures. The module could be used as a standalone application, or act as a server for distributed computing.

Key words:

n-tuple algebra, logic and probablistic analysis, СOM interfaces.

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

В алгебре кортежей (АК), основы которой подробно изложены в [4, 5, 6], разработаны методы расчёта надёжности структурно сложных систем с множеством состояний, представленным в виде [7]:

пары элементов («работоспособен»/ «неработоспособен»);

конечного множества элементов;