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 の整数キーが 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 に答える