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

Как уже было написано во введении, одной главных задач данной работы является разработка алгоритма сравнения двух таблиц на их соответствие. На вход в алгоритм поступают две модели таблиц, которые имеют вид, подобный виду описанном на рис. 2.3. Данная модель будет реализована виде списка списков(List< List<string>>). На выходе будет ответ в виде "True/False", где True означает, что таблицы соответствуют друг другу, а False означает, что не соответствуют. Псевдокод алгоритма описан ниже.

Bool CompareTables(List<List<List<string>>> tbl1,

List<List<List<string>>> tbl2)

{

If (tbl1.Count == 0 || tbl2.Count == 0) return false;

Foreach (List<List<string>> lst1 in tbl1)

{

Foreach (List<List<string>> lst2 in tbl2)

{

If (lst1.Count == 0 || lst2.Count == 0)

{

Continue;

}

If (lst1.Count < lst2.Count)

{

If (compareLevels(lst1, lst2))

{

Return true;

}

}

Else

{

If (compareLevels(lst2, lst1))

{

Return true;

}

}

}

}

Return false;

}

В данном алгоритме происходит сравнение каждого уровня заголовков с каждым уровнем заголовков из другой таблицы. Каждый уровень заголовков состоит из набора заголовков. Для того, чтобы результат сравнения двух таблиц был равен true достаточно, чтобы хотя бы одно сравнение уровней дало положительный ответ. В данном алгоритме применяется функция CompareLevels, алгоритм которой описан в предыдущей пункте.

На вход алгоритму поступают две модели таблиц, состоящие из одного и более уровней, а каждый уровень содержит непосредственно заголовки таблиц. Далее в алгоритме идет процесс сравнения каждого уровня заголовка из одной таблицы с каждым уровнем заголовков и другой. Если хоть одно из сравнений дало положительный ответ, то алгоритм возвращает true, а это в свою очередь означает, что он признает эти таблицы соответствующими друг другу. Рассмотрим алгоритм сравнения двух таблиц на соответствие друг другу на конкретном примере

Сравнение произведено в соответствии с алгоритмом описанным в предыдущим пункте. Зеленая стрелка означает, что данные уровни релевантные, красная - не релевантные. Так как для данного алгоритма достаточно всего одного совпадения, чтобы вернуть true, то результатом сравнения данных таблиц будет true. Если n - количество уровней в первой табле, а m - во второй, то сложность алгоритма будет стремится к выражению n*m.

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




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

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