Содержание к диссертации
Введение
Глава 1. Основные подходы к поиску информации в электронных документах 14
1.1. Традиционные поисковые системы 14
1.1.1 Формальные компоненты поисковой системы 15
1.1.2 Логический метод определения множества претендентов 17
1.1.3 Проблема ранжирования: переход от ~ к 19
1.1.3.1 Логический метод ранжирования 20
1.1.3.2 Ранжирование на основе вектора документа 21
1.1.3.3 Реалистичные модели ранжирования 24
1.1.4 Оценка качества документа на основе цитирования: алгоритм PageRank 25
1.1.4.1 Вычисление рейтинга страницы по алгоритму PageRank 27
1.1.4.2 Наглядное обоснование 28
1.2. Семантический поиск 29
1.3. Естественно-языковые поисковые системы 33
1.3.1 Обзор зарубежных естественно-языковых поисковых систем 35
1.3.2 Обзор отечественных естественно-языковых поисковых систем 36
1.4. Постановка задачи диссертационного исследования 39
1.5. Выводы по главе 1 41
Глава 2. Формализация и алгоритмизация обработки аспектно-ориентированных запросов 42
2.1 Состояние исследований по семантической обработке вопросов на естественном языке 42
2.2 Базовые принципы нового подхода к семантически-ориентированному поиску информации в Интернете 46
2.3 Разработка принципов семантического расширения аспектно-ориентированных запросов 51
2.3.1 Центральные идеи предлагаемого подхода 51
2.3.2 Первичные информационные единицы для разработки алгоритма анализа аспектно-ориентированных запросов 53
2.4 Краткая характеристика теории К-представлений 54
2.5 Разработка математической модели проблемно-ориентированной системы первичных единиц концептуального уровня 57
2.6 Разработка плана алгоритма построения семантического расширения аспектно-ориентированного поискового запроса 62
2.7 Анализ структуры входных запросов аспектно-ориентированного типа 67
2.8 Формализация предположений о входном языке аспектно-ориентированных поисковых запросов 70
2.9 Основные идеи разработки алгоритмов определения типа и объектов интереса входных запросов 75
2.10 Алгоритмы определения типа аспектно-ориентированного вопроса и его объектов интереса 80
2.10.1 Алгоритм определения типа запроса 80
2.10.2 Алгоритм определения объектов интереса запроса 81
2.11 Разработка алгоритма построения семантического расширения аспектно-ориентированного поискового запроса 83
2.12 Обсуждение разработанных алгоритмов 85
2.13 Выводы по главе 2 86
Глава 3. Разработка алгоритмов семантического преобразования обобщенных запросов на основе математических моделей компонентов базы знаний 88
3.1. Разработка принципов семантического расширения обобщенных запросов достижения целей 88
3.2. Формальная модель базы знаний для представления целей 92
3.3. Анализ структуры запросов достижения целей 94
3.4. Разработка алгоритма определения типа вопросов достижения целей и их объектов интереса 95
3.5. Метод преобразования вопросов достижения целей к расширенному виду .98
3.6. Разработка принципов семантического расширения обобщенных запросов об изменениях состава множеств 98
3.7. Разработка формальной модели базы знаний для описания изменений состава множеств 103
3.8. Анализ структуры запросов об изменениях составов множеств 105
3.9. Разработка алгоритма определения типа запросов об изменениях составов множеств и их объектов интереса 107
3.10. Метод построения семантического расширения вопросов об изменениях в составе множеств 112
3.11. Разработка итоговой модели базы знаний для поддержки поиска 114
3.12. Выводы по главе 3 115
Глава 4. Программная реализация системы семантически-ориентированного поиска на основе предложенного метода и исследование полученных результатов 117
4.1 Разработка и реализация архитектуры программного комплекса AOS Engine 117
4.1.1 Разработка концептуальной архитектуры программного комплекса... 117
4.1.2 Разработка компонентной архитектуры программного комплекса. 121
4.1.2.1 Общая архитектура программного комплекса и выбор платформы реализации 121
4.1.2.2 Лингвистическая база знаний 122
4.1.2.3 Аспектно-ориентированная база знаний 127
4.1.2.4 Подсистема AOS Engine 129
4.1.2.5 Выбор платформы реализации 131
4.2 Разработка итогового алгоритма построения расширенного множества запросов и ранжирования результатов 133
4.3 Исследование полученных результатов 137
4.4 Выводы по главе 4 142
Заключение 144
Список литературы 147
Приложения 157
- Вычисление рейтинга страницы по алгоритму PageRank
- Первичные информационные единицы для разработки алгоритма анализа аспектно-ориентированных запросов
- Разработка алгоритма определения типа вопросов достижения целей и их объектов интереса
- Разработка итогового алгоритма построения расширенного множества запросов и ранжирования результатов
Введение к работе
Актуальность темы исследования. В настоящее время параллельно с ростом объемов информации в Интернете происходит разработка новых и совершенствование существующих подходов к ее поиску. Все большую актуальность приобретают средства семантического поиска, под которыми понимаются системы, принимающие на вход некоторый запрос, обрабатывающие его с использованием рассуждений над специфичной базой знаний и возвращающие совместимые результаты. Входным запросом может являться, например, вопрос на естественном языке (ЕЯ), представление вопроса при помощи триплетов, графическое представление, набор ключевых слов, отдельные фразы и т.д. В роли базы знаний могут выступать онтологии, аннотированные массивы текста, текстовые документы, Веб, XML-документы, RDF документы, HTML документы и т.д. В нашей стране значительный вклад в развитие семантического поиска внесли Э.Э. Гасанов, А.Е. Ермаков, А.Н. Королев, И.П. Кузнецов, Д.Г. Лахути, Н.Н. Леонтьева, М.Г. Мальковский, А.Г. Мацкевич, А.С. Нариньяни, И. С. Некрестьянов, Т.С. Осипов, И.В. Сегалович, А.В. Сокирко, Н.В. Перцов, Н.Н. Перцова, Э.В. Попов, В.Ш. Рубашкин, И.А. Тихомиров, В.О. Толчеев, В.А. Тузов, В.А. Фомичёв, Н.П. Харин, В.Ф. Хорошевский и другие учёные.
Однако, несмотря на большое разнообразие методов и подходов к семантическому поиску, у существующих поисковых систем имеется ряд недостатков. К ним можно отнести отсутствие семантического описания электронных документов (в большинстве случаев), высокую трудоемкость алгоритмизации автоматизированного создания данного описания, большой разрыв между технологиями семантического веба и гипертекстового поиска (развиваются параллельно и независимо друг от друга), недостаточные интеллектуальные возможности анализаторов естественно-языковых запросов вопросно-ответных систем.
Объект исследования: методы семантической обработки поисковыми системами естественно-языковых запросов.
Предмет исследования: методы применения формальных средств для семантического анализа и преобразования поисковых запросов на естественном языке, проектирования лингвистической базы знаний, а также баз знаний для поддержки преобразования запросов и поиска.
Цель исследования: разработать такой метод семантического преобразования важных с практической точки зрения естественно-языковых поисковых запросов в форму (множество производных запросов), позволяющую традиционным системам поиска обнаружить наиболее релевантные результаты, который предусматривает применение формальных средств для описания (а) системы концептуальных единиц первичного уровня, (б) логической структуры базы знаний для поддержки преобразования запросов и поиска.
Задачи исследования:
1.Провести анализ состояния исследований по семантической обработке поисковыми системами вопросов на естественном языке (ЕЯ) с целью выявления классов вопросов, недостаточно проработанных в научной литературе и имеющих большую практическую значимость для систем естественно-языкового поиска.
2. По результатам проведенного анализа разработать метод семантического
преобразования, который бы позволил трансформировать поданный на вход
естественно-языковой запрос в форму (множество производных запросов),
позволяющую повысить релевантность документов, выдаваемых системами
поиска по ключевым словам.
3. Выбрать наиболее соответствующую предложенному методу
методологическую основу исследования для построения математических
моделей компонентов базы знаний, необходимых для семантического
преобразования естественно-языковых запросов.
4. Построить математические модели компонентов базы знаний,
необходимых для семантического преобразования поисковых запросов для
выбранных типов вопросов. Построить итоговую математическую модель для
поддержки семантического преобразования запросов и поиска.
5. На основе предложенных моделей разработать алгоритмы анализа и
преобразования поисковых запросов в форму (множество производных
запросов), позволяющую повысить релевантность документов, выдаваемых
системами поиска по ключевым словам. Разработать алгоритм ранжирования
результатов по степени релевантности поисковому запросу.
6 . Разработать программный комплекс, реализующий предложенный метод семантического преобразования поисковых запросов.
7. Провести тестирование разработанного программного комплекса и проанализировать полученные результаты.
Теоретико-методологическую основу исследования составляют теория алгоритмов, теория графов, теория контекстно-свободных грамматик, теория К-представлений, методы теоретического программирования и Веб программирования.
Достоверность и обоснованность научных положений подтверждается корректным применением математического аппарата теории К-представлений, теории контекстно-свободных грамматик, теории алгоритмов и результатами тестирования разработанной компьютерной программы.
В ходе исследования была решена научная задача создания такого метода семантического преобразования естественно-языковых запросов в расширенную форму, позволяющую традиционным поисковым системам получать более релевантные результаты, который предусматривает применение формальных средств для описания (а) системы первичных единиц концептуального уровня, (б) логической структуры базы знаний для
поддержки преобразования запросов и поиска, (в) шаблонов семантических трансформаций, необходимых для преобразования поисковых запросов.
Теоретическая значимость исследования. Впервые предложен базирующийся на математической модели подсистемы базы знаний метод семантического преобразования ЕЯ-запросов поисковых систем (ПС) в форму (множество производных запросов), позволяющую повысить релевантность результатов работы системы поиска по ключевым словам.
Практическая значимость исследования состоит в том, что предложен новый подход к анализу и преобразованию ЕЯ-запросов поисковых систем в такую форму (множество производных запросов), которая позволяет повысить релевантность документов, получаемых от традиционных поисковых систем. Данный подход базируется на построении математических моделей семантических и семантико-синтаксических объектов, которые используются алгоритмами построения множества преобразованных запросов. Разработанные алгоритмы позволяют определять типы и подтипы ЕЯ-запросов ПС, а также выделять объекты интереса запросов. На основе разработанной модели базы знаний для поддержки преобразования запросов и поиска в зависимости от типа запроса и выделенных объектов интереса происходит построение множества семантически преобразованных запросов, которые подаются на вход традиционной ПС. Разработанный алгоритм ранжирования результатов поисковой выдачи позволяет повысить релевантность результатов по сравнению с системами поиска по ключевым словам. Математический подход, базирующейся на теории К-представлений, является предметно независимым и может быть использован при проектировании базы знаний для поддержки преобразования запросов и поиска в разных предметных областях. Важным аспектом практической ценности разработанного комплекса является возможность его интеграции с любым количеством поисковых систем, а также возможность управления информацией в базе знаний с целью повышения соответствия результатов поиска информационной потребности пользователей, что не требует внесения изменений в разработанные алгоритмы.
Полученные в диссертации результаты использованы в научных и проектных исследованиях компании «Вокском - Голосовые Телекоммуникации» (Москва), а также в лекционных и лабораторных занятиях по дисциплине «Проектирование лингвистических процессоров» на кафедре «Информационные технологии» «МАТИ» - Российского государственного технологического университета им К.Э. Циолковского.
Основные положения, выносимые на защиту:
1. Разработан комплекс математических моделей семантических и семантико-синтаксических объектов, предназначенных для расширения пользовательских поисковых запросов:
1.1. Математическая модель проблемно-ориентированной системы
первичных единиц концептуального уровня, используемой для построения множества преобразованных аспектно-ориентированных запросов.
1.2. Математическая модель концептуальной базы целей,
используемая для преобразования запросов достижения целей.
1.3. Математическая модель концептуальной базы знаний об
изменениях множеств, используемой для поддержки преобразования
запросов об изменениях состава множеств.
1.4. Итоговая математическая модель базы знаний для поддержки
семантического преобразования запросов и поиска.
2. Разработан комплекс из двух алгоритмов, обеспечивающих анализ
поисковых запросов на соответствие рассматриваемым типам и подтипам
поисковых запросов, а также позволяющий определить значимые объекты
интереса поисковых запросов.
-
Разработаны метод и алгоритм построения множества преобразованных запросов.
-
Разработан программный комплекс, реализующий предлагаемый метод семантического преобразования поисковых запросов и использующий разработанные алгоритмы. Разработанный программный комплекс был успешно развернут по адресу
5. Разработана КС-грамматика в форме Бэкуса-Наура для описания
входного языка поисковых запросов пользователей.
Апробация и внедрение результатов исследования. Основные результаты работы представлялись и получили одобрение на научно-практической конференции студентов и аспирантов «Информационные технологии в экономике, бизнесе, управлении» (ГУ-ВШЭ, 2010), на IX Международной научно-технической конференции «Новые информационные технологии и системы» (НИТиС-2010), на молодежной научной конференции «Гагаринские чтения» в МАТИ (2011) и на научном семинаре «Математические модели информационных технологий» Отделения прикладной математики и информатики факультета бизнес-информатики НИУ ВШЭ в 2012 году. По теме диссертационной работы опубликовано 7 научных работ, включая две статьи в изданиях из списка изданий, рекомендованных ВАК РФ. Разработанный в диссертации программный комплекс был развернут по адресу
Структура диссертации: основной текст диссертации изложен на 156 страницах, состоит из введения, четырёх глав, заключения, списка литературы из 100 наименований и девяти приложений.
Вычисление рейтинга страницы по алгоритму PageRank
Можно провести аналогию между списками использованной литературы в академических работах и ссылками на определенные страницы в Вебе. Подсчет ссылок на страницу из разных источников дает приближенное значение важности или, другими словами, качества страницы. Алгоритм PageRank расширяет данный подход не только подсчетом количества ссылок (принимая значимость ссылок с каждой из страниц равной), но и упорядочивая страницы по количеству ссылок, содержащихся в них. Рейтинг страницы по PageRank определяется следующим образом [81]: Предположим, что на документ A ссылаются страницы T1...Tn . Параметр d является коэффициентом затухания, находящимся в интервале (0;1). Обычно d присваивается значение равное 0.85. C(A) определяет количество исходящих со страницы A ссылок. Тогда рейтинг страницы A по PageRank определяется как
PR(A)= (1- d)+d(PR(T1 )/C(T1 )+...+ PR(Tn )/C(Tn )) .
Следует отметить, что PagRank определяет распределение вероятностей для каждой страницы таким образом, что сумма рейтингов PagRank всех страниц будет равна единице.
Рейтинг PageRank (PR(A)) может быть вычислен с использованием простого итеративного алгоритма и будет соответствовать главному собственному вектору нормализованной матрицы ссылок. Нужно отметить, что рейтинг PageRank для 26 миллионов веб-страниц может быть вычислен за несколько часов на рабочей станции средней мощности [42].
Алгоритм PageRank можно рассматривать как модель поведения пользователя. Предполагается, что веб-серфер (пользователь, «путешествующий» по веб-страницам, т.е. переходящий по ссылкам с одной на другую) с заданной случайным образом стартовой страницы переходит по ссылкам (также выбирая их случайным образом) на другие страницы и никогда не возвращается на предыдущую страницу, иногда прерывая переход по ссылкам и начиная снова с другой случайной страницы. Вероятность того, что веб-серфер посетит определенную страницу и является ее рейтингом PageRank. А коэффициент затухания d определяет, насколько скоро веб-серфер начнет процесс заново, перейдя на случайную страницу. Единственное важное различие в задании фактора d заключается в том, что он может быть присвоен как группе страниц, так и отдельным страницам. Данный подход позволяет персонализировать выборку и сводит к минимуму вероятность того, что система ошибется, присваивая странице рейтинг. Существует несколько расширений алгоритма Page Rank, описанных в [82].
Другое наглядное обоснование того, что страница может иметь высокий рейтинг PageRank, заключается в определении количества страниц, ссылающихся на нее и имеющих также высокий рейтинг PagRank. Таким образом, страницы, на которые ссылается множество документов в вебе, являются более предпочтительными. Также страницы, имеющие хотя бы одну ссылку, например, с домашней страницы Yahoo!, являются более предпочтительными. Если ссылка на страницу не работает или страница низкого качества, то маловероятно, что домашняя страница Yahoo! будет ссылаться на нее. PageRank анализирует подобные ситуации, а также рекурсивные ссылки нескольких страниц, посредством которых их владельцы пытаются повысить их рейтинг.
Так же, как и в ситуации с Всемирной Сетью, рост Семантического Веба будет обуславливаться развитием возможностей его применения. Семантический поиск – это процесс поиска информации, основанный на установлении соответствия между смысловым содержанием запроса и смыслом текста, представленного в документах целевого репозитория. Поиск является наиболее популярным направлением использования Веба, это область со значительными возможностями для улучшения. Семантический поиск пытается расширить и улучшить традиционные результаты поиска (основанные на технологиях извлечения информации) при помощи использования данных из Семантического Веба.
Семантический поиск – это также процесс, используемый для улучшения результатов онлайн-поиска посредством использования данных из разнообразных баз знаний для разрешения неоднозначности между поисковыми запросами и текстами электронных документов в целях получения более релевантных результатов [90]. М. Хильдебранд в своей работе[89] проводит обзор существующих поисковых систем (ПС) и выделяет некоторые другие возможности использования семантики в процессе поиска. Р.Гуха [67] выделяет два основных типа поиска информации: навигационный и исследовательский.
В случае навигационного поиска, пользователь использует ПС как навигационное устройство для перехода к конкретному документу, содержащему в себе текст поискового запроса. Семантический поиск не применим к навигационному типу поиска. При исследовательском типе поиска пользователь подает на вход ПС фразу, являющуюся описанием объекта, о котором пользователь пытается найти информацию. При этом не существует какого-то определенного документа, который ищет пользователь, напротив, он пытается найти некоторое множество документов, которые совместно предоставят ему информацию об объекте интереса поискового запроса. Процесс семантического поиска очень широко применяется в данном типе поиска. В отличие от ранжирующих алгоритмов наподобие PageRank для определения релевантности, семантический поиск использует семантику, науку о значениях языковых конструкций, для предоставления результатов поиска наибольшей релевантности. В большинстве случаев целью поиска является предоставление пользователю информации, запрошенной им, вместо того, чтобы предоставлять пользователю список плохо взаимосвязанных результатов поиска по ключевым словам.
Первичные информационные единицы для разработки алгоритма анализа аспектно-ориентированных запросов
Как отмечалось выше, аспектно-ориентированными запросами (АО-запросами) будем называть вопросительные предложения, в которых запрашивается информация о различных аспектах того или иного объекта или системы: характеристиках, условиях существования или функционирования, назначении, структурной организации, функциях, области применения, принадлежности к какому-либо классу, отличиях, особенностях и возможностях различных объектов и систем.
Когда запрашивается информация о том или ином аспекте какого-либо объекта, то, во-первых, необходимо учитывать тип этого аспекта, а во-вторых, специфику объекта, которому принадлежит этот аспект. Другими словами, типизация аспектов является универсальной, а непосредственно значения аспектов — уникальными для объекта, о котором идет речь в запросе. В параграфе 2.3.2 предлагается 11 типов запросов, на взгляд автора, полностью покрывающих информационные потребности пользователей, пытающихся найти информацию об аспектах тех или иных объектов. Данным типам запросов будут строго соответствовать определенные типы аспектов.
Пример 1. Запросу “Каково устройство модема?” соответствует тип “Описание структуры”. Объектами интереса являются слова “устройство” и “модем”, причем характеристическое слово “устройство” является индикатором типа аспектов объекта “модем”. Для данного вопроса аспектами объекта интереса будут являться характеристики, описывающие его (объекта) устройство (структуру).
Для расширения поискового АО-запроса необходимо определить тип аспекта, о котором запрашивается информация. Анализ разнообразных входных запросов показал, что это можно сделать, обнаружив в запросе специфическое слово-индикатор (характеристическое слово) или проанализировав структуру запроса.
Пример 2. В запросе «Каковы особенности планшета Apple?» присутствует характеристическое слово «особенности», что позволяет определить тип запроса (а, соответственно, и аспекта) «Описание особенностей».
Пример 3. В запросе «Для чего нужен осциллограф?» отсутствуют слова-индикаторы, характерные для какого-либо типа запроса, однако структура запроса позволяет сделать вывод о том, что типом данного запроса является «Описание назначения».
Основной принцип расширения АО-запросов заключается, во-первых, в построении семантических производных первоначального запроса. Для преобразования такого рода необходимо учитывать концептуальное окружение характеристического слова, специфическое для определенного типа запроса, т. е. его синонимы, гипонимы и гиперонимы. Данное окружение позволит строить семантически близкие запросы, а также анализировать возвращаемые документы на соответствие запросу. Кроме того, необходимо учитывать непосредственно значения аспектов, характерных для того или иного объекта.
Пример 4. Объектом интереса запроса «Каковы характеристики компьютера Lenovo?» является «компьютер Lenovo», а аспектами, соответствующими понятию «компьютер», могут быть производительность, тактовая частота, объем памяти и т. д.
Наличие описания аспектов для понятий, характеризующих объекты интереса, обусловлено тем, что необходимо анализировать возвращаемые поисковой системой документы на присутствие в них информации о непосредственно аспектах, что позволит ранжировать документы по количеству релевантных запросу аспектов, находящихся в них.
Таким образом, необходимо разработать математическую модель, учитывающую типы аспектов, их концептуальные окружения и множество значений аспектов для каждого типа.
Для представления различных типов аспектов необходимо ввести реляционные символы, строго соответствующие тому или иному типу аспекта объекта или системы. Были выделены 11 основных типов, и для каждого из них введен специальный символ, обозначающий бинарное отношение. Рассмотрим данные символы, их смысл и пример вопроса, в соответствие которому может быть поставлен определенный реляционный символ (под X и Y будем понимать объекты интереса поискового запроса, если не указано другого):
(1) ОП_СТР – символ для представления содержания вопросов вида «Как устроен X?». Пример: «Как устроен двигатель внутреннего сгорания?»;
(2) ОП_ХАР – символ для представления содержания вопросов вида «Каковы характеристики X?». Пример: «Каковы характеристики автомобиля Mercedes ML 350?»;
(3) ОП_РАБ –символ для представления содержания вопросов вида «Как работает X?». Пример: «Как работает аппарат магнитно-резонансной томографии?»;
(4) ОП_ФУН – символ для представления содержания вопросов вида Каковы функции X?». Пример: «Какие функции выполняет сервер локальной сети?»;
(5) ОП_НАЗ – символ для представления содержания вопросов вида «Для чего предназначен X?», «Каково назначение X?». Примеры: «Для чего предназначен реостат?», «Каково назначение межкомпьютерной связи?»;
(6) ОП_ПРИМ – символ для представления содержания вопросов вида «Где используется X?», «Как применять X?». Примеры: «Где используется Java?», «Как применять активную XSS?»;
(7) ОП_ПРИН – символ для представления содержания вопросов вида «К какому классу принадлежит X?», «К какой категории относится X?». Пример: «К какому классу соединений относятся жиры?»;
(8) ОП_РАЗ – символ для представления содержания вопросов вида «Чем отличается X от Y?», «В чем разница между X и Y?». Примеры: «Чем отличается архитектура x86 от x64?», «В чем разница между процессорами Dual Core и Core 2 Duo?»;
Разработка алгоритма определения типа вопросов достижения целей и их объектов интереса
Рассмотрим более подробно структуру и конкретные примеры входных запросов, представленные в таблице 3.3. При рассмотрении будут использованы шаблоны стем-формы, описанные в параграфе 2.6.При анализе и разборе структуры запросов достижения целей используется принцип, основанный на использовании словарей специфических слов индикаторов, описанный в параграфе 2.9. Для определения типа запроса происходит анализ каждого слова запроса на соответствие записям в словаре. Запрос представляется в виде массива элементов, имеющих тип Расш_Слово. Определение типа запроса происходит при помощи проверки вхождения базовой формы одного из слов запроса в словарь с элементами типа ХС. Полный список записей находится в приложении 3. Рассмотрим записи словаря, соответствующие запросам достижения целей (Таблица 3.4):
Из соображений целостности, определение типа данного запроса может быть интегрировано в алгоритм «Опр_ТЗ», описанный в параграфе 2.8.1. Для этого необходимо дополнить список типов запросов, поступающих на вход алгоритма, типом В_ДЦ и добавить дополнительную проверку в главный цикл алгоритма. Данный фрагмент будет выглядеть следующим образом: ... если Допуст_Типы(j) ==если Вхождение_слова_в_словарь( Запрос(i)::Баз_Формы, Словарь::Получить_Словарь(В_ДЦ, ХС)) Тип_Запр := В_ДЦ выход цик кесли кесли
Таким образом, при наличии словаря, содержащего слова-индикаторы для запросов достижения целей, происходит дополнение алгоритма «ОпрТЗ» возможностью определять тип запроса достижения целей.
Спецификой запросов достижения целей является присутствие указания на временной период, который интересует пользователя. Т. е. пользователя интересуют успехи, либо неудачи компании за конкретный период. Для этих целей был разработан подалгоритм «Определение_ Даты», описание которого доступно в приложении 4.
Рассмотрим алгоритм получения объектов интереса запроса. Внешняя спецификация алгоритма «Разбор_ЗапросаДостижения_Целей»
Назначение: Алгоритм предназначен для разбора запроса достижения целей. В алгоритме используется обращение к подалгоритму «Определение Даты», описанному выше. Передача входных параметров в данный подалгоритм будет производиться в скобках после названия алгоритма в том же порядке, в котором они описаны в его спецификации.
Вход: Запрос — массив элементов типа РасшСлово, представляющий входной запрос; Словарь_Доп_Слов — словарь допустимых слов-индикаторов; Словарь_Запр_Слов — словарь незначимых слов-индикаторов, т. е. продукций пустых цепочек.
Выход: Отличит_Слово — слово-индикатор, по которому был определен тип запроса, имеет тип Расш_Слово; ОИ — массив элементов типа Расш_Слово, представляющий объект интереса. Объект интереса может состоять из нескольких слов, поэтому все они должны быть возвращены как значимые; Дата — массив элементов типа Расш_Слово, содержащий информацию о дате, относительно которой запрашивается информация по успехам либо неудачам.
Преобразование происходит при помощи правил трансформации, уникальных для каждого из фактов. В правиле трансформации указываются порядок слов в результирующем словосочетании, а также их формы. На основании хранимых в базе фактов и соответствующих правил трансформации генерируются словосочетания, которые позволят системе поиска по ключевым словам найти документы, содержащие в себе упоминания данных фактов. После того, как множество словосочетаний-индикаторов сформировано, оно передается на вход синтаксической поисковой системе, которая осуществит отдельный поиск по каждому из них. Множество результирующих документов, возвращенных поисковой системой (ПС), будет проанализировано с точки зрения количества вхождений различных словосочетаний-индикаторов, т.е. указателей на присутствие упоминания того или иного факта в документе. Релевантность документов будет определяться, во-первых, по количеству вхождений различных фактов, а во-вторых, по рейтингу документа, определяемому алгоритмом используемой ПС. Отсортированные по релевантности первоначальному запросу документы затем будут переданы пользователю.
Метод порождения результирующих индикаторов.
1.По входному запросу находится информационная единица Studied-object, обозначающая объект интереса запроса.
2. По шаблону вида (3.2) строится цепочка X Y Z.
3. В цепочке X Y Z символ #A# заменяется на произвольную лексическую еди ницу, которой соответствует информационная единица Studied-object.
Разработка итогового алгоритма построения расширенного множества запросов и ранжирования результатов
В предыдущих главах упоминались алгоритмы извлечения данных из аспектно-ориентированной базы знаний, лингвистической базы знаний, а также из базы целей и базы множеств. Данные подалгоритмы, используемые в основных алгоритмах расширения запросов, представляют собой обращения к веб-сервису, который осуществляет выборку из базы данных, либо непосредственно к самой базе данных. В таблице 4.5 приведены ссылки на исходный код алгоритмов для ознакомления с тем, каким образом данные извлекаются из базы данных.
Рассмотрим итоговый алгоритм анализа и расширения поисковых запросов аспектно-ориентированного типа, вопросов достижения целей и вопросов изменения состава множеств.
Внешняя спецификация алгоритма «Анализ_и_Расш_Запр» Вход: Текст - Цепочка We Linput - входной запрос; Словарь_Старт_Слов — словарь стартовых слов, содержащий типы запросов, которые могут начинаться с того или иного слова; РассмТипы — массив, содержащий строки, соответствующие всем типам запросов
Выход: ExtSet — множество семантически преобразованных запросов.
Внутренние переменные: Тип_Запр — тип запроса; Допустимые_Типы — массив, содержащий строки, соответствующие типам запросов; Отличит_Слово — слово-индикатор, по которому был определен тип запроса; ОИ — массив элементов типа Расш_Слово, представляющий объект интереса; ОИ2 — массив элементов типа Расш_Слово, представляющий второй объект интереса; Доп_ОИ — дополнительный значимый объект интереса, влияющий на смысл запроса.
Алгоритм ранжирования результатов в силу его простоты не приводится. Алгоритм определяет релевантность следующим образом: итерируя по массиву возвращенных поисковой системой документов, алгоритм сначала определяет наличие объектов интереса в представленном системой сниппете, а затем определяет повторные вхождения одного и того же документа в выборку, используя в качестве уникального ключа URL страницы. Если было обнаружено повторное вхождение, то повышается рейтинг документа, который уже содержится в выборке. После этого полученное множество сортируется по значению данного рейтинга.
Разработанный программный комплекс в настоящее время развернут и функционирует. Доступ к подсистемам можно получить по следующим URL-адресам (таблица 4.7):
Необходимо исследовать полученные результаты разработки метода преобразования поисковых запросов различных типов (аспектно-ориентированные запросы, запросы о достижении целей, запросы об изменениях в составе множеств). Для этого необходимо, во-первых, провести тестирование алгоритмов определения типа, объектов интереса запроса и построения множества преобразованных запросов ExtSet. Во-вторых, необходимо проанализировать работу комплекса AOS Engine с точки зрения возвращаемых результатов поиска, тем самым определив работоспособность разработанного метода и комплекса программ, реализующего данный метод. Следует отметить, что исходный код комплекса прошел интеграционное тестирование, и все компоненты и подсистемы комплекса взаимодействуют корректно.
Для тестирования алгоритмов определения типа и объектов интереса поисковых запросов было выбрано множество запросов, которые принадлежат формальному языку входных запросов Linput.
Тестирование алгоритмов определения типа и объектов интереса поисковых запросов производилось методом белого ящика в автоматическом режиме при помощи библиотеки тестирования JUnit. Было сформировано множество из более чем 300 уникальных поисковых запросов различных типов, элементы которого последовательно подавались на вход алгоритмам, затем средствами фреймворка JUnit производился анализ соответствия результатов работы алгоритма ожидаемым. Из соображений компактности листинг результатов не приводится, однако множество запросов и логика тестирования доступны в исходном коде комплекса. В таблице 4.8 приведены классы, в которых производится тестирование, и их назначение.
