Для того, чтобы устанавливать факт наличия заимствования материалов из публичных источников, может оказаться эффективным метод анализа семантических моделей текстов, представленных на естественном языке.
Задача сравнения семантических моделей близка по характеру к задаче установления изоморфности графов, но имеет ряд специфических особенностей.
В классической теории графов задача установления изоморфности является NP-полной, то есть, не может быть выполнена за полиномиальное время, хотя строгого доказательства того, что задача не может быть решена полиноминальным алгоритмом, не существует. Решение данной проблемы является весьма перспективным направлением, поскольку задача установления изоморфности может очень широко использоваться во многих прикладных направлениях.
Формально изоморфность графов определяется следующим образом:
Если существует 2 различных графа и возможно изменить нумерацию вершин таким образом, чтобы эти графы стали эквивалентными, то эти два графа называются изоморфными.
Некоторым образом оптимизировать алгоритм установления изоморфности возможно за счет применения механизма поиска с возвратом.
Суть алгоритма состоит в последовательном наложении (установлении соответствия) вершин одного графа на вершины другого таким образом, чтобы формируемые подмножества вершин в одном и другом графах имели одинаковые отношения смежности.
Оригинальный алгоритм позволяет установить факт изоморфности графов путем последовательного рекурсивного перебора вершин одного графа и попыток установить соответствие с вершинами другого графа.
Такой алгоритм является очень требовательным к вычислительным характеристикам компьютера, а именно – производительности процессора и объема оперативной памяти. Как правило, требуется выполнять проблемно-ориентированную оптимизацию вычислений. В исследованиях [11], посвященных алгоритмам установления изоморфности графов, приводятся аргументы в пользу того, что существенный выигрыш в производительности алгоритма в общем виде возможно получить только в случае применения оптимизации по следующим направлениям:
· Максимально избавиться от рекурсивных вызовов, так как такие вызовы потребляют значительную часть процессорного времени и не позволяют оптимизировать алгоритм по объему используемой оперативной памяти
· Использовать механизм “back tracking” (рекурсия с возвратом). Однако данный подход должен быть адаптирован для решения с использованием динамического программирования (в данном случае его основная цель – избавиться от рекурсии).
В данной работе при оптимизации алгоритма можно учитывать тот факт, что каждой вершине графа обязательно будет поставлено в соответствие определенное значение – семантическая лексема.
Однако, следует учитывать, что при использовании данного метода установление полного соответствия графа, представляющего связи между семантическими лексемами недостаточно, так как может оказаться допустимым использование родственных семантических понятий (например, использование синонимов или переводов).
Таким образом, в данной работе предполагается использовать следующий алгоритм установления степени изоморфности семантических моделей.
Обозначим графы как G1 и G2:
, (3.1)
представляющие собой множества вершин соответствующих графов.
Определим функцию
, (3.2)
которая задает вес ребра между двумя вершинами из одного из множеств (1) с номерами i и j. Если между соответствующими вершинами ребро отсутствует (или присутствует по иному ориентированное ребро), то значение этой функции будет равно .
Определим также функцию
, (3.3)
которая задает длину кратчайшего пути между двумя вершинами из одного из множеств (3.1) с номерами i и j. Если между соответствующими вершинами путь отсутствует, то значение этой функции будет равно .
Под кратчайшим путем в данном контексте понимается такое множество вершин , принадлежащего множеству вершин соответствующего графа, что
Определим функцию изоморфности двух подграфов PG1 и PG2, составленных из вершин, количество которых составляет |PG1| и |PG2| соответственно:
(3.4)
Шаг 1. Получить два графа, соответствующие семантическим моделям анализируемых текстов. Предполагается, что уже выполнено выделение основного смысла текстов, и семантические модели отражают именно основную смысловую нагрузку.
Шаг 2. Определить максимально допустимое время работы алгоритма (с).
Шаг 3. Определить предметную область в семантическом словаре по алгоритму выделения максимальной компоненты.
Шаг 4. Выделить из графа, представляющего собой семантическую модель исходного текста вершину, имеющую наибольший вес и максимальную степень (количество исходящих ребер). Рассчитать ее индексное значение, исходя из определения (3.5), по формуле:
, (3.5)
где
- степень значимости веса вершины,
- степень значимости связности графа
Степени значимости определяются исходя из того насколько семантический словарь и модель являются полными и связными. Если семантический словарь содержит достаточный объем материалов, позволяющих определить степень заимствования с высокой долей вероятности, и, как следствие, в семантическом словаре присутствует большое количество связей, то и в исходном тексте необходимо определять в качестве исходной такую вершину, которая связана с наибольшим количеством семантических лексем. Это означает, что значение должно быть достаточно большим.
Самым идеальным вариантом (когда следует принимать значение ) является ситуация, когда компонента графа семантического словаря представляет собой полный граф. В таком случае разброс значений весов будет весьма значительным, что потребует использовать большие численные значения.
В общем случае для их анализа потребуется применять механизмы длинной арифметики, однако в данной работе предполагается, что все значения весов ребер будут находиться в диапазонах стандартных типов данных. В данной работе рекомендуется для этих целей применять вычислительную технику с 64-разрядной архитектурой.
Если для определения типа связи ребра будет использоваться тип данных
unsigned __int64,
то это позволит закодировать до 2^64 – 1 типов ребер, что достаточно для задачи анализа заимствований.
Если существует семантический словарь, который представлен графом с высоким значением связности, то вероятность успешного определения факта заимствования материалов достаточно высока, но сложность алгоритма установления изоморфности двух графов прямопропорциональна показателю степени связности графа. Например, если будут рассматриваться два полных графа, то задача определения изоморфности будет сведена к задаче полного перебора, что составил сложность соответствующего алгоритма
O(n) = n!
При том объеме данных, которые будут участвовать в процессе определения факта заимствования, данная сложность алгоритма не может считаться приемлемой. В таком случае подграф графа словаря семантической модели будет ограничиваться не только предметной областью, но и объемами, которые следует определять исходя из значения, определенного на Шаге 2.
Если объем данных в семантическом словаре незначительный, то имеет смысл наиболее точно определять степень согласованности предметных областей, т.е. максимизировать параметр .
В случае, если никакой дополнительной информации о характере графа, представляющего собой семантическую модель словаря и семантической модели рассматриваемого текста на естественном языке нет, то эти коэффициенты следует брать одинаковыми. В данной работе предлагается использовать коэффициент 0.5
Шаг 5. Найти вершину в графе, представляющем семантическую модель словаря, которая будет максимально похожа на ту, которая была определена на Шаге 4.
Схожесть вершин следует определять, сравнивая соответствующие индексы вершин, которые определяются согласно формуле (3.5)
Шаг 6. Вычислить степень изоморфности графов по формуле (3.4).
Пример.
Предположим, что существует некоторый семантический словарь, который представлен графом, изображенным на рис. 3.1
Рис. 3.1. Пример семантического словаря
Предположим, что для анализа предоставлен следующий текст, представленный на естественном языке:
“Одним из типов звуковой аппаратуры являются усилители звуковых сигналов. В настоящий момент распространены два типа усилителей: транзисторные и ламповые”.
Соответствующая модель данного текста может быть представлена на рис. 3.1
Рис. 3.2. Пример семантической модели текста
На этапе определения предметных областей будут определены компоненты исходного графа, представляющего собой семантический словарь. В соответствии с алгоритмом определения компонент графа, каждой вершине будет присвоено некоторое индексное значение.
Количество данных индексных значений будет соответствовать количеству компонент графа. Для всех вершин одной компоненты графа все значения индексов вершин будут одинаковыми.
Схематическое представление графа с проставленными компонентными индексами представлено на рис. 3.3
Рис. 3.3 Разделение графа на компоненты
Таким образом, граф, представляющий семантическую модель словаря, был разделен на 4 компоненты. Каждая компонента представляет собой информацию одной предметной области.
Далее следует определить предметную область, к которой можно отнести исходный текст на естественном языке. В качестве такой предметной области в данном случае следует использовать подграф с вершинами, пронумерованными индексом 2.
Таким образом, задача определения заимствования в данном случае может быть сведена к задаче установления семантической изоморфности двух графов, представленных на рис 3.4
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42
