Алгоритм сравнения двух заголовков на соответствие друг другу - Разработка средств автоматизации поиска структурированной информации в гетерогенной среде

Данный алгоритм будет использоваться в алгоритме сопоставления двух таблиц. На вход алгоритму подается два списка слов из двух заголовков. Первым подается тот список, в котором меньше слов. Описание алгоритма приведено ниже.

Bool CompareHeaders(List<string> lstMin, List<string> lstMax)

{

Int countrelevant=0;

Foreach (string str1 in lstMin)

{

Foreach (string str2 in lstMax)

{

If (CompareWords(str1, str2))

{

Countrelevant++;

Break;

}

}

}

If (lstMin. Count > 0)

If ((countrelevant / lstMin. Count)*100 >= percentage_of_relevancyHeaders) return true;

Return false;

}

Bool CompareWords(string str1, string str2)

{

Str1 = Stem(str1);

Str2 = Stem(str2);

If (str1 == str2) return true;

Else return false;

}

В псевдокоде, описанном выше, присутствуют две функции: CompareHeaders и CompareWords. В функции CompareРeaders происходит непосредственно сравнение двух заголовков на соответствие друг другу. Для реализации этой функции необходимо было выделить функцию сравнения двух слов на релевантность. В функции CompareWords используется стемминг, который вызывается посредством функции Stem.

На вход алгоритму поступают два набора слов ( один из первого заголовка, второй из второго). Для каждого слова из заголовка, в котором количество слов меньше, проводится сравнение с каждым словом, где количество слов больше. Под сравнение слов понимается сравнение основ слов, который реализуется посредством стемминга. Если слово из набора слов, в котором меньше слов, находит равное себе во втором наборе слов, то переменная-счетчик countrelevant увеличивается на единицу и происходит переход к следующему слову из заголовка, в котором меньше слов. В итоге, если countrelevant разделить на количество слов в наборе, в котором меньше слов, и это значение будет больше или равно параметру - необходимое количество процентов схожести двух заголовков для признания этих заголовков релевантными, то это означает, что заголовки имеют схожий смысл.

Если за n считать количество слов в первом заголовке, за m количество слов во втором, то сложность алгоритма будет стремится к выражению n*m.

Рассмотрим пример сравнения двух заголовков. Есть два заголовка : "Результаты экзамена" и "Итоговый экзамен по программированию". Эти два заголовка будут разделены на следующие наборы слов : (Результаты, экзамена) и (Итоговый, экзамен, программированию). Предлоги и союзы не входят в набор слов так как не несут на себе смысловой нагрузки.

Красная линия означает, что данные слова не соответствуют друг другу, а зеленая если соответствуют. В итоге получается, что из двух слов первого набора, только одно нашло себе соответствующее слово во втором наборе. Теперь необходимо найти процент соответствия заголовков. Для этого нужно разделить количество слов, из набора, в котором меньше слов, которые нашли себе соответствие в другом наборе на количество слов в этом наборе. То есть, в данном случае это будет Ѕ =50%. Если в параметрах соответствия заголовков, стоит значение 50 или менее, то приложение вернет ответ true на вопрос: " Соответствуют ли эти заголовки друг другу?"

Похожие статьи




Алгоритм сравнения двух заголовков на соответствие друг другу - Разработка средств автоматизации поиска структурированной информации в гетерогенной среде

Предыдущая | Следующая