Python - 过滤重叠范围

Question

我有一个 map ，其中 {integer_key -> list[tuple]} 作为键/值对。元组包含表示子字符串操作的字符串索引的 (start,end) 值。

我的目标是移除重叠区域并返回键/值对为 {tuple -> integer_key} 的映射。 映射到较低 integer_keys 的范围优先于较高范围。

下面是我当前实现的一个可运行示例(需要这个 ordereddict 类):

from collections import OrderedDict

string_length = 20

idx_region_map = OrderedDict()
idx_region_map[0] = [(0,2), (7,10)]
idx_region_map[1] = [(4,5), (18,19)]
idx_region_map[2] = [(3,3), (5,6), (10,13)]
idx_region_map[3] = [(15,17), (19,20)]

# Which can be represented as follows:
#
#  |012345678901234567890|
# 0|ooo----oooo----------|
# 1|----oo------------oo-|
# 2|---o-oo---oooo-------|
# 3|---------------ooo-oo|
# ...

def filter_overlaps(string_length, idx_region_map):
    region_idx_map = {}
    occupied = [False for i in range(string_length)]
    for idx, regions in idx_region_map.items():
        for region in regions:
            start, end = region[0], region[1] + 1
            overlaps = any(occupied[start:end])

            if not overlaps:
                for i in range(start, end):
                    occupied[i] = True
                region_idx_map[region] = idx
    return region_idx_map


# Prints: {(3, 3): 2, (4, 5): 1, (18, 19): 1, (7, 10): 0, (0, 2): 0, (15, 17): 3}
print filter_overlaps(string_length, idx_region_map)

这似乎足以满足我的需求，但我很想知道有哪些替代算法可以解决这个问题。例如，使用不同的数据结构或比上述更有效的东西。

Answer 1

您可以使用 Interval tree .

我不懂 Python，但我认为你在这里使用蛮力。

另一种方法是根据起始索引进行排序；所以对于你来说，你得到

0 3 4 5 7 10 15 18 19

现在遍历每个起始索引并通过二进制搜索检查其对应的结束索引位于 w.r.t 之后的起始索引，即这里我们取 0，获取其结束索引 2 并查看 2 位于何处。因为 2 紧跟在 0 之后，所以它不与任何东西重叠，但假设 0 的结束索引为 17，那么这意味着 0,17 与所有起始索引重叠，直到 15，即 3、4、5、7、10、15。复杂度为nlogn。

编辑

我刚刚意识到，尽管 4,5 和 5,6 重叠，但您保留了 4,5，我猜是因为 4,5 整数键为 1，小于 5,6 的整数键，即 2。所以我猜你总是保留较低的整数键，尽管它是重叠的。

如果是这种情况，复杂度将为 O(n^2)，因为您不能盲目地进行二分查找。例如如果 4 的结束索引是 10 那么你将不得不通过 5,7 和 10 来检查它们的整数键是否小于 4。如果是 4 则可以过滤其结束索引，否则保留 4。