Алгоритм семантического поиска в больших текстовых коллекциях Виталий Савченко АлтГТУ им. И. И. Ползунова, Барнаул, Россия 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