Эффективный алгоритм для нахождения перекрытий строк

Question

Я не буду вдаваться в подробности проблемы, которую я пытаюсь решить, но она имеет дело с большой строкой и включает в себя поиск перекрывающихся интервалов, существующих в строке. Я могу использовать только один из интервалов, которые перекрываются, поэтому я хотел отделить эти интервалы и проанализировать их по отдельности. Мне было интересно, какой алгоритм использовать, чтобы сделать это максимально эффективно.

Я должен подчеркнуть, что здесь важна скорость. Мне нужно как можно быстрее отделить интервалы. Алгоритм, который пришел мне на ум, был Деревом Интервала, но я не был уверен, что это лучшее, что мы можем сделать.

Интервал Деревья могут быть запрошены в O (log n), n - количество интервалов, а для построения требуется O (nlog n) время, хотя я хотел знать, можем ли мы срубить их.

Спасибо!

Редактировать: Я знаю, вопрос неопределенный. Прошу прощения за путаницу. Я предлагаю, чтобы люди смотрели на ответ Аарона Хурана и комментарии к ним. Это должно помочь прояснить ситуацию намного больше.

Answer 1

Ну, мне было скучно прошлой ночью, поэтому я сделал это на Python. Это рекурсивно без необходимости (я только что прочитал The Little Schemer и думаю, что рекурсия супер аккуратная прямо сейчас), но она решает вашу проблему и обрабатывает все входные данные, которые я выбрал.

intervals = [(0,4), (5,13), (8,19), (10,12)] 

def overlaps(x,y): 
    x1, x2 = x 
    y1, y2 = y 
    return ( 
     (x1 <= y1 <= x2) or 
     (x1 <= y2 <= x2) or 
     (y1 <= x1 <= y2) or 
     (y1 <= x2 <= y2) 
    ) 

def find_overlaps(intervals, checklist=None, pending=None): 
    if not intervals: 
     return [] 

    interval = intervals.pop() 

    if not checklist: 
     return find_overlaps(intervals, [interval], [interval]) 

    check = checklist.pop() 

    if overlaps(interval, check): 
     pending = pending or [] 
     checklist.append(check) 
     checklist.append(interval) 
     return pending + [interval] + find_overlaps(intervals, checklist) 
    else: 
     intervals.append(interval) 
     return find_overlaps(intervals, checklist) 

Использование так:

>>> find_overlaps(intervals) 
[(10, 12), (8, 19), (5, 13)] 

Обратите внимание, что он возвращает все перекрывающиеся интервалы в порядке, обратном порядку их начальной точки. Надеюсь, это второстепенная проблема. Это происходит только потому, что я использую push() и pop() в списке, который работает в конце списка, а не insert(0) и pop(0), который работает в начале.

Это не идеально, но оно работает в линейном времени. Также помните, что размер фактической строки вообще не имеет значения - время работы зависит от количества интервалов, а не от размера строки.

Answer 2

Вы хотите рассчитать разницу между двумя строками вправо? На каком языке вы пытаетесь это сделать?

Обновление: Без каких-либо критериев, как вы будете выбирать, какие интервалы использовать, есть огромные возможные решения.

Одним из способов было бы принять наименьшее начальное число, захватить его конец. Захватите следующий стартовый номер, который больше, чем конец предыдущего интервала. Получить конец этого интервала и повторить.

Итак, для 0-4, 5-13, 8-19, 10-12 Вы получаете: 0-4, 5-13 и игнорируете остальные.

Answer 3

Возможно, вы захотите попробовать использовать алгоритм Укконена (см. https://en.wikipedia.org/wiki/Ukkonen%27s_algorithm).

Существует бесплатная версия кода на http://biit.cs.ut.ee/~vilo/edu/2002-03/Tekstialgoritmid_I/Software/Loeng5_Suffix_Trees/Suffix_Trees/cs.haifa.ac.il/shlomo/suffix_tree/suffix_tree.c