python - 将范围元组列表折叠到重叠范围中

Question

我正在寻找最节省内存的方法来解决这个问题。

我有一个表示句子中部分字符串匹配的元组列表:

[(0, 2), (1, 2), (0, 4), (2,6), (23, 2), (22, 6), (26, 2), (26, 2), (26, 2)]

每个元组的第一个值是匹配的开始位置，第二个值是长度。

这个想法是折叠列表，以便只报告最长的继续字符串匹配。在这种情况下，它将是:

[(0,4), (2,6), (22,6)]

我不想要最长的范围，比如 algorithm to find longest non-overlapping sequences ，但我希望所有范围以最长的时间折叠。

如果您想知道，我正在使用 Aho-Corasick 的纯 Python 实现将静态字典中的术语与给定的文本片段进行匹配。

编辑:由于这些元组列表的性质，重叠但不是独立的范围应该单独打印出来。例如，有词 betaz和 zeta在字典中，匹配 betazeta是 [(0,5),(4,8)] .由于这些范围重叠，但不包含在其他范围内，因此答案应该是 [(0,5),(4,8)] .我还修改了上面的输入数据集，以便涵盖这种情况。

谢谢!

Answer 1

import operator
lst = [(0, 2), (1, 2), (0, 4), (2,6), (23, 2), (22, 6), (26, 2), (26, 2), (26, 2)]
lst.sort(key=operator.itemgetter(1))
for i in reversed(xrange(len(lst)-1)):
    start, length = lst[i]
    for j in xrange(i+1, len(lst)):
        lstart, llength = lst[j]
        if start >= lstart and start + length <= lstart + llength:
            del lst[i]
            break
print lst
#[(0, 4), (2, 6), (22, 6)]