Свернуть список кортежей диапазонов в перекрывающиеся диапазоны

Question

Я ищу наиболее эффективный способ памяти для решения этой проблемы.

У меня есть список кортежей, представляющих частичные совпадения строк в предложении:

[(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 на Py thon для сопоставления терминов в статическом словаре с заданным фрагментом текста.

РЕДАКТИРОВАТЬ: Из-за характера этих списков кортежей перекрывающиеся, но не автономные диапазоны должны быть распечатаны по отдельности. Например, имея слова betaz а также zeta в словаре совпадения для betazeta являются [(0,5),(4,8)], Поскольку эти диапазоны перекрываются, но ни один не содержится в другом, ответ должен быть [(0,5),(4,8)], Я также изменил входной набор данных выше, чтобы охватить этот случай.

Спасибо!

Answer 1

import operator
lst = [(0, 2), (1, 2), (0, 4), (2,6), (23, 2), (22, 6), (26, 2), (26, 2), (26, 2)]
lst.sort(key=operator.itemgetter(1))
for i in reversed(xrange(len(lst)-1)):
    start, length = lst[i]
    for j in xrange(i+1, len(lst)):
        lstart, llength = lst[j]
        if start >= lstart and start + length <= lstart + llength:
            del lst[i]
            break
print lst
#[(0, 4), (2, 6), (22, 6)]

Answer 2

a = [(0, 2), (1, 2), (0, 4), (23, 2), (22, 6), (26, 2), (26, 2), (26, 2)]
b = [set(xrange(i, i + j)) for i, j in a]
c = b.pop().union(*b)
collapsed = sorted(c)
print collapsed
#Maybe this is useful?:
[0, 1, 2, 3, 22, 23, 24, 25, 26, 27]

#But if you want the requested format, then do this:
d = []
start = collapsed[0]
length = 0
for val in collapsed:
    if start + length < val:
        d.append((start,length))
        start = val
        length = 0
    elif val == collapsed[-1]:
        d.append((start,length + 1))
    length += 1
print d
#Output:
[(0,4), (22,6)]

Answer 3

Итак, заверяю вас, что ваш главный интерес - это космическая эффективность, вот один из способов сделать то, что вы хотите:

lst = [(0, 2), (1, 2), (0, 4), (23, 2), (22, 6), (26, 2), (26, 2), (26, 2)]
lst.sort()
start, length = lst.pop(0)
i = 0
while i < len(lst):
    x, l = lst[i]
    if start + length < x:
        lst[i] = (start, length)
        i += 1
        start, length = x, l
    else:
        length = max(length, x + l - start)
        lst.pop(i)
lst.append((start, length))

Это изменяет список на месте, никогда не делает список длиннее, использует только небольшое количество переменных для сохранения состояния и требует только одного прохода по списку.

Гораздо более быстрый алгоритм возможен, если вы не хотите изменять список на месте - извлечение элементов из середины списка может быть медленным, особенно если список длинный.

Одной из разумных оптимизаций было бы сохранить список индексов, которые вы собираетесь удалить, а затем вернуться и перестроить список за второй проход, чтобы вы могли перестроить весь список за один раз и избежать pop накладные расходы. Но это будет использовать больше памяти!