2

我有一个带有{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)

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

4

2 回答 2

2

您可以使用区间树。

我不懂 Python，但我认为你在这里做的是蛮力。

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

0 3 4 5 7 10 15 18 19

现在遍历每个起始索引并通过二进制搜索检查其对应的结束索引在起始索引之后的位置，即这里我们取 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。

于 2012-07-10T13:01:51.777 回答
0

而不是occupied = [False]*string_length您可以维护一个存储迄今为止看到的非重叠范围并支持.overlaps(start, end)操作的数据结构：

def overlaps(self, start, end):
    # invariant: all stored intervals do not overlap
    # perform binary search on non-overlapping intervals O(log n)
    # if overlaps; merge with stored intervals O(m)
    # else store (start, end) O(1)
    # return whether (start, end) overlaps with already seen intervals

复杂性是O(log n + m)，其中n- 存储间隔的m数量， - 与给定范围重叠的间隔数量。

如果string_length不是很大，您的算法看起来还不错。

于 2012-07-10T16:35:45.737 回答