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

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

Bool compareLevel(List<List<string>> minTbl, List<List<string>> maxTbl)

{

Int countRelevant = 0;

Foreach (List<string> lstMin in minTbl)

{

Foreach (List<string> lstMax in maxTbl) //Можно добавить глубину поиска

{

If (lstMin. Count <= lstMax. Count)

{

If (CompareHeaders(lstMin, lstMax))

{

CountRelevant++;

Break;

}

}

Else

{

If (CompareHeaders(lstMax, lstMin))

{

CountRelevant++;

Break;

}

}

}

}

Decimal dblCountRelevant = decimal. Parse(countRelevant. ToString());

If (minTbl. Count > 0)

{

Decimal value = dblCountRelevant / minTbl. Count;

If (value * 100 >= percentage_of_relevancyTables) return true;

}

Return false;

}

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

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

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

Рассмотрим пример сравнения двух наборов заголовков. Есть два набора заголовков: (Студент, Результат) и (ФИО, рейтинг до экзамена, экзамен, результат).

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

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




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

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