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

• Колосов, Алексей Павлович
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Колосов, Алексей Павлович

Оглавление

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

Приложение А

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

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

Приложение Б

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

Введение диссертации (часть автореферата) на тему «Математическое и программное обеспечение полнотекстового поиска в базах данных на основе концептуального моделирования»

Введение

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

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

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

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

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

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

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 приложений.

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

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

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

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

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

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

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

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

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

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

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

1 Системы полнотекстового поиска: состояние и актуальные

задачи развития

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

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

Первые системы информационного поиска появились еще в 50-60-х годах прошлого века. В начале 90-х годов задача информационного поиска приобрела широкую популярность с появлением первых поисковых систем в Интернете [44]. К задачам информационного поиска относится поиск изображений, поиск документа по метаданным (например, по названию, автору, размеру) и полнотекстовый поиск. Основной задачей существующих поисковых систем, таких как Google, Yandex или Nigma, является именно полнотекстовый поиск, то есть поиск по всему тексту документов в некоем множестве документов с целью нахождения текстов, близких по смыслу к поисковому запросу.

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

1. Ввод поискового запроса на естественном языке через интерфейс поисковой системы.

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

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

Такие поисковые системы работают с множеством веб-страниц, для каждой из которых известны присутствующие на странице слова, заголовок страницы, дата последнего обновления и т.п., причем каждая поисковая система покрывает не более трети всех страниц в Интернете [70]. Каждая из этих систем использует свои алгоритмы полнотекстового поиска, причем результаты поиска по одному и тому же запросу в разных системах могут существенно различаться исследования показывают, что наиболее релевантные результаты, возвращаемые двумя различными системами, могут совпадать только на 12%, а результаты для трех поисковых систем - на 3% [2]. Алгоритмы, использующиеся доя поиска, являются коммерческой тайной разработчиков поисковых систем, а проблема поиска наиболее эффективного алгоритма остается актуальной и по сей день - одним из возможных решений, основанным на различиях между алгоритмами, является использование метапоисковых систем, собирающих и обрабатывающих результаты сразу с нескольких поисковых систем. Однако вне зависимости от алгоритма каждая современная поисковая система, как правило, решает следующие задачи:

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

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

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

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

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

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

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

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

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

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

16

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

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

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

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

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

частотной характеристике, зависящей от частоты возникновения слова в документе и обратной частоты документа [67]. При этом релевантность между запросом и документом оценивается на основе расстояния между векторами документа и запроса в Евклидовом пространстве слов, с учетом булевских операторов в запросе (для операторов И/ИЛИ применяются разные формулы).

Модель нечеткого поиска сочетает в себе расширенную булевскую модель и элементы теории нечетких множеств. В этой модели степень присутствия слова в документе или запросе (то есть координата по соответствующему измерению) не является константой и зависит от булевских операторов в запросе [33].

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

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

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

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

индексов, или некий внешний ресурс, такой как Л^огсПЧе! [56], описывающий отношения (в том числе иерархические) между различными словами.

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

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

являются частоты возникновения соответствующих слов в документах. После этого производится уменьшение ранга матрицы, при котором и выделяются связи между словами, формирующими понятия [6] [32]. Латентно-семантический анализ позволяет снизить негативный эффект двух главных ограничений булевских запросов: одно и то же значение, присущее разным словам (синонимию) и многозначность одних и тех же слов в разных контекстах (полисемию). Отметим, что два этих ограничения зачастую приводят к ошибкам в информационном поиске, поскольку авторы текстов и пользователи могут пользоваться различными словами для описания одних и тех же понятий [34]. Еще одной важной особенностью латентно-семантического анализа является тот факт, что он не требует наличия словарей для обработки текстов. При этом ЛСА оказался полезен для решения ряда задач, связанных с выделением понятий [30] [4], таких как выявление информации о связях между словами [37]. Помимо информационного поиска, латентно-семантический анализ применяется для кластеризации и классификации документов, выявления синонимов и многозначных слов, выявления понятий из текстов (что также применяется в информационном поиске), а также нахождения похожих документов вне зависимости от их языка (после анализа множества переведенных документов).

К проблемам латентно-семантического анализа можно отнести производительность, а также вопрос об оптимальном ранге матрицы, обеспечивающем наиболее качественное выделение понятий. Исследованию данного вопроса посвящен целый ряд работ [49] [13] [19] [46] [40]. Еще одним недостатком этого метода, характерным для всех статистических методов, являются возможные ошибки при выявлении связей между словами. Хотя латентно-семантический анализ считается лучшим алгоритмом для выявления латентных зависимостей внутри множества документов, слишком большое

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

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

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

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

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

Модель вероятностной релевантности также определяет релевантность документа к запросу как вероятность того, что документ окажется релевантным. Помимо этого предполагается, что часть документов в рассматриваемом множестве содержит ответ, который ищет пользователь. Считается, что документы, входящие в это множество идеальных ответов, являются релевантными запросу, а документы, не входящие в него - нерелевантными [63]. Отметим, что слова в данной модели опять же считаются независимыми друг от друга, что является существенным недостатком. Однако, именно на этой модели основывается популярное семейство алгоритмов Okapi (Okapi ВМ11, Okapi BMI 5 [64] и, наиболее известный из всех, Okapi ВМ25, а также его модификация, Okapi BM25F, учитывающая структуру документа [47]).

Модель неявного вывода была создана как попытка связать запрос и релевантный документ неким формальным отношением. Суть формализации заключается в операции логической импликации между документом d и запросом q с некоторым значением неопределенности. Это значение считается вероятностью логической импликации между документом и запросом [76]. Считается также, что запрос может быть интерпретирован как ряд утверждений об искомом документе. Задача поисковой машины заключается в том, чтобы выяснить, рассматривая соответствующий документ, соответствует ли он утверждениям, содержащимся в запросе. Если документ соответствует им, он включается в список результатов поиска. Во многих случаях содержимого документов оказывается недостаточно для того, чтобы провести такую оценку. Для этого требуется база знаний, содержащая факты и правила.

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

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

В модели скрытого распределения Дирихле каждый документ представляется в виде комбинации различных тематик. Данная модель основана на предположении о том, что некий набор наблюдений можно объяснить влиянием скрытых переменных. В частности, если считать наблюдениями набор слов в документах и считать, что каждый документ состоит из небольшого числа определенных тематик, то появление в документе тех или иных слов объясняется тематиками документа, к которым принадлежат эти слова. Считается, что распределение тематик в документах соответствует распределению Дирихле [36]. Для распределения тем по документам и распределения слов по темам применяются также и другие виды распределений [9] [57] [7], например, в иерархической версии данной модели возможные тематики формируют иерархию [8].

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

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

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

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

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

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

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

известный вес TF-IDF или алгоритм Okapi ВМ25 [38]). В них учитывается, как правило, частота появления слова в документе (TF) и обратная частота документа (IDF). Грамматика, пунктуация и даже порядок слов в таких алгоритмах полностью игнорируется. Такой подход зачастую оказывается оправдан для коротких поисковых запросов, состоящих из нескольких слов, если количество документов относительно невелико и/или вероятность нахождения нужного текста по одному только факту наличия в нем большого числа повторов искомых ключевых слов достаточно высока.

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

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

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

попадут в результаты поиска. Поэтому логичным представляется вычисление релевантности с учетом близости слов, при котором неточные совпадения получают меньший вес. Такой подход используется в некоторых существующих алгоритмах [16] [18] [24] [27] [58] [62] [71]. Для решения задачи поиска по словосочетаниям применяется индекс, хранящий информацию о позициях слов в тексте [79]. Также предлагалось использовать индексы специального вида, хранящие информацию о встречающихся в текстах парах слов и/или более длинных словосочетаниях [21] [77] [78].

Хотя выводы о связях между словами, как уже упоминалось ранее, делаются, как правило, на основании статистики совместного употребления слов, существуют и алгоритмы, использующие для этого графы. К таким алгоритмам относятся TextRank [54] [55] и основанный на нем алгоритм PATeR [3], которые будут подробнее описаны ниже. Отметим, что TextRank не предполагает моделирование смысла текста, а лишь помогает выявить наиболее вероятные ключевые слова, основываясь на данных о взаимном расположении слов. Информация о частях речи используется в нем лишь для фильтрации определенных частей речи (например, для включения в результаты лишь глаголов и существительных).

Наиболее известным из алгоритмов, использующих графы, и основой для TextRank (а также множества других алгоритмов) является PageRank [14] [1], применяющийся в поисковой системе Google. Данный алгоритм относится к вероятностным и не строит графов в явном виде, однако использует связи между документами (гиперссылки), которые могут быть представлены в виде графа, для определения индекса цитирования документа. Сегодня данный подход активно применяется в веб поиске, в частности, его используют две наиболее популярные поисковые системы - Google и Yandex.

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

В более поздних работах предлагается комбинировать релевантность по содержимому статей и по словосочетаниям [16] [24] [27] [58] [62] [71]. Такие подходы можно разделить на два класса. Первый класс алгоритмов использует линейную комбинацию релевантности по словосочетаниям (рассчитанной по минимальному размеру окна, в котором встречаются все искомые ключевые слова [58], или по расстоянию между парами слов, попадающих в окно фиксированного размера [62]) и ранга документа, полученного, например, по формуле, аналогичной Okapi ВМ25. Второй класс алгоритмов использует более целостный подход, в котором релевантность по словосочетаниям теснее интегрируется с рангом документа в выдаче, учитывая частоту возникновения искомых слов в документах [27] [24] или комбинацию этой частоты и релевантности, полученной по формуле, основанной на Okapi ВМ25.

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

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

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

Также размер запроса обусловливает необходимость фильтрации слов, не влияющих на смысл текста. Если системы веб-поиска могут позволить себе не фильтровать шумовые слова и использовать все слова запроса при поиске [52], то в случае длинных запросов такой подход оказывается крайне неэффективным - как с точки зрения скорости работы системы, так и с точки зрения вычисления релевантности, что подтверждается результатами проведенных экспериментов. Исключение из запроса шумовых слов, к которым обычно относятся предлоги, союзы, артикли и т.п., позволяет сократить длину запроса, однако при этом о связях между словами можно судить лишь по статистике, как, например, при латентно-семантическом анализе [51] что не всегда является эффективным. Качество анализа можно повысить за счет учета знаков препинания для выделения потенциально связанных слов и сужения контекстного окна (например, можно не считать связанными слова, если они следуют друг за другом, но находятся в разных предложениях [3]). Такой подход используется в

алгоритме индексирования: каждый проиндексированный документ представляется в виде матрицы М X Ы, где М - количество уникальных слов в документе, а ТУ- максимальное число повторов того или иного слова. С каждым словом ассоциируются его позиции относительно начала текста, вычисленные с учетом знаков препинания между словами, о чем будет подробнее рассказано позже.

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

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

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

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

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

В зависимости от конкретного формата текстовых данных, индексируемые документы, в том числе и сами запросы, могут быть разделены на несколько полей, имеющих различную важность. Например, аннотация научной статьи должна содержать краткое описание сути этой статьи, а название документа - отражать в нескольких словах его тему, то есть отвечать на вопрос «о чем документ?». Логично предположить, что такие поля должны иметь больший вес, чем сам текст документа. Такой подход уже применяется в существующих алгоритмах [68], наиболее известным из которых является Okapi BM25F [66] [65] [84] - модификация известной формулы Okapi ВМ25, дающая различный вес разным полям индексируемых документов. Подобный подход используется и при поиске в Интернете - различные поля (заголовки, присвоенные авторами ключевые слова, названия документов, тексты ссылок и т.п.) приобретают различный вес.

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

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

1.4 Постановка задач исследования 1.4.1 Особенности поставленной задачи

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

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

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

1. Общее количество документов относительно невелико (от нескольких десятков до нескольких сотен тысяч).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5. Экспериментальная проверка эффективности разработанных алгоритмов и настройка алгоритмов на основе реальных данных.

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

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

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

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

4. Поставлены следующие задачи исследования:

• Разработка нового алгоритма извлечения ключевых словосочетаний из текстов на естественном языке.

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

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

• Экспериментальная проверка эффективности разработанных алгоритмов и настройка алгоритмов на основе реальных данных.

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

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

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

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

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

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

Рисунок 1 - Концептуальный граф предложения «Студент читает книгу».

На рисунке 1 концепты графа показаны в виде прямоугольников, а отношения - в виде эллипсов. Отношения «агенс» и «пациенс» - это стандартные, известные из лингвистики, отношения [88]. Отношение «агенс» означает субъект действия - в данном случае это студент. Отношение «пациенс» означает объект, на который направлено действие - это книга. Само действие задается концептом «читать». Как видно из рисунка, этот концепт является основным - от него направлены стрелки ко всем остальным концептам. В данном случае в графе использована вербоцентрическая концепция [99], согласно которой смысл предложения в первом приближении моделируется глаголом. В концептуальном графе такому глаголу соответствует центральный концепт - концепт «читать» на рисунке 1.

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

Концептами, отношениями и их типами определяется семантика концептуальных графов. Кроме этого, семантика определяется той логикой связей, которая задается структурой графа. Поэтому, как показано в [74],

каждому концептуальному графу можно поставить соответствие логическое выражение. При этом аппарат логики предикатов первого порядка достаточен для моделирования семантики концептуальных графов [23].

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

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

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

словосочетаний

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

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

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

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

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

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

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

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

некотором тексте «студент-отличник» признается как словосочетание, то «человек-отличник» таковым уже не будет.

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

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

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

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

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

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

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

российская государственная библиотека

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

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

Кратко опишем алгоритмическую реализацию рассмотренных задач.

Языковой анализ. Определение языка производится на основе ASCII-кодов букв, входящих в исследуемый текст. Определение производится в два этапа.

Определение языка производится на основе ASCII-кодов букв, входящих в исследуемый текст. Определение производится в два этапа.

1. Находится среднее значение ASCII-кодов символов текста по следующей формуле:

N

с =

ф N

где с, - ASCII-код /-го символа, N - число символов в тексте, сср - среднее значение ASCII-кодов текста.

2. Если полученное число больше 128 (середина таблицы ASCII), то текст признаётся русским. В ином случае - английским.

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

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

Графематический анализ также состоит из двух этапов.

Сначала проводится разделение текста на элементы (слова и знаки пунктуации), производится отделение знаков пунктуации от слов.

После этого элементов текста объединяются в предложения. Отметим, что на этом этапе используются следующие предположения:

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

• предложение всегда начинается с большой буквы;

• размер предложения не может превышать одного абзаца;

• предложение не может состоять только из знаков препинания.

Морфологический анализ основывается на сопоставлении элементов

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

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

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

Грамматические шаблоны состоят из лексических элементов. Лексические элементы можно задавать разными способами, начиная от поэлементного перечисления слов и заканчивая предопределенными классами (например, класс слов с общими морфологическими признаками).

Список шаблонов формируется на основе известных грамматических шаблонов [85] с учетом их упорядоченности. Этот порядок соответствует порядку построения концептуальных отношений: от менее значимых к более значимым. Можно выделить несколько основных типов шаблонов:

• двухуровневый шаблон - проверяет два рядом стоящих элемента;

• трёхуровневый шаблон - проверяет три рядом стоящих элемента;

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

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

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

Минимальными элементами текста в данном алгоритме являются слова и

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

текста в исходном виде (в естественной форме), нормализованная форма

43

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

А = {а1;а2, ...,ап },

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

*

атрибутов .,4 .

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

вида:

ы = {Г,И,А),

где - элемент текста, в исходном варианте соответствующий

морфологическому словарю И/-*, /- естественная форма элемента текста, N -нормализованная форма элемента, А - список морфологических атрибутов элемента.

Упорядоченная последовательность элементов текста представляется в следующем виде:

Рп = {\Л/1,]К2)...,\Кп},

где Р - последовательность элементов текста длиной п, ж, - текстовый элемент, при этом элемент предшествует элементу если / <у.

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

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

У|1П кгм Г" С> -

элементов й^у.да»

Н'ПЧСС (№03 с обшим» шарф, признаками

Сем'античевкий'кпасо --

|----1

| - I

I___-Г

Множесцаа слав, заданное

Перечислением

-

Г'

йонкре-нои СЯСМ

Г'

Разделительный

знак

У Ч

/' \

г- \

Чиспя

"ТГ

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Колосов, Алексей Павлович

Результаты работы докладывались и обсуждались на:

• 4-й международной конференции по распознаванию образов и искусственному интеллекту PReMI 2011 - Pattern Recognition and Machine Intelligence, Россия, Москва, 2011.

• 13-й всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции», Россия, Воронеж, 2011.

• 14-й всероссийской объединенной научной конференции «Интернет и современное общество» IMS-2011, Россия, Санкт-Петербург, 2011.

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

Основное содержание диссертации опубликовано в 7 печатных работах.

Заключение

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

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

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

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

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

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

В процессе выполнения работы был решен ряд практических задач:

• Исследовано поведение разработанных алгоритмов с различными настройками.

• На основе результатов экспериментов с несколькими корпусами текстов получены рациональные значения параметров алгоритмов.

• Разработана система полнотекстового поиска, которая может быть интегрирована со сторонними приложениями.

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

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

Список литературы диссертационного исследования кандидат технических наук Колосов, Алексей Павлович, 2012 год

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

1 Agrawal R. h «p. Diversifying search results// Proceedings of the 2nd ACM International Conference on Web Search and Data Mining. - 2009. - CTp. 5-14.

2 Altman A. h Moshe T. Ranking Systems: The PageRank Axioms// Proceedings of the 6th ACM Conference on Electronic Commerce (EC-05). -Vancouver, BC, 2005.

3 Atre Anand Aran Meta-Search Engine based on Query-Expansion Using Latent Semantic Analysis and Probabilistic Latent Semantic Analysis/ Indian Institute of Information Technology. - Allahabad, 2007.

4 Bani-Ahmad S.G. h Al-Dweik G. A new term-ranking approach that supports improved searching in literature digital libraries// Research Journal of Information Technology. - 2011 r.. -1 : T. 3. - CTp. 44-52.

5 Bartell B., Cottrell G. h Belew R. Latent Semantic Indexing is an Optimal Special Case of Multidimensional Scaling // Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval. - 1992. -CTp. 161-167.

6 Becker J. h Kuropka D. Topic-based Vector Space Model // Proceedings of Business Information Systems (BIS 2003) / pe^. Abramowicz W. h Klein G.. - 2003.

7 Berry M.W. h flp. Using Linear Algebra for Intelliget Information Retrieval // SIAM Review. - 1994 r.. - 37 : T. 4. - CTp. 573-595.

8 Blei D.M. h flp. Hierarchical Topic Models and the Nested Chinese Restaurant Process// Advances in Neural Information Processing Systems 16: Proceedinsg of the 2003 Conference: MIT Press, 2004. - ISBN 0-262-20152-6.

9 Blei D.M. h Lafferty J.D. Correlated topic models // Advances in Neural Information Processing Systems. - 2006 r.. - T. 18.

10 Blei D.M., Ng A.Y. h Jordan M.I. Latent Dirichlet Allocation // Journal of

Machine Learning Research. - 2003 r.. - 4 : T. 3. - CTp. 993-1022.

143

11 Bogatyrev M. и Kolosoff A. 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. - стр. 466-473.

12 Bogatyrev M.Y., Mitrofanova O.A. и Tuhtin V.V. Building Conceptual Graphs for Articles Abstracts in Digital Libraries // Proceedings of the Conceptual Structures Tool Interoperability Workshop (CS-TIW 2009) at 17th International Conference on Conceptual Structures (ICCS'09). - Moscow, 2009. - стр. 50-57.

13 Botev C. Expressiveness and performance of full-text search languages// EDBT: Springer, Heidelberg, 2006. - стр. 349-367.

14 Bradford R. An Empirical Study of Required Dimensionality for Large-scale Latent Semantic Indexing Applications// Proceedings of the 17th ACM Conference on Information and Knowledge Management. - 2008. - стр. 153-162.

15 Brin S. и Page L. The anatomy of a large-scale hypertextual Web search engine // Proceedings of the 7th International World Wide Web Conference. - 1998. -T. 30.-стр. 107-117.

16 Burges C.J.C. и др. Learning to rank using gradient descent // Proceedings of the 22nd International Conference on Machine Learning. - Bonn, Germany, 2005. -стр. 89-96.

17 Buttcher S. и Clarke C.L.A. Efficiency vs. effectiveness in terabyte-scale information retrieval // Proceedings of the Text Retrival Confecence (TREC). - 2005.

18 Buttcher S., Clarke C.L.A. и Cormack G.V. Information Retrieval: Implementing and Evaluating Search Engines: MIT Press, 2010.

19 Buttcher S., Clarke C.L.A. и Lushman B. Term proximity scoring for ad-hoc retrieval on very large text collections// Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. - New York, USA, 2006. - стр. 621-622.

20 Cangelosi R. и Goriely A. Component Retention in Principal Component Analysis With Application to Cdna Microarray Data // BMC Biology Direct. - 2007 г.. - 2 : T. 2.

21 Challis John Lateral Thinking in Information Retrieval// Information Management and Technology. - Август 2003 г.. - 4 : T. 36. - стр. 169-173.

22 Chang M. и Poon C.K. Efficient phrase querying with common phrase index // ECIR: Springer, Heidelberg, 2006. - стр. 61-71.

23 Chaudhiri S. и др. Probabilistic information retrieval approach for ranking of database query results// ACM Transactions of Database Systems. - 2006 г.. - 31 : T. 3.

24 Chein M. и Mugnier M. Conceptual Graphs: fundamental notions // Revue d'Intelligence Artificielle. - 1992 г.. - 4 : T. 6. - стр. 365-406.

25 Clarke C.L.A, Cormack G.V. и Tudhope E.A. Relevance ranking for one to three term queries // Information Processing and Management. - 2000 г.. - 36 : T. 2. -стр. 291-311.

26 Cormack G.V. и Lynam T.R. Statistical precision of information retrieval evaluation // Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. - 2006. - стр. 533-540.

27 Croft В., Metzler D. и Strohman T. Search Engines: Information Retrieval in Practice: Addison Wesley, 2009.

28 de Kretser О. и Moffat A. Effective document presentation with a locality-based similarity heuristic // SIGIR. - 1999. - стр. 113-120.

29 Deerwester S. и др. Improving Information Retrieval with Latent Semantic Indexing// Proceedings of the 51st Annual Meeting of the American Society for Information Science. - 1988. - стр. 36-40.

30 Deerwester S.C. и др. Indexing by latent semantic analysis // Journal of the American Society of Information Science. - 1990 г.. - 41 : T. 6. - стр. 391-407.

31 Ding С. A Similarity-based Probability Model for Latent Semantic Indexing // Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval. - 1999. - стр. 59-65.

32 Dubin D. The Most Influential Paper Gerard Salton Never Wrote // Library Trends. - 2004 г.. - 52 : Т. 4. - стр. 748-764.

33 Dumais S.T. Latent semantic analysis // Annual Review of Information Science and Technology. - 2004 г.. - 1 : Т. 38. - стр. 188-230.

34 Fox E. и др. Information Retrieval: Algorithms and Data Structures: Prentice-Hall, Inc., 1992.

35 Furnas G. и др. The Vocabulary Problem in Human-System Communication// Communications of the ACM. - 1987 г.. - 30 : T. 11. - стр. 964971.

36 Garcia E. A Tutorial on Okapi Simple BM25F. - 02 08 2011 г.. - 12 01 2012 г.. - http://www.miisHta.com/information-retrieval-tutorial/okapi-simple-bm25f-tutorial.pdf.

37 Girolami M. и Kaban A. On an Equivalence between PLSI and LDA// Proceedings of SIGIR 2003. - 2003. - ISBN 1-58113-646-3.

38 Graesser А. и Karnavat A. Latent Semantic Analysis Captures Causal, Goal-oriented and Taxonomic Structures // Proceedings of CogSci 2000. - 2000. -стр. 184-189.

39 Grossman D.A. и Frieder O. Information Retrieval. - Heidelberg : Springer,

2005.

40 Hjorland B. The foundation of the concept of relevance // Journal of the American Society for Information Science and Technology. - 2010 г.. - 61 : Т. 2. -стр. 217-237.

41 Ни X., Cai Z. и др. LSA: First Dimension and Dimensional Weighting// 25th Annual Meeting of the Cognitive Science Society. - Boston, MA.

42 Hulth A.// GitHub. - 28 04 2010 г.. - 23 12 2011 г..-https://githubxom/snkim/AutomaticKeyphraseExtraction/blob/master/Hulth2003.t

z.

43 Hulth A. Improved automatic keyword extraction given more linguistic knowledge // Proceedings of the 2003 Conference on Empirical Methods in Natural Language Processing. - 2003.

44 Institution of Engineering and Technology Inspec - the IET // IET: The Institution of Engineering and Technology.- 24 12 2011 г..-http://www.theiet.org/resources/inspec/.

45 Internet History - Search Engines // Search Engine Watch. - Universiteit Leiden, Netherlands, Сентябрь 2001 г..- 30 Октябрь 2011 г..-http://www.google.com/url?q=http%3A%2F%2Fwww.internethistory.leidenuniv.nl% 2Findex.php3%3Fc%3D7&sa=D&sntz= 1 &usg=AFQj CNHUI5-TYdKmOhWqOUIJbeWpBIcvMQ.

46 Jarvelin К. и Kekalainen J. Cumulated gain-based evaluation of IR techniques // ACM Transactions on Information Systems. - 2002 г.. - 20 : T. 4. - стр. 422-446.

47 Jolliffe L.T. Principal Component Analysis. - New York : Springer-Verlag,

1986.

48 Jones K.S., Walker S. и Robertson S.E. A Probabilistic Model of Information Retrieval: Development and Comparative Experiments// Information Processing and Management. - 2000 г.. - 36 : T. 6. - стр. 779-840.

49 Jurafsky D. и Gilde D. Automatic Labeling of Semantic Roles// Association for Computational Linguistics. ACL-02. - Philadelphia, 2002.

50 Karypis G. и Han E. Fast Supervised Dimensionality Reduction Algorithm with Applications to Document Categorization and Retrieval // Proceedings of CIKM-00, 9th ACM Conference on Information and Knowledge Management. - 2000.

51 Lancaster F.W. и Fayen E.G. Information Retrieval On-Line. - Los Angeles : Melville Publishing Co., 1973.

52 Landauer Т.К., Foltz P.W. и Laham D. An Introduction to Latent Semantic Analysis //Discourse Processes. - 1998 г.. - Т. 25. - стр. 259-284.

53 Manning С., Raghavan P. и Schutze H. Introduction to Information Retrieval: Cambridge University Press, 2008. - ISBN 9780521865719.

54 Metzler D. и др. Indri at TREC 2004: Terabyte track // TREC. - 2004.

55 Mihalcea R. Graph-based ranking algorithms for sentence extraction, applied to text summarization // Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACL 2004). - Barcelona, Spain, 2004.

56 Mihalcea R. и Tarau P. TextRank: Bringing Order into Texts // Proceedings of the Conference on Empirical Methods in Natural Language Processing. - 2004.

57 Miller G.A. и др. WordNet: An online lexical database// International Journal of Lexicography. - 1990 г.. - 3 : Т. 4. - стр. 235-244.

58 Minka Т. и Lafferty J. Expectation-propagation for the generative aspect model // Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence. San Francisco. - San Francisco, CA : Morgan Kaufmann, 2002. - ISBN 1-55860-8974.

59 Monz C. Minimal span weighting retrieval for question answering// IR4QA. - 2004.

60 Online Help // SmartBear Software Support Portal. - SmartBear Software. -11 01 2012 г.. - http://smartbear.com/support/onlinehelp/.

61 Papka R. и Allan J. Why bigger windows are better than small ones : Технический отчет / CIIR. - 1997.

62 Ponte J.M. и Croft W.B. A Language Modeling Approach to Information Retrieval // Research and Development in Information Retrieval. - 1998 г.. - стр. 275281.

63 Rasolfo Y. и Savoy J. Term proximity scoring for keyword-based retrieval systems // ECIR / ред. Sebastiani F.: Springer, Heidelberg, 2003. - стр. 207-218.

64 Robertson S.E. и Jones K.S. Relevance weighting of search terms // Journal of the American Society for Information Science. - 1976 г.. - 27. - стр. 129-146.

65 Robertson S.E. и Zaragoza H. The Probabilistic Relevance Framework: BM25 and Beyond // Foundations and Trends in Information Retrieval. - 2009 г.. - 4 : Т. 3. - стр. 333-389.

66 Robertson S.E., Walker S. и Hancock-Beaulieu M. Okapi at TREC-7// Proceedings of the 7th Text Retrieval Conference. - 1998.

67 Robertson S.E., Zaragoza H. и Taylor M. Simple BM25 extension to multiple weighted fields// Proceedings of the 2004 ACM CIKM International Conference on Information and Knowledge Management: ACM, 2004. - стр. 42-49.

68 Salton G., Fox E.A. и Wu H. Extended Boolean information retrieval // Communications of the ACM. - 1983 г.. - 11 : T. 26.

69 Saptaditya M. и др. Sentence Ranking for Document Indexing // PReMI 2011, LNCS 6744: Springer-Verlag, 2011. - T. 6744. - стр. 274-279.

70 Schenkel R. и др. Efficient Text Proximity Search // SPIRE'07 Proceedings of the 14th international conference on String processing and information retrieval / ред. Ziviani Nivio и Baeza-Yates Ricardo: Springer-Verlag, 2007. - стр. 287-299. -ISBN 3-540-75529-2 978-3-540-75529-6.

71 Shanmukha Rao В., Rao S. V. и Sajith G. A user-profile assisted meta search engine // TENCON-2003 Conference on Convergent Technologies for Asia-Pacific Region. - 2003. - T. 2. - стр. 713-717.

72 Song F. и Croft W.B. A General Language Model for Information Retrieval // Research and Development in Information Retrieval. - 1999 г.. - стр. 279280.

73 Song R. и др. Viewing term proximity from a different perspective : Технический отчет / Microsoft Research Asia. - 2005. - MSR-TR-2005-69.

74 Sowa J.F. Conceptual Graphs: Draft Proposed American National Standard // International Conference on Conceptual Structures (ICCS-99). - Berlin: Springer, 1999.

75 Sowa J.F. Knowledge Representation: Logical, Philosophical, and Computational Foundations. - Pacific Groove, CA : Brooks Cole Publishing Co., 2000.

76 Troy A.D. и Zhang G.Q. Enhancing Relevance Scoring with Chronological Term Rank // Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. - New York, USA, 2007. -стр. 599-606.

77 van Rijsbergen C.J. A non-classical logic for information retrieval // The Computer Journal. - 1986. - стр. 481-485.

78 Williams H.E. и др. Fast phrase qerying with combined indexes // ACM Transactions on Infromation Systems. - 2004 г.. - 22 : Т. 4. - стр. 573-594.

79 Williams H.E. и др. What's next? Index structures for efficient phrase querying//Australasian Database Conference. - 1999. - стр. 141-152.

80 Witten I.H., Moffat А. и Bell T.C. Managing gigabytes: compressing and indexing documents and images. - San Francisco : Morgan Kaufmann Publishing, 1999. - ISBN 1-55860-552-5.

81 Wong S.K.M., Wojciech Z. и Wong P.C.N. Generalized vector spaces model in information retrieval // SIGIR. - 1985.

82 Wu H.C. и др. A retrospective study of probabilistic context-based retrieval // Proceedings of the 28th annual international ACM SIGIR Conference on Research and development in information retrieval (SIGIR'05). - 2005. - ISBN:1-59593-034-5.

83 Yilmaz E., Kanoulas E. и Aslam J.A. A simple and efficient sampling method for estimating AP and NDCG // Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. -Singapore, 2008. - стр. 603-610.

84 Yu C.T. и Salton G. Precision Weighting - An Effective Automatic Indexing Method // Journal of the ACM. - 1976 г.. - 23 : Т. 1. - стр. 76-88.

85 Zaragoza H. и др. Microsoft Cambridge at TREC-13: Web and HARD tracks // Proceedings ofTREC-2004. - 2004.

86 Агеев M., Кураленок И. и Некрестьянов И. Официальные метрики РОМИП 2010 // РОМИП. - 2010 г.- 10.2.2012 г..-http://romip.ru/romip2010/20_appendix_a_metrics.pdf.

87 Богатырев М.Ю. и Тюхтин В.В. Построение концептуальных графов как элементов семантической разметки текстов // Компьютерная лингвистика и интеллектуальные технологии: По материалам ежегодной Международной конференции «Диалог 2009». - Москва : РГГУ, 2009. - стр. 620.

88 Богатырев М.Ю., Латов В.Е. и Столбовская И.А. Применение концептуальных графов в системах поддержки электронных библиотек // Электронные библиотеки: перспективные методы и технологии, электронные коллекции. Труды 9-й всероссийской научной конференции RCDL'2007. -Переславль-залесский: Изд-во "Университет города Переславля", 2007. - стр. 310.

89 Демьянков В.З. Семантические роли и образы языка// Когнитивные аспекты лексикографии . - 24 11 2008 г.. - http://www.infolex.ru/deml.html.

90 Ермаков А.Е. Тематический анализ текста с выявлением сверхфразовой структуры // Информационные технологии, 2000 г. - 11.

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

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

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

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

95 Кузнецов С.О., О некоторых вопросах анализа понятий // Научно-техническая информация (НТИ). - 1999 г. 1-2. - стр. 57-61.

96 Ландэ Д.В., Снарский A.A. и Безсуднов И.В. Интернетика: Навигация в сложных сетях: модели и алгоритмы. - М.: Либроком, 2009. - ISBN 978-5-39700497-8.

97 Леонтьева А. и Кагиров И. Автоматический синтаксический анализ русских текстов // Электронные библиотеки: перспективные методы и технологии, электронные коллекции. Труды Десятой Всероссийской научной конференции «RCDL'2008». - Дубна : ОИЯИ, 2008. - стр. 415.

98 Люгер Дж.Ф. Искусственный интеллект: стратегии и методы решения сложных проблем, 4-е изд.. - Москва : Издательский дом "Вильяме", 2003.

99 Маннинг К., Рагхаван П. и ПЬотце X. Введение в информационный поиск: Вильяме, 2011. - ISBN 978-5-8459-1623-5.

100 Мельчук И.А. Опыт теории лингвистических моделей "Смысл-Текст". Семантика, синтаксис. - Москва : Школа "Языки русской культуры", 1999.

101 Павлов A.C. Методы обнаружения массово порождаемых неестественных текстов на основе анализа разнообразия тематической структуры текстов// Труды 13-й Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» - RCDL'2011. - Воронеж, 2011.

102 Фримен А. и Раттц Дж. LINQ: язык интегрированных запросов в С# 2010 для профессионалов: Вильяме, 2011. - ISBN 978-5-8459-1701-0.

103 Шаров С.А. Средства компьютерного представления лингвистической информации // Информационные технологии и телерадиокоммуникации. - 2000 г. - 2.