Эффективное «Выравнивание последовательности», сравнивающее два списка наборов для поиска совпадений - python

Question

Я пытаюсь сравнить два списка наборов (или список списков) и пытаюсь найти эффективное решение.

Даны два списка с различной длиной и, возможно, разными наборами размеров в каждой позиции. , Размер наборов составляет от 1 до 6 целых чисел, а размер списков составляет примерно 4000 элементов для больших и 100 для меньших.

list_1= [{42, 189, 31}, {32, 75, 189}, {42, 31}, {100, 63}, {75, 37}]
list_2=[{75, 37}, {42, 37}]

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

В этом В этом случае наилучшее выравнивание будет в списке list_1 [1: 3], где есть два перекрывающихся элемента

{32, 75 , 189} по индексу 1 списка list_1 и {75 , 37} в индексе 0 списка list_2 в сочетании с { 42 , 31} в индексе 2 списка list_1 и { 42 , 37} по индексу 1 в list_2, что дает счет 2, потому что у нас есть два совпадения. Выходные массивы должны выглядеть следующим образом для приведенного выше примера

sequence_alligenment(list_1,list_2): [0,2,0,1]

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

Я безуспешно пытался использовать пересечение множеств и морозилок из-за некоторых неуклюжих петель for, окружающих их.

Answer 1

Если вам нужна эффективность (если вам нужно много раз использовать этот код и в конечном итоге ждать его), вы, вероятно, могли бы использовать алгоритм нечеткого сопоставления.

Большинство алгоритмов нечеткого сопоставления кажутся нацелены на строки, но они могут быть отправной точкой.

Если это не то, что вы ищете, вы можете попробовать сделать обратный индекс, например: {42: {42, 189, 31}, 189 : {{42, 189, 31}}, 31: {42, 189, 31}, 32: {32, 75, 189}, 75: {32, 75, 189}, 189: {32, 75, 189} , 42: {42, 31}, 31: {42, 31}, 100: {100, 63}, 63: {100, 63}, 75: {75, 37}, 37: {75, 37}}

А затем посчитайте, сколько дубликатов вы получите между любыми двумя парами таким образом. Я верю, что так и будет O (n).

Answer 2

Посмотрите алгоритм Смита-Уотермана. Это алгоритм DP для локального выравнивания последовательностей различной длины.

Answer 3

Это не очень распространенная проблема. Я думаю, что наиболее эффективным будет просто перебрать. Было бы просто сделать код простым. Не самое эффективное, но я не вижу лучшего решения.