문자열 오버랩을 찾는 효율적인 알고리즘

Question

해결하려고하는 문제에 대해서는 자세히 설명하지 않지만 큰 문자열을 처리하고 문자열에 겹치는 간격을 찾는 작업이 포함됩니다. 중복되는 간격 중 하나만 사용할 수 있으므로이 간격을 분리하고 개별적으로 분석하려고했습니다. 가능한 효율적으로이 작업을 수행하는 데 어떤 알고리즘이 사용되는지 궁금합니다.

속도가 가장 중요하다는 사실을 강조해야합니다. 가능한 한 빨리 간격을 분리해야합니다. 내 마음에 온 알고리즘은 인터벌 트리 (Interval Tree) 였지만, 이것이 우리가 할 수있는 최선인지는 확실하지 않았습니다.

간격 나무는 O (log n) 시간에 쿼리 할 수 ​​있습니다. n은 간격 수이고 O (nlog n) 시간이 필요합니다.하지만 어느 쪽을 줄일 수 있는지 알고 싶습니다.

감사합니다.

편집 : 질문이 모호하다는 것을 알고 있습니다. 혼란에 대해 사과드립니다. 저는 사람들이 Aaron Huran의 답변과 그에 대한 의견을 살펴볼 것을 제안합니다. 그것은 많은 것을 명확히하는 데 도움이 될 것입니다.

Answer 1

글쎄, 나는 어젯밤 지루했기 때문에 이것을 파이썬에서했다. 그것은 불필요하게 재귀 적입니다. (저는 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

Ukkonen 알고리즘을 사용해보십시오 (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