我正在寻找解决此问题的内存效率最高的方法。
我有一个表示句子中部分字符串匹配的元组列表:
[(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
andzeta
的匹配项betazeta
是[(0,5),(4,8)]
。由于这些范围重叠,但没有包含在另一个范围内,因此答案应该是[(0,5),(4,8)]
。我还修改了上面的输入数据集,以便涵盖这种情况。
谢谢!