=Paper=
{{Paper
|id=Vol-1197/paper24
|storemode=property
|title=Алгоритм семантического поиска в больших текстовых коллекциях
(Semantic Search Algorithms in Large Text Collections)
|pdfUrl=https://ceur-ws.org/Vol-1197/paper24.pdf
|volume=Vol-1197
|dblpUrl=https://dblp.org/rec/conf/aist/Savchenko14
}}
==Алгоритм семантического поиска в больших текстовых коллекциях
(Semantic Search Algorithms in Large Text Collections)==
https://ceur-ws.org/Vol-1197/paper24.pdf
Алгоритм семантического поиска в больших
текстовых коллекциях
Виталий Савченко
АлтГТУ им. И. И. Ползунова, Барнаул, Россия
64svv@rambler.ru
Аннотация В статье рассматривается метод семантического поис-
ка для многопоточной обработки текстов большого объема. Поиско-
вый запрос и обрабатываемый текст преобразуются в графы семан-
тических связей. Предлагается алгоритм вычисления коэффициента
соответствия семантических графов. Приводятся оценки времени об-
работки.
Ключевые слова: семантический анализатор, граф, справочник,
вес, тип семантической связи.
1 Общие сведения
В наше время, в условиях большого и стремительно растущего объе-
ма информации, актуальна задача поиска в больших текстовых коллекци-
ях [1]. Одним из вариантов поиска является семантический поиск, т.е. по-
иск с точки зрения содержащейся в тексте информации [2,3,4]. Среди наи-
более популярных систем семантического поиска можно выделить Google,
SearchMonkey, Freebase и AskNet. Однако они имеют определенные недостат-
ки, такие как: применение семантики лишь для незначительного улучшения
результатов поиска, ограничение на длину запроса, снижение качества по-
иска с увеличением поискового запроса. Кроме того большинство из таких
поисковых систем работают только с английским языком.
Учитывая сложность семантического поиска необходимо применять ме-
тоды, основанные на имеющихся в системе знаниях о предметной области.
2 Семантический поиск
В данной работе представлен результат разработки системы семантиче-
ского поиска для больших текстовых коллекций на русском языке. Клю-
чевой особенностью полученной системы - является снятие ограничений на
величину поискового запроса и многопоточная обработка текстовой коллек-
ции.
Исходными данными для поиска являются текстовые коллекции и запрос
пользователя, который представляет собой текстовую коллекцию. Исходя из
161
предположения, что большая текстовая коллекция в общем случае неодно-
родна и с точки зрения поиска интересна ее определенная часть, то текст
нужно разделить на определенные участки - страницы, абзацы или наборы
из нескольких предложений. Такие фрагменты будем называть «окнами».
Для каждого окна запроса и поисковых коллекций строится граф семан-
тических связей, назовем его «семантический граф». Семантический граф
представляет собой направленный граф, вершинами которого являются сло-
ва русского языка, представленные в нормальной форме, а ребра характери-
зуются весом и типом семантической связи. Направление ребра зависит от
типа семантической связи, например, отношение объект - действие, объект
- свойство, действие - время.
Для построения семантического графа каждое предложение из окна кол-
лекции обрабатывается семантическим анализатором. В данной работе ис-
пользуется семантический анализатор RML1 .
Предложения окна обрабатываются последовательно. На каждой ите-
рации семантический граф предыдущей итерации объединяется с графом
Gnew обрабатываемого предложения. Веса ребер семантического графа Gnew
равны 1. После объединения у графа Gi+1 все веса ребер умножаются на
коэффициент затухания η.
Gi+1 = (Gi + Gnew ) ∗ η (1)
После этого результирующий семантический граф используется для следу-
ющей итерации. Затем из графа удаляются ребра с весом меньше δ. Умень-
шение веса ребер на заданный процент, аналогичное испарению феромона в
«муравьином алгоритме» [5], сделано для ослабления воздействие предше-
ствующих семантических зависимостей между вершинами графа.
Далее необходимо подсчитать величину коэффициента соответствия се-
мантического графа запроса и семантического графа окна. Простой поиск
наибольшего общего подграфа, даже с учетом совпадения не только вершин,
но и типов ребер, не приведет к цели. Во-первых, по причине NP- полно-
ты данной задачи. Во-вторых, один и тот же смысл содержится в текстах
разного стилевого оформления, например, содержит обобщающие сведения
или только частичную информацию. К хордовым, обитающим в тайге, в
том числе относятся и зайцы тайги. Очевидно, улавливается связь: хордо-
вые → зайцы. Однако между хордовыми и зайцами не должно быть полного
отождествления, т. к. хордовые – это не только зайцы.
Для поиска связанных по смыслу слов был использован словарь, в ко-
тором представлен перечень слов в нормальной форме [6]. Каждому сло-
ву сопоставлен набор слов, связанных с ним ассоциативной, синонимичной
и т. д. связью. Таким образом, словарь представляет собой направленный
граф Gword = (Vword ,Uword ), где вершины Vword - это слова в нормальной
форме, а ребра Uword имеют действительные весовые коэффициенты от 0
до 1. Назовем граф Gword графом справочника.
1
http://www.aot.ru
162
За коэффициент связанности слов ak и am - вершин семантического гра-
фа запроса Grequest и семантического графа окна коллекции Gtext возьмем
произведение весов от таких же слов до общего предка в графе справочни-
ка. При совпадении слов данный коэффициент будет равен 1, иначе будет
принадлежать промежутку [0;1].
Замечание: Граф справочника является упрощенной моделью знаний о
реальном мире, а общий предок слов ak и am в этом графе - это некоторое
обобщение соответствующих понятий. Нет смысла искать общего предка
слов во всем графе справочника. Следовательно, нас интересует некое ξ
окружение искомых слов. В противном случае считаем, что слова никак не
связаны по смыслу. Фрагмент графа Gword представлен на рис. 1.
Рис. 1. Граф справочника
Далее ищем наилучшее совпадение семантического графа запроса с гра-
фом окна. Коэффициент соответствия рассчитываем по формуле 2:
n
X
S= D1k ∗ D2k ∗ L1k ∗ L2k , (2)
k=1
где n – количество совпавших ребер графа запроса и окна, k – индекс со-
ответствующего ребра, D1k , D2k – произведение весов ребер в графе спра-
вочника от слова запроса и слова окна до общего предка соответственно,
L1k – вес ребра k семантического графа запроса, L2k – вес ребра k семан-
тического графа окна. Так как вариантов совпадения графов много – нас
интересует максимальное значение коэффициента соответствия. Определив
максимальное значение по всем окнам текстовой коллекции - получим общее
значение – коэффициент соответствия запроса и текстовой коллекции.
3 Тесты и результаты
Оценка полученной системы является экспертной. Для поиска были ото-
браны текстовые коллекции большого объема удовлетворяющие одному и
тому же запросу к поисковой системе google.ru. В зависимости от настроек
163
системы были получены различные значения коэффициента соответствия
между поисковым запросом и коллекцией. Однако, для коллекций по со-
держанию которых строился запрос или коллекций аналогичного содержа-
ния значение коэффициента минимум на порядок превосходило значение
коэффициента других коллекции, не похожих по содержанию.
Временные затраты на обработку коллекции в зависимости от количе-
ства предложений в запросе и окне коллекции, а так же относительные вре-
менные затраты при многопоточной обработке представлены на рис. 2.
Рис. 2. Временные затраты
Основным минусом текущей реализации алгоритма является значитель-
ное увеличение времени обработки с ростом размеров окна и запроса. Плю-
сом является то, что текстовая коллекция и запрос могут быть разделены
на окна оптимального размера с точки зрения времени обработки. Кроме
того обработка окон текстовой коллекции, в данном случае, может выпол-
няться параллельно, что значительно повышает скорость выполнения на
многопоточных и многопроцессорных системах.
Список литературы
1. Hannah Bast, Marjan Celikik Efficient Fuzzy Search in Large Text Collections //
ACM Transactions on Information Systems, 2010.
2. Mathieu d’Aquin, Enrico Motta Watson, more than a Semantic Web search engine
// IOS Press Amsterdam, 2011.
3. K Elbedweihy, S N Wrigley, F Ciravegna, D Reinhard, A Bernstein Evaluating
Semantic Search Systems to Identify Future Directions of Research // Second
International Workshop on Evaluation of Semantic Technologies, page 25-36, 2012.
4. G. Tsoumakas, M. Laliotis, N. Markantonatos, I. Vlahavas Large-Scale Semantic
Indexing of Biomedical Publications at BioASQ // BioASQ Workshop, 2013.
5. Штовба С. Д. Муравьиные алгоритмы // Exponenta Pro. Математика в при-
ложениях, №4, с.70-75, 2003
164
6. Крайванова В.А., Кротова А.О., Крючкова Е.Н. Построение взвешенного лек-
сикона на основе лингвистических словарей // Материалы Всероссийской кон-
ференции с международным участием ЗОНТ-2011, Т.2, Новосибирск, 2011.
165
Semantic Search Algorithms in Large Text
Collections
Vitaliy V. Savchenko
Altai State Technical University, Barnaul, Russia
64svv@rambler.ru
Abstract. This article describes a method of semantic search based
on the text processing of large volume. Search requests and processing
text from analyzed collection is transformed into a graph of semantic
relationships, the comparison of which allows us to define a measure
of semantic similarity of compared texts. An algorithm is proposed to
calculate the coefficient of semantic graphs concordance. Estimates of
the processing time are also given.
Keywords: semantic analyzer, graph, directory, weight, type of seman-
tic communication.
166