高效的“序列对齐”，比较两个集合列表以查找匹配项

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} 在 list_1 的索引 1 和 {75， 37} 在 list_2 的索引 0 与 {42， 31} 在 list_1 的索引 2 和 {42， 37} 在索引 1 的 list_2 给出计数 2，因为我们有两个匹配项。对于上面的示例，输出数组应如下所示

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

列表的顺序很重要，因为这样，我试图找到重叠最大的时间点。

我一直在尝试使用集合和冻结集的交集，但由于它们周围有一些笨拙的for循环，所以没有太多的运气。

Answer 1

这不是一个非常常见的问题。我认为最有效的方法是迭代。使代码变得简单是很简单的。不是最有效的，但我没有看到更好的解决方案。

Answer 2

如果你需要效率（如果你需要经常使用这个代码，并且有时等待它），你可能会使用模糊匹配算法。大多数模糊匹配算法似乎都针对字符串，但它们可能是一个起点。如果这不是您要查找的内容，您可以尝试执行反向索引，例如：{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： {75， 37}}然后以这种方式计算在任何两对之间得到的重复项数。我相信它会是O（n）那样。

Answer 3

查找 Smith-Waterman 算法。它是一种DP算法，用于局部对齐不同长度的序列。