如何从字典列表中筛选基于起止字符索引的最长区间条目？

我们有如下格式的字典列表，需要清洗掉被更长区间完全包含的条目，只保留覆盖范围最大的区间条目：

原始输入：

[{'name': 'NOUN-NOUN', 'start_char': 91, 'end_char': 105, 'lemma': 'digital groupe', 'text': 'digital groupe'} ,
{'name': 'NOUN', 'start_char': 91, 'end_char': 98, 'lemma': 'digital', 'text': 'digital'},
{'name': 'NOUN', 'start_char': 99, 'end_char': 105, 'lemma': 'groupe', 'text': 'groupe'},
{'name': 'NOUN-PROPN', 'start_char': 99, 'end_char': 113, 'lemma': 'groupe siparex', 'text': 'groupe siparex'},
{'name': 'NOUN-NOUN-PROPN', 'start_char': 91, 'end_char': 113, 'lemma': 'digital groupe siparex', 'text': 'digital groupe siparex'},

{'name': 'PROPN-PROPN', 'start_char': 0, 'end_char': 12, 'lemma': 'Jean François', 'text': 'Jean François'}
]

期望输出：

[{'name': 'NOUN-NOUN-PROPN', 'start_char': 91, 'end_char': 113, 'lemma': 'digital groupe siparex', 'text': 'digital groupe siparex'},
{'name': 'PROPN-PROPN', 'start_char': 0, 'end_char': 12, 'lemma': 'Jean François', 'text': 'Jean François'}]

实现思路 #

核心逻辑是保留不被任何其他条目区间完全包含的条目：对每个条目，检查是否存在另一个条目，其start_char≤当前条目start_char，且end_char≥当前条目end_char（排除条目自身）。如果不存在这样的条目，就保留当前条目。

代码实现 #

def filter_longest_intervals(items):
    filtered = []
    for item in items:
        is_contained = False
        curr_start = item['start_char']
        curr_end = item['end_char']
        # 检查当前条目是否被其他条目完全包含
        for other in items:
            if item is other:
                continue
            if other['start_char'] <= curr_start and other['end_char'] >= curr_end:
                is_contained = True
                break
        if not is_contained:
            filtered.append(item)
    return filtered

# 原始数据
input_data = [
    {'name': 'NOUN-NOUN', 'start_char': 91, 'end_char': 105, 'lemma': 'digital groupe', 'text': 'digital groupe'},
    {'name': 'NOUN', 'start_char': 91, 'end_char': 98, 'lemma': 'digital', 'text': 'digital'},
    {'name': 'NOUN', 'start_char': 99, 'end_char': 105, 'lemma': 'groupe', 'text': 'groupe'},
    {'name': 'NOUN-PROPN', 'start_char': 99, 'end_char': 113, 'lemma': 'groupe siparex', 'text': 'groupe siparex'},
    {'name': 'NOUN-NOUN-PROPN', 'start_char': 91, 'end_char': 113, 'lemma': 'digital groupe siparex', 'text': 'digital groupe siparex'},
    {'name': 'PROPN-PROPN', 'start_char': 0, 'end_char': 12, 'lemma': 'Jean François', 'text': 'Jean François'}
]

# 执行过滤
result = filter_longest_intervals(input_data)
print(result)

代码说明 #

1. 定义filter_longest_intervals函数，接收字典列表作为参数。
2. 遍历每个条目，逐一检查是否被其他条目完全包含。
3. 若当前条目不被任何其他条目包含，则加入结果列表。
4. 返回的结果列表即为仅保留最长区间条目的清洗后数据。

内容的提问来源于stack exchange，提问作者Alain Pulcini