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

Введение.

Глава 1.

1.1. Обзор технологий поиска.

1.2. Системы поиска в сети Internet

1.3. Поисковые агенты.

1.4. Системы поиска в локальных сетях.

Глава 2.

2.1. Основные определения.

2.2. Фактографическая логика средних.

2.3. Логика ранжирования списков оценок экспертов

2.4. Геом. интерпретация отрицания среднего выбора

2.5. Механизм поиска на основе описанных логик

2.6. Проверка законов булевой алгебры.

Глава 3.

3.1. Обзор элементов ТРИЗ.

3.2. Использование элементов ТРИЗ для уточнения поиска

3.3. Описание ссылочного языка и ссылочного документа

3.4. Характеристика ссылочного языка и документа

3.5. Система поиска на основе ссылочного языка.

Глобальная сеть Internet и локальные сети intranet содержат гигантский объем информации на самые различные темы. Найти нужную и полную информацию по интересующей тематике вручную практически невозможно.

Существует ряд поисковых систем для сети Internet (более 200) и для локальных сетей, которые по логической комбинации ключевых слов возвращают список ссылок на документы, удовлетворяющие запросу [9]. Однако Такой список может содержать от нескольких десятков до нескольких тысяч ссылок, из которых зачастую более 90 процентов ссылок неудачные, либо возвращаемый список пуст [8]. В силу своей эффективности наиболее популярными поисковыми системами в настоящее время являются Aport, Yandex, AltaVista, Yahoo, Lycos и другие.

Существующие системы не позволяют включать в документы дополнительную информацию для поиска (например, список всех важных слов, не включая предлоги, частицы, местоимения, союзы и другие). Обычно информация в сети хранится в виде HTML-файлов (HyperText Markup Language, язык разметки гипертекста) и поиск осуществляется только по вхождению ключевых слов в заголовках и телах документов.

Поисковые системы имеют индексные базы размером в более сотни гигабайт, в которых проиндексированы ключевые слова. Каждому слову из таблицы сопоставляются адреса URL (Uniform Resource Locator, универсальный локатор ресурсов) документов, в которых они встречаются. Во время выполнения запроса поисковая система производит операции с соответствующими списками (объединение, пересечение и разность) по логической комбинации ключевых слов, указанных в запросе. Поисковые системы на основе предварительного индексирования требуют дополнительных ресурсов для хранения индексных таблиц и, самое главное, значительное время на их создание и поддержание актуальности. Системы для поиска в локальных сетях ориентированы в первую очередь на конкретный тип сети и операционной системы, откуда осуществляется поиск, то есть являются платформо-зависимыми. Системы поиска в глобальных сетях проводят анализ в основном HTML-файлов, используемых для представления гипертекстовой информации, не предоставляя возможности указывать другие форматы документов для поиска. Очень часто, с первого раза сложно построить запрос, по которому были бы найдены все релевантные документы и только они. В существующих системах отсутствует возможность дальнейшей удобной модификации и уточнения запросов и наличие соответствующих подсказок для того, чтобы новый запрос был более удачным.

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

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

Пример неудачного поиска в сети Internet Для поиска домашней страницы Санкт-Петербургского государственного университета были указаны ключевые слова Petersburg, State и University, В результате получили список из нескольких тысяч документов, подавляющая часть которых являлись домашними страницами студентов или преподавателей этого университета. Все дело в том, что в заголовках страниц содержались фразы, подобные: I am а . of Saint -Petersburg State University.

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

В некоторых справочных системах, например Kodeks [7], поиск является контекстным и требует непосредственного полного просмотра текста, занимая много времени. Время ожидания в таком случае возрастает уже до нескольких десятков минут.

Пример неудачного поиска в системе Kodeks. Задача заключалась в том, чтобы найти полную редакцию закона "О защите прав потребителейДля поиска были заданы ключевые слова: защита, прав и потребителей, объединенных связкой И. После двадцати пяти минут поиска был сформирован список более чем из тысячи документов. В чем заключается неэффективность поиска? После анализа результатов выяснилось, что ключевое слово прав входит как подстрока в слово правительство, что и привело к такому эффекту. В параметрах поиска системы Kodeks нельзя задавать слова с концевым пробелом, например, "прави".

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

Существуют документы, которые содержат заданные ключевые слова как подстроку, но не являются релевантными. Причинами этого несоответствия (противоречия) являются следующие факторы: омонимы, графическое вхождение ключевого слова как подстроки в текст. Например, слово лед входит в ледокол, коза входит в стрекоза. Существуют документы и другого рода, которые удовлетворяют теме поиска, но не содержат вовсе заданных ключевых слов.

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

Рис. 1. Прогноз погоды

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

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

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

Рис. 2. Пример трехсторонней ссылки

Использование тг-сторонних ссылок (мультиссылок) XLink языка XML (extensible Markup Language) в поисковых системах связано с трудностью из-за наличия большого числа различных описаний грамматик XML-файлов (Document Type Definition, DTD). Для того, чтобы обеспечить проверку корректности XML-документов, необходимо использовать анализаторы, ее производящие. В отличие от языка SGML, определение DTD-правил в XML не является необходимостью, и это обстоятельство позволяет создавать любые XML-документы, возможно, с некорректными ссылками, так как разметка просто показывает, что такая ссылка существует, но не определяет, что следует приложению с ней делать. Атрибуты ссылок XLink жестко фиксированы и не позволяют ограничивать глубину при поиске или навигации. Язык XML не оказывает серьезного влияния на технологии поисковых систем, пока не будет создан список общих, стандартных спецификаций DTD. Существующие системы поиска не позволяют видеть один и тот же документ по-разному для различных пользователей в соответствии с их системой настроек.

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

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

Во второй главе вводятся фактографическая логика средних [16] и логика ранжирования списков оценок экспертов (n-агентная логика [32]), на основе которых построен механизм поиска, возможно, с противоречивыми запросами разного уровня. В отличие от предложенных Н.К. Косовским эвристической и плюралистической логик [12], в которых значения переменных представляются кортежами фиксированной длины из п рациональных чисел (эвристическая логика является при п — 2 частным случаем плюралистической логики), в предлагаемых логиках разным значениям переменных 9 могут соответствовать кортежи разной длины при условии, что длина кортежа не превосходит максимального количества экспертов. В следующем разделе рассматривается логика ранжирования списков оценок экспертов. Далее рассматривается геометрическая интерпретация операции отрицания предложенных логик и механизм поиска ссылочных документов на основе логик и ссылочного языка, рассматриваемого в третьей главе. В конце главы приведена проверка того, что для введенных логик выполняются основные законы булевой алгебры (кроме закона исключенного третьего и закона противоречия).

В третьей главе первый раздел посвящен элементам теории решения изобретательских задач (ТРИЗ), предложенной Г.С. Альтшуллером для разрешения технических несоответствий (парадоксов и противоречий). Описывается использование методов и приемов ТРИЗ для получения удачного уточнения (модификации) запроса в разработанной поисковой системе [27], [31]. Дается описание взаимодействия некоторых компонент реализованного комплекса [28]. Во втором разделе третьей главы рассматривается структура ссылочного документа и описание ссылочного языка. В заключении приведены основные результаты работы.

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

Заключение

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

1. Предложен механизм творческого навигационного поиска в сети с элементами теории решения изобретательских задач (ТРИЗ), на его базе реализован поисковый Java-комплекс, превосходящий по эффективности аналогичные системы на 20-30 процентов. Продемонстрирована на примерах его эффективность.

2. Описан и реализован ссылочный язык для формирования ссылочных документов и ссылочных шаблонов.

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

1. Альтшуллер Г.С. Творчество как точная наука. — М.: Советское радио, 1979. — 175 с.

2. Альтшуллер Г.С. Найти идею: введение в теорию изобретательских задач. — Новосибирск: Наука, 1986. — 209 с.

3. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1. Синтаксический анализ. — М.: Мир, 1978. — 611 с.

4. Биркгоф Г. Теория структур. — М.: Иностранная литература, 1952. — 407 с.

5. Владимиров Д.А. Булевы алгебры. — М.: Наука, 1969. — 320 с.

6. Волгин Л.И., Левин В.И. Континуальные логики, теория и приложения. — Таллинн, 1991.

7. Информационная система "Кодекс". —. Санкт-Петербург: Центр компьютерных разработок, 1997. — 60 с.

8. Капустин В. Поиск информации в Интернете // Мир Internet. — 1998. — № 9. — С. 54-59.

9. Качулин Н. Поиск в Интернете // Мир Internet. — 1997. — № 11. — С. 32-39.

10. Кондаков Н.И. Введение в логику. — М.: Наука, 1967. — 466 с.

11. Кнут Д. Искусство программирования для ЭВМ. Т. 1. Основные алгоритмы. — М.: Мир, 1976. — 734 с.

12. Косовский Н.К., Тишков А.В. Плюралистическая логика // Информационные технологии & интеллектуальные методы, Санкт-Петербургский институт информатики и автоматизации РАН. — Санкт-Петербург, 1999. — Вып. 3. — С. 62-71.

13. Косовский Н.К., Тишков А.В. Логики конечнозначных предикатов на основе неравенств. — СПбГУ, 2000. — 268 с.

14. Косовский Н.К., Ярославский В.В. Фактографические дизъюнкция и конъюнкция на основе среднего арифметического векторов значений //2 международная конференция "Смирновские чтения". — Москва, 18-20 мая, 1999. — С. 163-164.

15. Косовский Н.К., Ярославский В.В. Булевы операции усредняющей логики / / Информационные технологии в гуманитарных науках. Сборник докладов. — Казань, 1999. — С. 64-68.

16. Косовский Н.К., Ярославский В.В. Многоагентная фактографическая логика средних для поиска в сети / / VII международная конференция "Математика. Компьютер. Образование". — Дубна, 23-30 января, 2000. — С. 169.

17. Косовский Н.К., Ярославский В.В. Дискретно-непрерывный логический аппарат // Труды международной конференция "Континуальные логико-алгебраические и нейросетевые методы в науке, технике и экономике".-----Ульяновск, 16-18 мая,2000. — С. 41.

18. Нильсон Н. Искусственный интеллект. Методы поиска решений. — М.: Мир, 1973. — 270 с.

19. Романовский И.В. Дискретный анализ. — Санкт-Петербург: Невский диалог, 1999. — 254 с.

20. Скорняков Л.А. Элементы теории структур. — М.: Наука, 1982. — 160 с.

21. Салтон Дж. Динамические библиотечно-информационные системы. — М.: Мир, 1979. — 557 с.

22. Уэно X., Исидзука М. Представление и использование знаний. — М.: Мир, 1989. — 220 с.

23. Фитиалов С.Я. Формальные грамматики. — JL: Ленинградский университет, 1984. — 99 с.

24. Шрейдер Ю.А. Тезаурусы в информатике и теоретической семантике // Научно-техническая информация. — 1971. — № 3. — С. 15-17.

25. Ярославский В.В. Проект системы ссылочных шаблонов для документов сети //VI международная конференция "Математика. Компьютер. Образование". — Пущино, 24-31 января, 1999. — С. 307.

26. Ярославский В.В. Проект информационной системы поиска на основе ссылочного языка для эффективной работы // Шестая всероссийская конференция "Муниципальные геоинформационные системы" (МГИС'99). — Обнинск, 25-30 января, 1999. — С. 149-152.

27. Ярославский В.В. Творческий поиск однородных текстов // Информационные технологии в гуманитарных науках. Сборник докладов. Казань. 1999. С. 85 89.

28. Ярославский В.В. Поиск однородных документов с использованием логических шаблонов / / Международной научной конференции "Интеллектуализация обработки информации". — Симферополь: Таврический национальный университет, 2000. — С. 127-129.

29. Dayang Sh., Zuoquan L. Searching Algorithms of Internet Information Collecting Agent // The International Workshop74on Distributed Artificial Intelligence and Multi-agent Systems (DAIMAS'97). — Saint-Petersburg, June 15-18, 1997. — P. 111-114.

30. Iaroslavski V. Creative search of the homogeneous texts // Proceedings of the 3-d International Conference "Interactive Systems: The Problems of Human-Computer Interaction". — Ulianovsk, September 22-24, 1999. — P. 104.

31. Kossovski N.K., Tishkov A.V., Iaroslavski V.V. The prepositional n-agent logic // Proceedings of the 1-st International Workshop of Central and Eastern Europe on Multi-Agent Sytems (CEEMAS' 99). — St.-Petersburg, June 1-4, 1999. — P. 331-333.

32. Krulwich В., Burkley Ch. The InfoFinder Agent: Learning user interests through heuristic phrase extraction // IEEE Expert, 1997, vol. 12, № 5. — P. 22-27.

33. Luhn H.P. A Statistical approach to mechanized encoding and searching of literary information. — IBM Journal of Research and Development, №4. P. 309 317.

34. Nwana H.S., Ndumu D.T. An introduction to agent technology / / Applications & Technology. Software agents and soft computing. — Springer-Verlag, Berlin, 1997. — P. 3-26.

35. Salton G. Effective information retrieval using term accuracy // Communication ACM, V. 20, 1992. — P. 135-142.