在两个不同长度的非相同未排序 python 列表中处理 matching/joining 元素的最佳方法是什么？

Question

例如，我有以下 python 列表：

a = [1,2,1,3,2,1,1,1,2,1,1,1,1,1,3,1,2]  
b = [1,1,2,1,3,1,1,1,1,2,2,1,1,1,1,3,1,2]

我想获取可以自信匹配的元素的索引元组，例如：

[(0,0), (1,2), (2,3), (3,4), (8,9), (14,15), (15,16), (16,17)]

数据代表了记录到达和离开队列的人数，但数据也不是完美的，所以a和b的总和不匹配，人也不总是需要按照他们到达的顺序离开。

我知道它取决于几个变量（或阈值参数），但我只是在寻找有关如何最好地解决问题的建议。我很乐意使用 Pandas/Numpy/Scipy 来完成这项工作。

我发现这很难解释。靠眼睛，我很容易匹配部分序列，例如1,2,1,3。不过，找到一个好的算法方法并不是那么容易。

Answer 1

我不完全理解你的输出，但要按顺序获取匹配的元素索引：

a = [1, 2, 1, 3, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 2]
b = [1, 1, 2, 1, 3, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 3, 1, 2]
from collections import defaultdict, deque

d = defaultdict(deque)
for i, j in enumerate(b):
    d[j].append(i)

print([(i, d[j].popleft()) for i, j in enumerate(a)])

我能匹配你的输出的唯一方法是我们考虑不是序列的元素：

from itertools import groupby 
from operator import itemgetter

def pairs(a, b):
    for (k, v) in (groupby(enumerate(a), key=itemgetter(1))):
        data = next(v)
        if not next(v, None):
            ind, val = data
            if b[ind] == val:
                yield (ind, ind)
            elif val == b[ind + 1]:
                yield (ind, ind + 1)

 print(list(pairs(a, b)))

哪个会给你：

[(0, 0), (1, 2), (2, 3), (3, 4), (8, 9), (14, 15), (15, 16), (16, 17)]

Answer 2

我终于意识到 Python 有 difflib 库来处理这种事情！

a = [1, 2, 1, 3, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 2]  
b = [1, 1, 2, 1, 3, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 3, 1, 2]  

from difflib import SequenceMatcher  

s = SequenceMatcher(None, a, b, autojunk=False)  

matched_element_indices = []
for m in s.get_matching_blocks():
    matched_element_indices += [(m.a+i,m.b+i) for i in range(m.size)]

它产生这个：

In : matched_element_indices
Out: [(0, 1), (1, 2), (2, 3), (3, 4), (5, 6), (6, 7), (7, 8), (8, 9), 
           (10, 11), (11, 12), (12, 13), (13, 14), (14, 15), (15, 16), (16, 17)]

在两个不同长度的非相同未排序 python 列表中处理 matching/joining 元素的最佳方法是什么？

What is the best approach to matching/joining elements in two non-identical unsorted python lists of different lengths?

python

numpy

pattern-matching

matching

fuzzy-comparison