|
|
Таблица 3.2
Расчет индексов вершин графа, представляющего семантическую модель исходного текста
Номер вершины
Расчет
Результат
1
0.5 + ½
1
2
0.5 + 2/2
1.5
3
0.5 + 0/2
0.5
4
0.5 + 0/2
0.5
Согласно проведенным расчетам стартовыми точками на первом шаге следует выбирать в графе, представляющем семантическую модель исходного текста, вершину, номер которой равен единице. Для графа, представляющего семантическую модель словаря, стартовой вершиной будет вершина с номером 2.
Задача следующего этапа целиком ориентированна на установление изоморфности этих графов и определение степени их соответствия.
Вычисление этих показателей следует вести, используя формулу (3.4) и максимизируя соответствующий параметр.
Предположим, что на первой итерации будет осуществлена попытка установки соответствия графов так, как это показано на рисунке 3. 6
Рис. 3.6. Первая итерация установления соответствия
На рисунке предполагаемые соответствия обозначены пунктиром.
В данном случае степень соответствия составит 1/3, поскольку совпала только одна вершина из трех (та, которая была выбрана в качестве стартовой). Анализируя текущий уровень соответствия можно существенно оптимизировать алгоритм таким образом, чтобы осуществлялся возврат на уровень вверх тогда, когда текущий уровень соответствия меньше заданного значения. С точки зрения реализации данный подход можно рассматривать как перебор с возвратом.
На второй итерации будет выполнена попытка установить соответствие графов таким образом, как это показано на рис. 3.7.
Рис. 3.7. Вторая итерация установления соответствия
В результате выполнения данной итерации будет установлено, что значение уровня соответствия составляет 3/3 (совпали все вершины).
Решение задачи завершается расчетом максимального значения уровня соответствия по итерациям:
Z = max(1/3, 3/3) = 3/3 = 1
Таким образом установлено, что степень соответствия графов составляет 1, что говорит о том, что графы абсолютно семантически изоморфны, а значит имеет место абсолютное заимствование текста. Процент заимствования составит
Z*100 = 100%.
Данный пример не претендует на полноценную иллюстрацию работы алгоритма, он всего лишь показывает логику работы алгоритма. Одной из существенных деталей, которая в данном примере не рассматривалась, является то, что для ребер графов обязательно должно быть проставлено значение их весов. В примере было принято значение весов ребер равными 1, на практике же значение обычно определяется некоторым дробным числом, причем, чем точнее будет определено это значение, тем точнее будет определен результат степени соответствия, и тем эффективнее и оптимальнее будет работать алгоритм перебора с возвратом.
Кроме этого, следует обратить внимание на то, что степень соответствия будет зависеть не только от значения веса текущего ребра графа, а и от удаленности от стартовой вершины. Такой подход имеет две полезные особенности:
· Он более логично позволяет описать логику работы семантических моделей;
· Используя нити графа с весом, определяемым таким образом, возможно существенно оптимизировать работу алгоритма.
Если для графа
Определена функция весов ребер согласно (3.2)
,
определена исходная вершина и такие, что
,
(3.7)
Функция определяет длину кратчайшего пути между вершинами и , и соответствует (3.3).
Данное ограничение (3.7) определяет, что между вершинами и отсутствует прямое ребро (то есть они не являются инцидентными), но между ними существует конечный путь.
Предположим, что вершины и удовлетворяют ограничению (3.7) и существует множество
, (3.8)
такое, что (3.8) представляет собой множество вершин, составляющих кратчайший путь.
Нить между вершинами и будет представлять собой некоторое абстрактное ребро, определяющее наличие непрямой связи между семантическими лексемами.
Весом нити между вершинами и будет являться значение, определяемое следующей формулой:
(3.9)
Пример.
Предположим, что существует некоторая семантическая модель, представленная графом, изображенным на рисунке 3.8.
Следует обратить внимание, что данная семантическая модель не отражает истинного смысла предметной области, это всего лишь пример, на котором возможно продемонстрировать использование оптимизации установления факта изоморфности графа с использованием нитей.
Рис. 3.8. Семантическая модель, для которой предполагается использовать нити
Предположим, что требуется построить нить таким образом, как это показано на рисунке 3.9 (нить обозначена пунктиром)
Рис. 3.9. Построение нити в семантической модели.
Вычисление веса нити следует вести согласно формуле (3.9), предварительно определив кратчайший путь.
Согласно формуле (3.9) вес нити будет определен следующим образом:
Таким образом, семантическая лексема «Чаты и форумы» имеет отношение к семантической лексеме «Средства взаимодействия между вычислительными узлами”. Степень этого отношения определяется уровнем 0.1836.
Использование нитей может оказаться очень эффективным инструментом при установлении факта изоморфности графов, однако перед их использованием следует выполнить ряд подготовительных действий.
Основная проблема при использовании нитей заключается в том, что возможна ситуация, когда в путь, являющийся промежуточным для данной нити, может попасть вершина, которая может быть сопоставлена другой вершине в сравниваемом графе, и тогда алгоритм установления факта изоморфности графов не будет работать корректно.
Таким образом, выделению в путь, который будет заменен нитью, подлежат только те вершины, индекс соответствия которых меньше предельно допустимого.
3.2. Анализ оптимальности алгоритма
В настоящий момент не существует формального алгоритма установления факта изоморфности графов, оценка которого имеет полиномиальный характер. Более того, гарантированное время, за которое анализ изоморфности будет выполнен составляет
O(n) = n!
Предположим, что имеется некоторая база документов в виде семантических моделей, объем которой:
· 18000 записей базового семантического словаря;
· 300000 документов, каждый их которых содержит 10000 семантических лексем
Эти численные данные взяты исходя из предварительного анализа базы документов referat.ru.
Объем данных в таком случае составит:
Вычислим приближенное значение факториала данного числа по формуле Стирлинга:
Вычисление значения выражения, соответствующего формуле Стирлинга в рамках данной работы вести не обязательно, достаточно отметить, что это значение будет значительно превосходить число
Страницы: 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
При использовании материалов активная ссылка на источник обязательна.