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

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Введение

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

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

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

Решением проблемы поиска литературы по интересующей теме становятся системы, автоматизирующие оба этапа поиска релевантных документов. Во время изучения степени разработанности проблемыбыли рассмотрены различные виды приложений, позволяющих производить поиск литературы по интересующей теме на основе документа. В основном, такие системы работают со своей базой документов [23, 29] или обращаются к поисковым системам [5, 33, 35]. В процессе работы с первым типом систем пользователь должен иметь доступ к базе документов, однако на практике существует множество ограничений доступа. Во время работы со вторым типом систем пользователю достаточно иметь лишь текст исходного документа. Тем не менее, результаты поиска содержат множество ненаучных источников, что затрудняет поиск интересующей научной литературы. Соответственно, разработка приложения, позволяющего искать научную литературу по содержанию текста, является актуальной задачей.

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

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

Задачи данной работы:

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

Проанализировать подходы к извлечению ключевых слов.

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

Выполнить проектирование системы поиска релевантных документов.

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

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

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

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

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

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

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

Рассмотрим примеры таких систем:

1. Системы с доступом к базе документов.

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

Пример такой системы SoftInform Search Technology [29]. Она позволяет производить быстрый поиск, сравнение и анализ документов внутри предприятия. Система имеет возможность интеграции практически со всеми из современных систем управления базами данных и поддерживает различные форматы текстовых файлов (doc,pdf,trf,txt,html).

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

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

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

2. Системы, ориентированные на поиск в сети Интернет.

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

В работе [35] предложен метод QDB (QueryByDocument). Для извлечения ключевых слов в немописан метод, использующий Википедию, а также метрику TF-IDF иMutualInformation.После составления ключевых слов документа, формируется поисковый запрос. Для поиска используется поисковая система BlogScope, которая работает примерно с десятью миллионами блогов, позволяет производить поиск по ключевым словам.Система возвращает блог посты, связанные с темой исходного документа.

В статье лаборатории HP [21] описана система поиска документов на основе текущего, которая также предлагает пользователю рекомендации на основе истории его поиска. Для извлечения ключевых слов используется построение семантического графа текста. После извлечения ключевых слов, формируются запросы к различным поисковым системам, например,Google и Yahoo. Для повышения качества возвращаемых результатов, производятся запросы с различными комбинациями извлеченных ключевых слов и наиболее подходящими считаются документы, которые находятся на пересечении множеств возвращаемых результатов для различных запросов к различным поисковым системам. Также извлеченные ключевые слова сохраняются, для определения поля интересов пользователя, которое позже используется для предложения рекомендаций пользователю.

Система SimSeerX [33] представляет собой веб-приложение для поиска релевантных документов. Его особенность состоит в том, что анализируется не только текст текущего документа, но и его название и метаданные. На основе этой информации формируется запрос, и результаты ранжируются с использованием алгоритма шинглов [13] и алгоритма Simhash [14].

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

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

Анализ подходов к извлечению ключевых слов

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

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

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

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

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

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

Статистические подходы к извлечению ключевых слов

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

1. Частотные методы.

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

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

,(1.1)

гдеTF (Term Frequency) - частота термина в анализируемом документе, отношение числа вхождения термина к количеству терминов в документе (1.2), IDF (Inverse Document Frequency) - инвертированная частота документа, частота с которой термин встречается в других документах коллекции (1.3).

,(1.2)

где ni-частота встречаемости i-го термина в анализируемом документе, nk-количество терминов в анализируемом документе.

,(1.3)

где N - общее количество документов в коллекции (корпусе),df - количество документов, содержащих термин.

Выбор основания логарифма не имеет значения, так как не влияет на соотношение весов терминов.

Также существует метрика C-value [20], однако она менее популярна.

Встречаемость длинных терминов в тексте ниже, чем встречаемость коротких, и метод C-value был предложен для компенсации этого эффекта. Значение терминологичности рассчитывается по формуле (1.4):

,(1.4)

где a - кандидат в термины,|a| - длина словосочетания, измеряемая в количестве слов,freq(a) - частотность кандидата a,Ta - множество словосочетаний, которые содержатa,P(Ta) - количество словосочетаний, содержащих a.

Легко видеть, что чем больше частота термина-кандидата и его длина, тем больше его вес. Но если этот кандидат входит в большое количество других словосочетаний, то его вес уменьшается.

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

2. Методы на основе внешних ресурсов.

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

Например,метрика Domain Pertinence [24] (1.5).

,(1.5)

где Ttarget(t)- частота вхождений термина t в коллекции текстов исследуемой предметной области,Treference(t) - частота вхождений термина t во внешнем корпусе.

Использование метода Relevance [28] позволяет уменьшить важность терминов, которые редко встречаются в наборе текстов обрабатываемой предметной области, или которые часто встречаются во внешнем корпусе документов (1.6).

,(1.6)

где Ttarget(t)- частота вхождений термина t в коллекции текстов исследуемой предметной области,Treference(t) - частота вхождений термина t во внешнем корпусе,DFtarget(t)- количество документов исследуемой предметной области, в которые входит термин t.

Также существуют другие методы на основе внешних ресурсов, например DomainRelevance,DomainSpecificity,Weirdness и т.д.

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

3. Методы на основе ассоциации.

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

Гибридные подходы к извлечению ключевых слов

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

1. Использование графов.

Распространено извлечение ключевых слов с использованием графов [9].Семантический граф представляет собой взвешенный граф, вершинами которого являются термины документа, наличие ребра между двумя вершинами означает тот факт, что термины семантически связаны между собой, вес ребра является численным значением семантической близости двух терминов, которые соединяет данное ребро. Затем в графе происходит поиск сообществ и их ранжирование. Обычно ранжирование происходит в соответствие с плотностью сообщества и его информативностью, которая может быть посчитана с помощью любой статистической метрики, описанной в разделе 1.2.1. Например, для следующего текста: «Статья посвящена вопросу извлечения терминов из текстов на русском языке при помощи графовых моделей. Описан и экспериментально исследован алгоритм решения данной задачи. Сформулированы требования и рекомендации к применению алгоритма в задачах обработки русского языка», граф представлен на рисунке 1.1.



Рисунок 1.1. Граф приведенного текста

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

2. Методы на основе машинного обучения.

Для извлечения ключевых слов также используются методы на основе машинного обучения. Задача извлечения рассматривается как задача классификации. Для обучения, необходима выборка с заранее извлеченными ключевыми словами. В рамках обучения вычисляются различные параметры, такие как часть речи, местоположение в документе, статистические метрики и т.д. Рассчитывается вероятность отнесения термина к ключевым. При обработке документа решается задача классификации, вычисляется релевантность термина для данной предметной области. Самым распространенным и простым в реализации методом на основе машинного обучения с учителем, является Наивный Байесовский классификатор, основанный на теореме Байеса. Слово «наивный» в данном контексте означает предположение классификатора о независимости случайных величин. В рамках задачи автоматического извлечения ключевых фраз случайными величинами могут являются различные признаки фраз, например, длина фразы, абсолютное расположение в документе, информативность. У каждого признака есть свой вес, соответственно можно рассчитать важность фразы с помощью произведения каждого из признаков на его вес. Также используются методы на основе нейронных сетей [24, 31], деревьев решений [30] и т.д.

3. Методы на основе Википедии.

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

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

4. Методы на основе поисковых машин.

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

Обоснование выбора метода извлечения ключевых слов

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

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

Таблица 1.1. Сравнение методов извлечения ключевых слов

Группа методов	Методы	Требуется корпус документов	Требуется обращение к внешним ресурсам	Требуется предварительное обучение	Сложность реализации
Статистичес-кие методы	Частотные	Да/Нет	Нет	Нет	Низкая
	На основе внешних ресурсов	Да	Да	Нет	Низкая
	На основе ассоциации	Да/Нет	Нет	Нет	Средняя
Гибридные методы	На основе графов	Нет	Да/Нет	Нет	Высокая
	На основе машинного обучения	Да	Да/Нет	Да	Высокая
	На основе Википедии	Нет	Да	Нет	Высокая
	На основе поисковых машин	Нет	Да	Нет	Средняя

На основе данного сравнения был выбран частотный подход, так как его использование не требует предварительного обучения и обращения к внешним ресурсам, также метод достаточно прост в реализации при высоких показателях эффективности, что подтверждают исследования [3, 34, 36]. Частотные методы можно использовать в любой предметной области, что было отмечено в работе [5], в то время как методы на основе поисковых машин и методы на основе Википедии показывают различную эффективность в зависимости от предметной области анализируемого документа. В частности, в данной работе была выбрана метрика TF-IDF, которая является наиболее популярной метрикой для вычисления информативности слова в анализируемом документе. Метрика требует наличия корпуса документов, однако это не является критичным.

Анализ электронных научных ресурсов

Для поиска научной литературы на русском языке существуют различные электронные библиотеки, имеющие свою базу научных документов, поисковые системы, которые имеют доступ к базам электронных библиотек. В данном разделе рассмотрены четыре наиболее популярных ресурса для поиска научной литературы на русском языке: научная библиотека eLibrary, электронная библиотека КиберЛенинка,Российская Государственная Электронная Библиотека и поисковая система Академия Гугл.

Были выделены следующие характеристики электронных научных ресурсов для их сравнения:

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

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

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

Удобство разметки страницы для программного разбора.

Обзор электронных научных ресурсов

Научная библиотека eLibrary [18] это крупнейшая российская электронная библиотека, которая содержит более 22 миллионов статей и публикаций. Библиотека обладает различными возможностями поиска, например, есть возможность установить фильтры по типу публикации, авторам, годам публикации, по расположению слов в структуре документа и т.д.Библиотека также интегрирована с Российским индексом научного цитирования. Для доступа ко всем публикациям организована платная подписка, однако для бесплатного просмотра доступны статьи из более чем двух тысяч научных журналов.

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

Российская Государственная Электронная Библиотека [12] представляет собой электронный каталог Российской Государственной Электронной Библиотеки. Содержит электронные копии наиболее ценных и запрашиваемых публикаций, а также содержит документы, изначально созданные в электронном виде. Содержит около миллиона документов и постоянно пополняется.

Академия Гугл (GoogleScholar) [1] это часть поисковой системы Гугл, которая позволяет находить научные работы из большинства научных журналов крупных издательств Европы и Америки. Является бесплатным ресурсом и обладает простым и понятным интерфейсом схожим со стандартным интерфейсом поисковой системы Гугл. Позволяет фильтровать результаты по датам, типу публикаций, языку и т.д.

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

Выбор электронного научного ресурса

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

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



Таблица 1.2. Сравнение научных электронных ресурсов

Название ресурса	Возвращаемые результаты	Возможность чтения онлайн	Формат файлов	Удобство разметки страницы для разбора	Примечание
eLibrary	Страница, содержащая названия, ссылки на публикации, автора, издательство	Присутствует возможность чтения для отдельных статей	PDF	Разметка неудобна для программного разбора	Параметры запроса кодируются неизвестным способом
КиберЛенинка	Страница, содержащая названия, ссылки на публикации, автора, издательство	Присутствует возможность чтения	PDF	Удобная разметка для программного разбора	При переходе по ссылке необходимы дополнительные действия по открытию документа
Российская Государственная Электронная Библиотека	Страница, содержащая ссылки на каталоги библиотеки	Присутствует возможность чтения для пользователей, имеющих доступ к библиотеке	MRC	Разметка неудобна для программного разбора	Необходимо переходить по ссылкам на каталоги
Академия Гугл	Страница, содержащая названия, ссылки на публикации, автора, издательство	Присутствует возможность чтения	PDF, HTML и др.	Удобная разметка для программного разбора	Покрывает большинство документов остальных трех библиотек

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

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

Выводы по первой главе

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

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



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

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

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

Рисунок 2.1. Диаграмма прецедентов системы поиска релевантных документов

Как можно видеть на построенной диаграмме, основными акторами системы поиска документов релевантных заданному тексту являются:

Пользователь.

Набор статей, необходимый для расчета уникальности термина.

Файл с рассчитанными коэффициентами IDF.

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

Система поиска научных статей, в качестве которой была выбрана Академия Гугл.

Основные прецеденты системы:

Ввод текста.

Поиск по ключевым словам.

Извлечение ключевых слов.

Расчет коэффициентов IDF.

В таблицах 2.1-2.4 представлено подробное описание каждого из выявленных прецедентов.

Таблица 2.1. Прецедент «Ввод текста»

Название	Ввод текста
Акторы	Пользователь
Краткое описание	Пользователь подает на вход текст для последующей обработки
Триггер	Начало работы с системой
Основной поток	Пользователь выбирает файл в одном из трех форматов (docx,pdf,txt) и нажимает кнопку «OK», текст документа отображается на главной форме
Альтернативные потоки	Пользователь вручную вводит текст в соответствующее поле на главной форме

Таблица 2.2. Прецедент «Извлечение ключевых слов»

Название	Извлечение ключевых слов
Акторы	Пользователь, Файл с коэффициентами, Морфологический анализатор
Краткое описание	Система производит обработку текста, извлекает ключевые слова и выводит их пользователю
Триггер	Пользователь нажимает на кнопку «Извлечь ключевые слова»
Основной поток	Производится отбор кандидатов в ключевые термины с использованием морфологического анализатора, затем для каждого из кандидатов рассчитывается метрика TF-IDFс использованием файла с рассчитанными коэффициентами, после чего производится ранжирование терминов и их вывод пользователю
Альтернативные потоки	-

Таблица 2.3. Прецедент «Расчет коэффициентов»

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

Таблица 2.4. Прецедент «Поиск по ключевым словам»

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

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

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

AOT [2] - проект инструментов обработки текста на естественном языке. Пакет состоит из компонентов - лингвистических процессоров, которые друг за другом обрабатывают входной текст. Также содержит морфологический анализатор, базирующийся на грамматическом словаре А.А. Зализняка.

Mystem [26] - морфологический анализатор русского языка с поддержкой снятия морфологической неоднозначности, разработан в компании «Яндекс». Программа работает на основе словаря и способна формировать морфологические гипотезы о незнакомых словах.

Pymorphy [7] - морфологический анализатор, разработанный на языке программирования Python. Выполняет лемматизацию и анализ слов, способен осуществлять склонение по заданным грамматическим характеристикам слов. В процессе работы использует словарь АОТ.

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

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

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

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

Рисунок 2.2. Диаграмма классов системы поиска релевантных документов

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

Класс TextProcessing содержит методы для обработки текста и извлечения ключевых терминов.

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

Методы для осуществления поиска и разбора результатов содержатся в классе SearchProcessing.

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

Описание алгоритма извлечения ключевых слов

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

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

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

Рисунок 2.3. Алгоритм обработки кандидата в ключевые слова

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

Так как у Google Scholar отсутствует API, необходимо производить разбор страницы результатов (парсинг). Для получения результатов поиска, необходимо произвести веб-запрос. Существует 2 вида веб-запросов: GET и POST. Между ними существуют следующие различия:

Метод GET отправляет данные сайту как часть URL, в случае POSTзапроса, данные передаются сайту в теле запроса, то есть они скрыты.

Метод POST позволяет передавать файлы.

Объем передаваемой информации в GET-запросе ограничен 2 килобайтами.

Google Scholarне поддерживает POST-запросы, следовательно, необходимо производить GET-запрос.Для разрабатываемой системы безопасность не является критичной, так как не происходит передачи секретных данных, следовательно, использование GET запроса является приемлемым.

Результаты поиска публикаций по фразе «извлечение ключевых слов» показаны на рисунке 2.4.

Рисунок 2.4. Результаты поиска в Google Scholar

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

Алгоритм работы с Google Scholar представлен на рисунке 2.5.Вначале необходимо сформировать запрос с использованием извлеченных ключевых слов с указанием различных параметров, таких как язык выводимых результатов, виды источников и т.д. Затем для каждой из первых десяти страниц результатов поиска необходимо произвести веб-запрос. После получения страницы в ответ на запрос производится разбор ее разметки, выделяются результаты поиска. Для каждого из результатов поиска на полученной странице выделяются тип публикации, название, авторы, ссылка. На основе полученных данных, для каждого из результатов поиска создается экземпляр класса SearchResult и добавляется в список результатов.

Рисунок 2.5. Алгоритм работы с системой GoogleScholar



Выводы по второй главе

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

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

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



Реализация системы поиска релевантных документов

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

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

После ввода текста документа производится вызов морфологического анализатора Mystem. Mystem представляет собой консольное приложение, производящее разбор текста из файла, имя которого передается в параметрах при запуске приложения. Для его запуска был использован класс Process пространства имен System.Diagnostics, который позволяет запускать процессы и управлять ими. Параметры запуска, это строка вида [опции] [входной файл] [выходной файл]. С помощью опций можно задать режим вывода результатов работы морфологического анализатора. Запуск приложения Mystem производится методом RunMyStem, который приведен на рисунке 3.1.

Рисунок 3.1. Метод RunMyStem

Приведенный метод возвращает массив строк с каждым словом в новой строке, знаки препинания также выносятся на отдельные строки. Также возвращаются морфологические характеристики слова строкой вида: [исходное слово]{[лексема]=[часть речи][[характеристики слова в зависимости от части речи] | [другие варианты разбора]}. Результат разбора слова, а именно часть речи, число, падеж, пол и лексема хранится в классе WordStructure.

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

Рисунок 3.2. Класс KeyPhrase

Список полей класса:

Adj_noun - показывает, является ли кандидат в ключевые слова фразой вида [прилагательное][существительное] или же [существительное][существительное].

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

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

Counter - счетчик количества появлений термина в тексте.

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

OneWord - является ли кандидат словом или фразой.

Result - строка которая будет показана пользователю.

Tf_Idf - рассчитанная TF-IDF метрика для фразы.

Unknown - отражает распознано ли слово.

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

Таблица 3.1. Вывод ключевых фраз пользователю

Тип фразы	Вывод пользователю
Существительное	Существительное в единственном числе именительном падеже
Прилагательное + существительное	Прилагательное и существительное в именительном падеже
Существительное + существительное	Первое существительное в именительном падеже, второе существительное в родительном падеже

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

Также был создан класс Text Processing, который содержит различные методы для обработки текста анализируемого документа.Содержимое класса представлено на рисунке 3.3.

Рисунок 3.3 Класс TextProcessing

Список методов класса:

Analyze Word- производит разбор морфологической характеристики, произведенной анализатором Mystem.

Calculate TFIDF - производит расчет метрики TF-IDF для каждого кандидата в ключевые слова на основе частоты его встречаемости в текущем документе и частоты встречаемости в корпусе документов.

OneWord, TwoWords- непосредственно реализуют алгоритмы, описанные в разделе 2.2.1.

ProcessText, ProcessArticles - реализуют извлечение N-грамм из текста и из набора статей соответственно.

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

Реализация запросов к электронным библиотекам

Для разбора возвращаемой GoogleScholar страницы было решено использовать библиотеку Html Agility Pack [22]. Это .NET библиотека с открытым исходным кодом, которая работает с DOM деревом страницы. Библиотека поддерживает LINQ-запросы, также имеет высокую скорость работы.

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

Рисунок 3.4. Класс SearchResult

Список полей класса:

Author - авторы публикации.

ResType- содержит информацию о формате документа, на который ведет ссылка. Это может быть PDF, HTML и т.д.

Title - Название публикации.

Url - непосредственно ссылка на документ.

Разбор страницы с использованием Html Agility Pack производится в конструкторе класса. Код приведен в приложении В.

Для осуществления запроса создается экземпляр класса WebClient, который предоставляет общие методы обмена данными с заданным ресурсом. Для каждых 10 страниц результатов поиска осуществляется отдельный запрос. Google блокирует запросы, которые осуществляются подряд с малым промежутком времени, что является методом защиты от автоматических запросов. Для обхода данного ограничения между запросами производится пауза продолжительностью 3 секунды. Параметры запроса добавляются в свойство QueryString, параметрами являются номер страницы результатов и ключевые слова для поиска. Для осуществления GET запроса вызывается метод DownloadString, который загружает требуемый ресурс как строку. Загруженная строка содержит HTML полученной страницы. Затем создается элемент класса SearchResult, в конструкторе которого производится разбор HTML-страницы.

Методы для осуществления запроса и получения результатов хранятся в классе SearchProcessing, который представлен на рисунке 3.5.

Рисунок 3.5. Класс Search Processing

Список методов класса:

GetPageHtml - создает экземпляр класса WebClient и загружает строку с указанными параметрами.

ParseResults - производит разбор полученной страницы с результатами поиска с помощью Html Agility Pack.

SendRequest - производит вызов методов GetPageHtml и ParseResults в цикле для каждой страницы с результатами поиска.

Интеграция компонентов

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

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

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

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

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



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

Интерфейс приложения реализован с использованием .NET библиотеки Metro Framework, которая предоставляет широкий выбор элементов управления в стиле ModernUI.

Основными элементами формы являются три вкладки:

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

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