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

我正在寻找解决这个问题的最有效内存的方法.

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

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

每个元组的第一个值是匹配的起始位置,第二个值是长度.

我们的想法是折叠列表,以便仅报告最长的继续字符串匹配.在这种情况下,它将是：

[(0,6)]

我不想要最长的范围,比如algorithm to find longest non-overlapping sequences,但是我希望所有的范围都是最长的.

万一你想知道,我正在使用Aho-Corasick的纯python实现来将静态字典中的术语与给定的文本片段进行匹配.

编辑：由于这些元组列表的性质,应单独打印重叠但不是自包含的范围.例如,在字典中使用单词betaz和zeta,betazeta的匹配是[(0,5),(4,8)].由于这些范围重叠,但没有一个包含在另一个中,答案应该是[(0,8)].我还修改了上面的输入数据集,以便涵盖这种情况.

谢谢！

import operator
lst = [(0,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,6)]

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!