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

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)]

我不想只是最长的范围,比如在算法中找到最长的非重叠序列,但我希望所有范围最长时间折叠.

万一你想知道,我正在使用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)]