Аннотация В статье рассматривается метод семантического поиска для многопоточной обработки текстов большого объема. Поисковый запрос и обрабатываемый текст преобразуются в графы семантических связей. Предлагается алгоритм вычисления коэффициента соответствия семантических графов. Приводятся оценки времени обработки. Ключевые слова: семантический анализатор, граф, справочник, вес, тип семантической связи.
предположения, что большая текстовая коллекция в общем случае неоднородна и с точки зрения поиска интересна ее определенная часть, то текст нужно разделить на определенные участки - страницы, абзацы или наборы из нескольких предложений. Такие фрагменты будем называть ¾окнами¿.
Для каждого окна запроса и поисковых коллекций строится граф семантических связей, назовем его ¾семантический граф¿. Семантический граф представляет собой направленный граф, вершинами которого являются слова русского языка, представленные в нормальной форме, а ребра характеризуются весом и типом семантической связи. Направление ребра зависит от типа семантической связи, например, отношение объект - действие, объект - свойство, действие - время.
Для построения семантического графа каждое предложение из окна коллекции обрабатывается семантическим анализатором. В данной работе используется семантический анализатор RML1.
Предложения окна обрабатываются последовательно. На каждой итерации семантический граф предыдущей итерации объединяется с графом Gnew обрабатываемого предложения. Веса ребер семантического графа Gnew равны 1. После объединения у графа Gi+1 все веса ребер умножаются на коэффициент затухания η.
Gi+1 = (Gi + Gnew) ∗ η
(
Далее необходимо подсчитать величину коэффициента соответствия семантического графа запроса и семантического графа окна. Простой поиск наибольшего общего подграфа, даже с учетом совпадения не только вершин, но и типов ребер, не приведет к цели. Во-первых, по причине NP- полноты данной задачи. Во-вторых, один и тот же смысл содержится в текстах разного стилевого оформления, например, содержит обобщающие сведения или только частичную информацию. К хордовым, обитающим в тайге, в том числе относятся и зайцы тайги. Очевидно, улавливается связь: хордовые → зайцы. Однако между хордовыми и зайцами не должно быть полного отождествления, т. к. хордовые – это не только зайцы.
Для поиска связанных по смыслу слов был использован словарь, в котором представлен перечень слов в нормальной форме [6]. Каждому слову сопоставлен набор слов, связанных с ним ассоциативной, синонимичной и т. д. связью. Таким образом, словарь представляет собой направленный граф Gword = (Vword,Uword), где вершины Vword - это слова в нормальной форме, а ребра Uword имеют действительные весовые коэффициенты от 0 до 1. Назовем граф Gword графом справочника. 1 http://www.aot.ru За коэффициент связанности слов ak и am - вершин семантического графа запроса Grequest и семантического графа окна коллекции Gtext возьмем произведение весов от таких же слов до общего предка в графе справочника. При совпадении слов данный коэффициент будет равен 1, иначе будет принадлежать промежутку [0;1].
Замечание: Граф справочника является упрощенной моделью знаний о реальном мире, а общий предок слов ak и am в этом графе - это некоторое обобщение соответствующих понятий. Нет смысла искать общего предка слов во всем графе справочника. Следовательно, нас интересует некое ξ окружение искомых слов. В противном случае считаем, что слова никак не связаны по смыслу. Фрагмент графа Gword представлен на рис. 1.
Рис. 1. Граф справочника
Далее ищем наилучшее совпадение семантического графа запроса с
графом окна. Коэффициент соответствия рассчитываем по формуле 2:
n
S = X D1k ∗ D2k ∗ L1k ∗ L2k,
k=1
(
Тесты и результаты Оценка полученной системы является экспертной. Для поиска были отобраны текстовые коллекции большого объема удовлетворяющие одному и тому же запросу к поисковой системе google.ru. В зависимости от настроек
Рис. 2. Временные затраты Основным минусом текущей реализации алгоритма является значительное увеличение времени обработки с ростом размеров окна и запроса. Плюсом является то, что текстовая коллекция и запрос могут быть разделены на окна оптимального размера с точки зрения времени обработки. Кроме того обработка окон текстовой коллекции, в данном случае, может выполняться параллельно, что значительно повышает скорость выполнения на многопоточных и многопроцессорных системах. Список литературы 6. Крайванова В.А., Кротова А.О., Крючкова Е.Н. Построение взвешенного лексикона на основе лингвистических словарей // Материалы Всероссийской конференции с международным участием ЗОНТ-2011, Т.2, Новосибирск, 2011.
Vitaliy V. Savchenko 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 semantic communication.