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

На правах рукописи

005017226

Колосов Алексей Павлович

МАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ [ЮЛНОТЕКСТОВОГО ПОИСКА В БАЗАХ ДАННЫХ НА ОСНОВЕ КОНЦЕПТУАЛЬНОГО МОДЕЛИРОВАНИЯ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 0 ['?"С"1

Тула 2012

005017226

Работа выполнена в ФГБОУ ВПО «Тульский государственный университет»

Научный руководитель:

доктор технических наук, доцент Богатырев Михаил Юрьевич

Официальные оппоненты:

Есиков Олег Витальевич,

доктор технических наук, профессор,

ФГУП «Научно-исследовательский институт

репрографии», советник по информатизации

Рыжков Евгений Александрович, кандидат технических наук,

ООО «Системы программной верификации», генеральный директор

Ведущая организация:

ФГБОУ ВПО «Российский государственный педагогический университет им. А.И. Герцена»

Защита состоится « мая 2012 г. в час. СО мин. на заседании диссертационного совета Д 212.271.07 при ФГБОУ ВПО «Тульский государственный университет» (300012, г. Тула, проспект Ленина, 92, 9-101)

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Тульский государственный университет».

Автореферат разослан « ^ » апреля 2012 г.

Учёный секретарь Данилкин Федор

диссертационного совета — " Алексеевич

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы исследований. Полнотекстовые базы данных играют все ¡олее важную роль в современных информационных ресурсах. Поэтому совершенствование математического и программного обеспечения полнотекстовых баз данных является одним из ключевых направлений развитая индустрии программирования. В рамках данного направления решение задач полнотекстового

поиска имеет принципиальное значение.

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

ключевых слов в документах базы данных.

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

является чрезвычайно актуальной задачей.

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

моделях текстов. ' . , „

Результаты, полученные в работе, опираются на известные ранее результаты в области информационного поиска, отраженные в работах россиис^х СН-Н Леонтьева, С.О. Кузнецов, А.Е. Ермаков) и зарубежных (Д.вомя, 8.Ви«с1гег, З.ЯоЬеНБОп) исследователей, и ориентированы на практическое применение в программном обеспечении полнотекстовых баз данных.

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

™ЬШ диссертационной работы является повышение точности решения

задач полнотекстового поиска в базах данных.

Поставленная цель достигается решением следующих задач. „„„„„„

1. Формализация задачи _ полнотекстового поиска с применением

концептуальных графовых моделей.

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

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

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

5. Разработка инструментального ПО системы полнотекстового поиска и е интеграция в существующие информационные системы.

6. Экспериментальная проверка эффективности разработанных алгоритмов и и; сравнение с существующими аналогами.

7. Разработка технологии полнотекстового поиска, реализующе] разработанные алгоритмы для конкретной СУБД.

Методы исследований. Основные результаты работы получены < применением методов обработки естественного языка, математической логики ] концептуального моделирования. Программные решения для систем техническоГ поддержки реализованы в парадигме объектно-ориентированног«

программирования.

Основные научные результаты диссертационной работы заключаются 1 следующем.

1. Показано, что применение концептуальных графов в качестве семантическоГ модели полнотекстовых запросов в инструментальном ПО полнотекстового поиск; обеспечивает извлечение из текста запроса словосочетаний, независимо от близосп слов в них.

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

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

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

Результаты данной работы получены при выполнении следующих научных проектов:

- гранта РФФИ, № 11-07-97542-р_центр_а,

- проекта, поддержанного Фондом содействия развитию малых форм предприятий в научно-технической сфере, госконтракт № 9444р/15234.

Практическая значимость результатов работы состоит в следующем.

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

2. Разработанное программное обеспечение позволяет снизить время получения ответа для пользователей систем технической поддержки, форумов и других =ob" осПвяГнньК ответам на вопросы, сформулированным в виде текстов на е^ГшГом языке, благодаря автоматическому поиску документов, которые могут

С°Т^РХ«стема полнотекстового поиска может быть и=Ров-с любыми информационными ресурсами: корпоративными ^^"итп ™ знаний, электронными библиотеками, системами техническом поддержки и т.шчто расширять возможности существующих систем в области

~л~я~с„мь1е на защиту. На защиту выносятся следующие

2 мГод выделения ключевых словосочетаний из текстов на естественном

языке использующий концептуальные графы для моделирования смысла текстов^ языке, и™^ полнотек^вого поиска, запросы для которого представляются

в виде множества словосочетаний. ,„,-, „„Кп™ Разпаботана

Реализация и внедрение результатов Д„ссертаиио„нои рабо™ РазраМ система полнотексгового поиска, которая внедрена в системе технической ~ки ООО «Автоматизированное обеспечение качества»,

wtBearSoftware и применяется на сайте компании. Система полнотекстового

программное обеспечение для разработки документации рщрабатьшаемое в ООО «Тульский Стандарт», что подтверждается актами о

"Te^bTaTb! диссертационного исследования внедрены в У-бныи процесс на кафедре Автоматики и телемеханики ТулГУ в лекционные курсы «Сетевое программирование», «Базы данных и знаний» и их лабораторный практикум профаммир , Основные результаты работы докладывались на

меж™дн х и всероссийских научно-технических конференциях, совещаниях и =ГГ,я международная конференция по распознаванию образов и семинарах, ь по^д, 9n,, _ Pattern Recogntion and Machine

20 Г2.21з!я всероссийская «Тучная конференция

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

коллекции», Россия, Воронеж, 2011. 3. 14-я всероссийская «

.20по ™е лиссертапиониого —д»7а печатных работ, в том числе 3 рекомендованных ВАК РФ, получено два

5 таблиц и 27 рисунков. Сооош » ввелешя, I» ™а», ST,e"™. »иска литературы ю 101 наименован», и 4 приложении.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

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

ДРУГИМ задачам 0™0сятся алгоритмическое и программное обеспечение полнотекстового поиска, реализация подсистемы полнотексгового поиска в

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

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

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

полнотекстового поиска.

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

птагккс (^агёвс^)

какой-то виртуальный другой?

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

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

идентификации словосочетаний.

Логическая модель концептуального графа строится как дизъюнкция

конъюнктивных форм вида:

<2(Л.....х„)(Рс(*і) А ...АРсЫЛЛ^РЛхиХ»,

где (¡(.х^-.хп) - сочетание кванторов переменных х1,...,х„ , соответствующих концептам графа, Рс(х() - предикат, соответствующий /-му концепту, Рг(х£,х;) -предикат соответствующий отношению, связывающему концепты /, ], п - число концептов в графе, т - число отношений. Данная форма соответствует каждому связному подграфу несвязного концешуального графа. Если граф связный, то он полностью задается указанной формой.

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

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

Алгоритм построения концептуального графа состоит из четырех этапов:

• языковой анализ - определение языка представленного текста;

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

• морфологический анализ - определение морфологических признаков элементов предложения;

• концептуальный анализ - выделение концептов из элементов предложения, определение отношений между концептами.

Алгоритмические решения для этапов 1-3 известны. В частности, известны достаточно надежные морфологические анализаторы текста. Четвертый этап алгоритма - наиболее сложный и наименее разработан в настоящее время. В работе новые программные решения предлагаются именно на данном этапе.

Каждый элемент текста представляется в виде тройки вида:

и/ = (ЛЛи>,

где у/ - элемент текста, в исходном варианте соответствующий морфологическому словарю IV*, /- естественная форма элемента текста, N - нормализованная форма элемента, А - список морфологических атрибутов элемента. Упорядоченная последовательность элементов текста представляется в следующем виде:

где Рп - последовательность элементов текста длиной п, - текстовый элемент, при ЭТОМ элемент И>/ предшествует элементу М>р если <</.

Для построения концептов и отношений применяются грамматические шаблоны. Каждый шаблон представляется в виде четвёрки:

где Р/1 - последовательность текстовых элементов длиной «для сравнения, С -список относительных атрибутов, с1 - действие (из набора действий £)'), применяемое к фразе, найденной в тексте и подходящей к шаблону, щ - длина фразы (число текстовых элементов в шаблонной фразе).

Формируется функция сравнения, которая сопоставляет шаблон с выбранной последовательностью элементов текста. Определяется функция сравнения следующим выражением:

( п = щ

| рп п РГ = рр

({Л; 6 с} П {л е и/;} = {лу е С} п {л е IV;}, £ = 1.. п,у = 1.. п

где rt - число элементов исследуемой текстовой последовательности, ns - число элементов последовательности шаблона сравнения, Р„ - исследуемая последовательность элементов текста, Ац - список атрибутов для сравнения i и j элемента исследуемой последовательности.

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

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

Словосочетания из текста запроса к системе предложено извлекать из концептуальных графов, строящихся на тексте запроса. Условие выбора концептов С; и Cj из графа в качестве части словосочетания, являющегося Диграммой, формулируется в виде выражения импликации: с£ й Ws A cj g WS,WS с

г е G(q) Are G{cj) ^ => t(ct, Cj) type (г) = attribute J где Ws — множество шумовых слов (стоп-слов), определяемое словарем, г — вершина отношения, связывающего концепты С£ И Cj , type (г) — тип отношения, С(с£) -множество вершин, связанных с вершиной с£. Объединение пары существующих множеств Г£ и 7} делается в случае, когда выполняется следующее выражение импликации:

ft(c£<Cy))

{ ct er£ \ ^ join(Ti,Tj) Uj^tJ

Предложено производить добавление нового концепта с£ к существующему словосочетанию 7} в случае, если верно следующее выражение импликации:

j CjSTj !• => add{ci,Tj)

UerJ

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

Т = (A, t2,..., tn}, tt g Ws, i = 1,2,..., n Vt£3ty: t(c£ = tu Cj = tj) A ref{c{) < ref(cj), i < j где t£ — i-oe слово из упорядоченного множества слов Т, представляющего словосочетание, выделенное из запроса. Сортировка слов в словосочетаниях в

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

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

обработку знаков препинания.

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

следующем виде:

е Вт

рох^.!) + е бц,

РОБ^.Ь^ = - р05(н'(_1) + Де Вр роз{и/£_!) + Д5, Ь] е В3

и, I=1

где ро5(1У(_1) - позиция предыдущего слова, вычисленная ранее, Вт, В„, ВркВ1-множества символов-разделителей, принадлежность к которым символа-разделителя Ь} определяется с помощью регулярных выражений, аАт, Д1У, Др и Д5-параметры метода, соответствующие различным классам символов-разделителей.

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

С 71,- =тг,П/ = |И^|,тг= |Т| ^

] иъ е сИс^кХ = тЩ. Т)

I. Р05(иъ) - р05(мк-{) < Д5 )

где - упорядоченное множество слов из документа, Т - упорядочение множество слов, т.е. словосочетание из запроса СЦТе <?), ¿¿сС(рк) - все формы к того слова из словосочетания Т, полученные с помощью словаря, ро5(иъ) - позици; /с-того слова из \l\fj относительно начала документа, А3 - константа, характеризующа; величину искусственного увеличения позиции слова после конца предложения.

Предложено релевантность каждого поля документа вычислять для парь где Q - множество словосочетаний из запроса, каждое словосочетани описывается парой (Т¡,иГ()е<2, а О, - проиндексированный документ из базь данных.

11гии((2.0])=-N-= "21

где Г; - словосочетание из запроса (), иТ[ - вес этого словосочетания, а Ят(ТиО^ -релевантность поля документа Dj словосочетанию из запроса, которую предлагается вычислять по следующей формуле:

"тп к=1

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

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

Zs(wl,tl)

где рох(и/;) — позиция 1-того слова из документа, соответствующего 1-тому слову из искомого словосочетания, 5(и/;, £г) — вес 1-того слова из документа, вычисляемый в зависимости от степени совпадения формы слова в запросе и в документе.

Функция 5(и7;, С;) представляется в следующем виде:

(Ч Щ = Ц

(о, IV; £ сИаСь)

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

и,

£=1

где Л^ — общее количество проиндексированных полей (в текущей реализации равно 2), щ — вес проиндексированного поля.

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

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

Архитектура разработанной поисковой подсистемы представлена на рисунке 2.

База данных

Новые, измененные, удаленные документы

Новые индексы i

Результаты запросов

Запросы

Модуль взаимодействия с базой данных

Обновляемые I индексы :

Новые слова

Модуль индексирования

Информация о статусе Лексемы индексирования из текстов

Информация о словах

: Словарь форм слов

Информация о формах слое

Запросы индексов

!

Информация основах

Подматрицы индексов

Модуль обработки I текстов

Запросы пользователей

Модуль поиска

Запросы пользователей

П

3

SQL-запросы для булевского поиска лексемы из отношений

Запросы .................

пользователей

Информация о словах

Словосочетания

Модуль обработки словосочетаний

Результаты поиска

Тексты

і запросов Модуль построения

: Отношения графов

из КГ

Рисунок 2 — Архитектура поисковой подсистемы.

Подсистема имеет следующие модули.

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

2. Словарный модуль обеспечивает обновление словаря и получен! информации о словах (в частности, о связях между различными формами одного того же слова) по полученным из текста лексемам.

3. Модуль обработки текстов производит чтение документов различнь поддерживаемых форматов (TXT, XML, HTML), разбиение текстов на предложени а предложений - на лексемы, после чего лексемы заменяются на слова из словар для каждого такого слова вычисляются, с учетом знаков препинания, его позиции тексте.

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

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

6. Модуль поиска принимает запросы пользователей системы и возвраща отсортированные в порядке уменьшения релевантности документы, релевантю

заданному запросу.

Разработанные программные модули (язык С#, СУБД Microsoft SQL Ser\ 2008 R2, технология LINQ) предназначены для использования в любой вере; операционной системы Windows, поддерживающей платформу .NET. Проведено внедрение в систему технической поддержки компании SmartBear Software с цел-

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

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

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

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

Результаты экспериментов приведены в табл. 1.

Табл. 1. Результаты экспериментов по оценке качества выделения словосочетаний

Алгоритм Словосочетаний Всего Среднее Правильных Всего Среднее Точность Полнота F-мера

Новый

Attribute, п-граммы, с фильтрацией стоп-слов 6 406 12,8 2 240 4,5 35,0 45,8 39,7

Attribute, п-граммы 6517 13,0 2 256 • 4,5 34,6 46,2 39,6

Attribute, биграммы 7 851 15,7 1 793 3,6 22,8 36,7 28,1

Все отношения, биграммы 20 389 40,8 1 927 3,9 9,5 39,4 15,2

TextRank

Undirected, window=2 6 784 13,7 2 116 4,2 31,2 43,1 36,2

Directed, forward, windovv=2 6 662 13,3 2 081 4,1 31,2 42,3 35,9

Hulth

Ngram with tag 7815 15,6 1 973 3,9 25,2 51,2 33,9

NP-chuncks with tag 4 788 9,6 1421 2,8 29,7 37,2 33,0

Pattern with tag 7 012 14,0 1 523 3,1 21,7 39,9 28,1

Сравнение проводилось с алгоритмом с обучением (НиНИ) и алгоритмом без обучения (ТехШапк). Оба алгоритма опираются при выделении словосочетаний на

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

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

Для полнотекстового поиска использовалась опубликованная в сети Интернет справочная документация к продуктам компании БшаЛВеаг и еще одна оценка релевантности: пйСО, учитывающая позицию результата в выдаче. Вычисляется величина пИСй по следующей формуле:

rell

nDCGp =

rel1+X Ulog2i

, yp rmax Tmax "r¿.¿=2iog2£

lreL = 0,.2,p=Í..N,rmax = 2

где ге^ — оцененная асессором релевантность г'-того результата, р - количество результатов поиска, гтах - максимально возможная величина релевантности.

График, показывающий изменение средней величины пОСС в зависимости о-количества оцененных запросов представлен на рис.3(вертикальная ос] соответствует среднемузначению пРСО, горизонтальная - количеству запросов):

0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 о

10 20 30 40 50 60 70 80 90 100

- Новый алгоритм * SQL Server ¡FTS

»Google

Рис.3. Зависимость величины пйСй от количества поисковых запросов

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

В диссертации для обобщенной оценки качества всего алгоритма в цело] использовалась база данных аннотаций технических статей, разделенны экспертами по тематикам. Для оценки качества алгоритмов использовалась мер Р@М (точность N наиболее релевантных результатов поиска), значения N бралис равным 5, 10 и 15 соответственно. Каждая статья корпуса поочередно выступала качестве запроса, релевантными документами для которого считались статьи из то же тематики.

Результаты проведенного эксперимента приведены в табл.2.

Табл.2. Величина P@N для четырех сравниваемых алгоритмов

Алгоритм

Р@10

Р@15

Іовьм алгоритм

74,3%

69,4%

64,3%

'ATeR

65,8%

53,3%

42,7%

:tr

60,7%

50,4%

41,3%

66,0%

53,9%

43,1%

Показано, что предлагаемый алгоритм дает на данной выборке существенно )лее качественные результаты, чем другие аналогичные алгоритмы. Так точность лделения словосочетаний по предлагаемому алгоритму превзошла точность ¡вестного алгоритма TextRank, лежащего в основе недавно разработанного эискового алгоритма PATeR, поэтому и точность поиска предлагаемого алгоритма сазалась выше. Аббревиатуры CTR и TP обозначают два других алгоритма, шяющихся модификациями алгоритма Okapi ВМ25,в которых при вычислении ;левантности учитывается меньшее количество факторов, чем в разработанном 1горитме. Стоит также учесть более сложное условие плавающего контекстного «на, основанного на искусственном увеличении позиций слов в документах, что исже является усовершенствованием по отношению к существующим алгоритмам.

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

В заключении сформулированы основные результаты и выводы по работе.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

5. На основе экспериментальных исследований подтверждена эффективность редложенных алгоритмов.

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

7. Результаты диссертационной работы внедрены в практическое спользование в ООО «Автоматизированное обеспечение качества», тульский 1илиал компании SmartBear Software.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. М. Bogatyrev, А. Kolosoff Using Conceptual Graphs for Text Mining in Technical Support Services // Pattern Recognition and Machine Intelligence 4th International conference, PReMI 2011. Proceedings. LNCS, vol. 6744. SpringerVerlag. Heidelberg, 2011.—p.p. 466-473

2. Колосов А.П. Выделение словосочетаний из текстов при помощи концептуальных графов // В мире научных открытий. Красноярск: НИЦ, 2012. №1.1(25).-с. 181-191

3. Колосов А.П. Алгоритм полнотекстового поиска с обучением на основе статистических данных // Известия ТулГУ: Технические науки. Вып. 6. Ч. 2 Тула: Издательство ТулГУ, 2011. -с. 462-471

4. Колосов А.П., Богатырев М.Ю. Алгоритм полнотекстового поиска по длинным запросам // Труды XIII Всероссийской научной конференции RCDL'2011. Воронеж: Издательско-полиграфический центр Воронежского государственного университета, 2011.-с. 151-157

5. Колосов А.П., Богатырев М.Ю. Полнотекстовый поиск в порталах технической поддержки // Интернет и современное общество: сборник тезисов докладов. СПб: МультиПроджектСистемСервис, 2011. — с. 57-62

6. Колосов А.П., Николаев Д.С., Муравьев А.Н. и др. Библиотека полнотекстового поиска с обучением на основе статистических данных, использующая гибридный алгоритм поиска // Свидетельство о государственной регистрации программы для ЭВМ №2011612246. РОСПАТЕНТ 17.03.2011

7. Колосов А.П., Николаев Д.С., Муравьев А.Н. и др. ClickHelp, веб-приложение для разработки документации // Свидетельство о государственной регистрации программы для ЭВМ №2012613286. РОСПАТЕНТ 6.04.2012

Изд. лиц. ЛР №020300от 12.02.97. Подписано в печать 18.04.2012г. Формат бумаги 60x84 l/iS .Бумага офсетная. Усл. печ.л .0,93 Уч.-изд.л. 0,8 Тираж 100 экз. Заказ 020 Тульский государственный университет 300012, г. Тула, пр. Ленина, 92 Отпечатано в Издательстве ТулГУ 300012, г. Тула, пр. Ленина, 95

61 12-5/3677

ФГБОУ ВПО «ТУЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

УДК 025.4.03

На щ пгиси

Математическое и программное обеспечение полнотекстового поиска в базах данных на основе концептуального

моделирования

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Колосов Алексей Павлович

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата технических наук

Научный руководитель д.т.н., доцент Богатырев М.Ю.

Тула, 2012

Оглавление

Введение.....................................................................................................................6

1 Системы полнотекстового поиска: состояние и актуальные задачи развития.. 13

1.1 Задача полнотекстового поиска....................................................................13

1.2 Обзор существующих алгоритмов...............................................................16

1.2.1 Теоретико-множественные модели.......................................................17

1.2.2 Алгебраические модели.........................................................................18

1.2.3 Вероятностные модели..........................................................................21

1.2.4 Свойства моделей...................................................................................24

1.2.5 Обработка словосочетаний....................................................................24

1.3 Применяемые модели и методы...................................................................28

1.3.1 Концептуальные модели и их применение...........................................28

1.3.2 Обработка структуры документов........................................................30

1.4 Постановка задач исследования...................................................................31

1.4.1 Особенности поставленной задачи.......................................................31

1.4.2 Задачи исследования..............................................................................33

Выводы к главе 1.................................................................................................35

2 Алгоритмическое и программное обеспечение поддержки концептуальных графов в информационных системах......................................................................36

2.1 Концептуальный граф как семантическая модель текстовых данных.......36

2.1.1 Определение концептуального графа...................................................36

2.2 Применение концептуальных графов для идентификации словосочетаний ..............................................................................................................................38

2.3 Алгоритм построения концептуальных графов..........................................40

2.3.1 Общий принцип построения концептуальных графов.........................40

2.3.2 Алгоритм концептнографического анализа..........................................43

2.3.3 Алгоритм формирования концептуального графа из элементов предложения....................................................................................................47

2.3.4 Инвариантность алгоритма относительно последовательности слов предложений....................................................................................................49

2.4 Применение концептуальных графов для идентификации словосочетаний ..............................................................................................................................51

Выводы к главе 2.................................................................................................56

3 Технология концептуального моделирования для извлечения словосочетаний в системах полнотекстового поиска.......................................................................57

3.1 Разработка алгоритма индексирования документов с обработкой знаков препинания..........................................................................................................57

3.2 Применение концептуальных графов для идентификации словосочетаний в тексте.................................................................................................................65

3.3 Разработка алгоритма полнотекстового поиска с применением словосочетаний...................................................................................................73

3.3.1 Булевский поиск.....................................................................................73

3.3.2 Вычисление релевантности...................................................................77

Выводы к главе 3.................................................................................................86

4 Программная реализация технологии концептуального моделирования в

системе полнотекстового поиска............................................................................87

4.1 Архитектура системы....................................................................................87

4.2 Структура базы данных................................................................................89

4.3 Разработка модуля взаимодействия с базой данных...................................92

4.4 Разработка словарного модуля.....................................................................94

4.5 Разработка модуля индексирования.............................................................95

4.6 Разработка модуля обработки текстов.........................................................97

4.7 Разработка модуля обработки словосочетаний...........................................99

4.8 Разработка модуля поиска..........................................................................102

4.9 Пример применения разработанной технологии в системе технической поддержки.........................................................................................................104

Выводы к главе 4...............................................................................................110

5 Экспериментальные исследования технологии концептуального моделирования.......................................................................................................111

5.1 Задачи экспериментальных исследований разработанной технологии... 111

5.2 Организация экспериментальных исследований......................................112

5.3 Определение веса отношений.....................................................................114

5.4 Оценка качества выделения словосочетаний............................................117

5.5 Оценка качества вычисления релевантности............................................124

5.6 Выбор веса полей индексируемых документов........................................128

5.7 Выбор величин искусственного изменения позиций слов.......................132

5.8 Оценка качества алгоритма полнотекстового поиска...............................137

Выводы к главе 5...............................................................................................139

Заключение.............................................................................................................141

Список литературы................................................................................................143

Приложение А........................................................................................................154

Приложение А.1. Описания грамматических шаблонов, применяемых при построении концептуальных графов...............................................................154

Приложение А.2. Пример применения шаблонов при построении концептуального графа.....................................................................................161

Приложение Б........................................................................................................164

Приложение Б.1. Средние значения пОСО в эксперименте по оценке качества алгоритма ранжирования..................................................................................164

Введение

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

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

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

Применение полнотекстовых запросов требует учета семантики в

решении задачи полнотекстового поиска, что невозможно при традиционном

подходе, поскольку семантика полнотекстовых запросов не может быть описана

6

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

Результаты, полученные в работе, опираются на известные ранее результаты в области информационного поиска, отраженные в работах российских (H.H. Леонтьева [97], С.О. Кузнецов[95], А.Е. Ермаков [90]) и зарубежных (J.Sowa [74] [75], S.Buttcher [17] [18] [19], S.Robertson [48] [64] [65] [66] [67]) исследователей, и ориентированы на практическое применение в программном обеспечении полнотекстовых баз данных.

Объектом исследования является ПО систем полнотекстового поиска.

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

Целью диссертационной работы является повышение точности решения задач полнотекстового поиска в базах данных.

Поставленная цель достигается решением следующих задач.

1. Формализация задачи полнотекстового поиска с применением концептуальных графовых моделей.

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

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

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

5. Разработка инструментального ПО системы полнотекстового поиска и ее интеграция в существующие информационные системы.

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

7. Разработка технологии полнотекстового поиска, реализующей разработанные алгоритмы для конкретной СУБД.

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

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

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

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

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

4. Разработан эффективный алгоритм полнотекстового поиска, использующий в качестве запросов тексты на естественном языке с

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

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

Результаты данной работы получены при выполнении следующих научных проектов:

-грантаРФФИ, № 11-07-97542-р_центр_а,

- проекта, поддержанного Фондом содействия развитию малых форм предприятий в научно-технической сфере, госконтракт № 9444р/15234.

Практическая значимость результатов работы состоит в следующем.

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

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

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

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

1. Алгоритм индексирования документов с учетом знаков препинания.

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

3. Алгоритм полнотекстового поиска, запросы для которого представляются в виде множества словосочетаний.

Реализация и внедрение результатов диссертационной работы.

Разработана система полнотекстового поиска, которая внедрена в системе технической поддержки ООО «Автоматизированное обеспечение качества», филиале компании SmartBearSoftware, и применяется на сайте компании. Система полнотекстового поиска также внедрена в программное обеспечение для разработки документации, разрабатываемое в ООО «Тульский Стандарт», что подтверждается актами о внедрении.

Результаты диссертационного исследования внедрены в учебный процесс на кафедре Автоматики и телемеханики ТулГУ в лекционные курсы «Сетевое программирование», «Базы данных и знаний» и их лабораторный практикум.

Апробация работы. Основные результаты работы докладывались на международных и всероссийских научно-технических конференциях, совещаниях и семинарах: 1. 4-я международная конференция по распознаванию образов и искусственному интеллекту PReMI 2011 - Pattern Recognition and Machine Intelligence, Россия, Москва, 2011. 2. 13-я всероссийская научная конференция «Электронные библиотеки: перспективные методы и технологии, электронные коллекции», Россия, Воронеж, 2011. 3. 14-я всероссийская объединенная научная конференция «Интернет и современное общество» IMS-

2011, Россия, Санкт-Петербург, 2011. 4. Всероссийский семинар «Natural Language Processing», Россия, Санкт-Петербург, 2011.

Публикации. По теме диссертационного исследования опубликовано 7 печатных работ, в том числе 3 рекомендованных ВАК РФ, получено два свидетельства о регистрации программ для ЭВМ.

Структура и объем работы. Диссертационная работа изложена на 153 страницах, включает 5 таблиц и 27 рисунков. Состоит из введения, пяти глав, заключения, списка литературы из 103 наименования и 3 приложений.

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

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

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

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

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

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

Также приводятся описания параметров метода и в