Найти пары соответствия между двумя наборами

Question

Учитывая два набора ключевых слов, где каждое ключевое слово получило начальное и конечное смещение (например, ключевое слово «abc» начинается со смещения 23 и заканчивается смещением 25), я хотел бы эффективно найти совпадающие пары между этими наборами. Подходящая пара - это ключевое слово из set1 и ключевое слово из set2, где одно ключевое слово начинается после окончания другого ключевого слова, но не более чем MAX_PROXIMITY символов между концом одного и началом другого. кроме того, каждое ключевое слово может принадлежать только одной паре (совпадающее ключевое слово не может быть повторно использовано для другого соответствия).

Answer 1

Вы можете сформулировать это как максимальное совпадение в двудольном графе. Рассмотрим два набора, которые у вас есть, как два набора вершин и генерируем ребра между всеми вершинами из первого набора ко всем вершинам второго набора, которые удовлетворяют вашему правилу, т. Е. «Где одно ключевое слово начинается после окончания другого ключевого слова, но не более MAX_PROXIMITY символы от конца одного до начала другого "

Когда у вас есть график, запустите алгоритм максимального соответствия в двудольном графике. http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matchings_in_bipartite_graphs

Answer 2

Вы можете использовать динамическое программирование для решения этой проблемы.

Предположим, у вас есть каждый набор ключевых слов, упорядоченный по смещению, с которого они начинаются. Давайте определим

set1_keyword[i] # i-th keyword in the first set (ordered by the start offset)
set2_keyword[j] # same for the second set
max_pairs[i][j] # number of pairs in optimal assignment between keywords 1..i from the first set and keywords 1..j from the second set

Конечно, max_pairs[n1][n2] - это решение вашей проблемы (где n1 и n2 - размеры первого и второго набора ключевых слов соответственно)

Для вычисления max_pairs таблицы используйте следующую формулу

if (set1_keyword[i] matches set2_keyword[j])
    max_pairs[i][j] = max_pairs[i-1][j-1] + 1
else
    max_pairs[i][j] = max(max_pairs[i-1][j], max_pairs[i][j-1])

Это в основном говорит о том, что, если вы можете сопоставить ключевые слова, вы делаете это, потому что для проблемы с ключевыми словами 1..i и 1..j это лучшее, что вы можете сделать. В другом случае (i-й и j-й ключевые слова не совпадают) у вас не может быть решения, в котором и i-й, и j-й ключевые слова связаны с некоторыми другими ключевыми словами. Таким образом, в оптимальном решении или ключевое слово i, или ключевое слово j должны быть непарными. Это в основном говорит нам о том, чтобы посмотреть (уже вычисленные) решения проблем max_pairs[i-1][j] (без ключевого слова i-го) или max_pairs[i][j-1] (без ключевого слова j-го) и выбрать лучшее из двух.

Если вы вычислите эту таблицу в правильном порядке, т.е.

for (int i = 0; i < n1; ++i)
    for (int j = 0; j < n2; ++j)
        # compute max_pairs[i][j] here

алгоритм будет иметь сложность O (n1 * n2), что лучше, чем проблема присвоения в двудольном графе (который работает в O (n ^ 3))

Подробнее о динамическом программировании см. динамическое программирование