루조-톰파 알고리즘

Ruzo-Tompa 알고리즘은 일련의 실수에서 모든 비 오버랩, 연속, 최대 스코어링을 찾기 위한 선형 시간 알고리즘이다.^[1]이 알고리즘은 이전에 알려진 2차 시간 알고리즘보다 개선된 것이다.알고리즘에 의해 생성된 집합에서 최대 점수 부속도 최대 서브 어레이 문제에 대한 해결책이다.

Ruzo-Tompa 알고리즘은 생물정보학, ^[2]웹 스크래핑 ^[3]및 정보 검색에 응용할 수 있다.^[4]

적용들

생물정보학

Ruzo-Tompa 알고리즘은 생물정보학 도구에서 생물학적 데이터를 연구하기 위해 사용되어 왔다.분리막 최대 반복을 찾는 문제는 DNA 분석에서 실제적으로 중요하다. 최대 반복 알고리즘은 투과성 분절의 식별과 시퀀스 호몰로지 평가에 사용되어 왔다.^[2]

알고리즘은 유사한 DNA, RNA 또는 단백질 시퀀스를 식별하는 방법으로 사용되는 시퀀스 정렬에 사용된다.두 시퀀스에서 높은 점수의 반복 쌍 순서를 설명하면 더 나은 시퀀스 정렬이 생성된다.이는 생물학적 모형이 서로 일치하는 영역 내의 삽입 또는 삭제에서 분리된 높은 점수의 반복 쌍이 발생함을 암시하기 때문이다.높은 점수의 하위 쌍을 일관성 있게 정렬해야 하는 경우 통계적 유의성이 증가한다.^[2]

웹 스크래핑

루조-톰파 알고리즘은 웹페이지에서 정보를 추출하기 위해 웹 스크래핑에 사용된다.Pasternack과 Roth는 HTML 문서에서 중요한 텍스트 블록을 추출하는 방법을 제안했다.웹 페이지는 먼저 토큰화되고 각 토큰의 점수는 로컬 토큰 레벨 분류기를 사용하여 발견된다.그런 다음, K의 가장 높은 가치의 토큰을 찾기 위해 Ruzo-Tompa 알고리즘의 수정된 버전을 사용한다.이러한 부분들은 기사에서 중요한 텍스트 블록의 예측으로 사용된다.^[3]

정보 검색

루조-톰파 알고리즘은 정보 검색 알고리즘에서 사용되어 왔다.량 외에서는 여러 마이크로블로그 검색 알고리즘의 검색 결과를 결합하는 데이터 융합 방식을 제안했다.그들의 방법에서, 루조-톰파 알고리즘은 정보의 폭발을 감지하는 데 사용된다.^[4]

문제 정의

$모든$ 최대 재열을 찾는 문제는 다음과 같이 정의된다:실제 번호가 매겨진 $점수{\displaystyle {}_{}}$ x 1,${\displaystyle {}_{}{x\mathrm{}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$…$$ $n$을 기준으로 하여$,$ 큰 총점을 주는 연속적인 재주 목록을 찾아라$,$ $여기$서 각 $재주점{\displaystyle {}_{}}$ ${\displaystyle S_{}}$i , ${\displaystyle j_{}}$ =${\displaystyle \underset{k}{}}$ k${\displaystyle \underset{}{j}}$ j $kdi$ {$n$$}.$$splaystyle S_{i,j}=\sum _{i\leq k\leq j}x_{k$반복은 분리(오버랩되지 않음)되어야 하며, 플러스 점수를 가져야 한다.

기타 알고리즘

모든 최대 점수 추가 문제를 해결하기 위한 몇 가지 접근법이 있다.자연스러운 접근방식은 기존의 선형 시간 알고리즘을 사용하여 최대 하위 배열 문제(최대 하위 배열 문제 참조)를 찾은 다음 최대 하위 배열의 왼쪽과 오른쪽으로 최대 하위 배열 문제를 재귀적으로 찾아내는 것이다.이 알고리즘의 분석은 Quicksort의 분석과 유사하다.최대 하위열은 나머지 시퀀스에 비해 작을 수 있으며 최악의 경우 실행 $시간$이 O (${\displaystyle }$n ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle O(n^{2})$로 이어질 수 있다.

알고리즘.

미디어 재생

이 애니메이션은 그래프에서 각각 선 세그먼트로 표현되는 11개의 정수의 입력 시퀀스로 실행 중인 Ruzo-Tompa 알고리즘을 보여준다.굵은 선으로 된 세그먼트는 지금까지 발견된 최대 세그먼트를 나타낸다.애니메이션은 각 단계에서$$ $I{\displaystyle }$, ${\displaystyle R}$ ${\displaystyle I,R}$ 및$$ $L{\displaystyle }$ ${\displaystyle L}$의 상태를 보여준다.그 아래는 이 페이지의 알고리즘 섹션에 있는 1-4 단계에 해당하는 알고리즘의 현재 상태를 보여준다.빨간색 강조 표시는 $1단계$와 3단계에서$$ j ${\displaystyle j}$에 대한 값을 찾는 알고리즘을 보여준다.$j{\displaystyle }$ ${\displaystyle j}$의 값이 해당 단계의 불평등을 충족하면$$ 하이라이트가 녹색으로 변한다.애니메이션이 끝나면 최대 반복이 굵게 표시되고 $I{\displaystyle }$ ${\displaystyle I}$에 표시된다$.$

Ruzo-Tompa 알고리즘의 표준 구현은 $O{\displaystyle }$(${\displaystyle n}$) ${\displaystyle O(n)}$시간에$$ 실행되며, 여기서 n은 점수 목록의 길이인 O(n) 공간을 사용한다.알고리즘은 동적 프로그래밍을 사용하여 문제의 더 큰 하위 집합을 점진적으로 점진적으로 해결함으로써 최종 솔루션을 점진적으로 구축한다.루조와 톰파가 제공하는 알고리즘에 대한 설명은 다음과 같다.

왼쪽에서 오른쪽으로 점수를 읽고 읽은 점수의 누적 합계를 유지한다.정렬된 ${\displaystyle {목록\mathrm{}}_{}}$ I 1,${\displaystyle {}_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle \dots ,}$ ${\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\$을(를) 유지 관리하십시오.각 부속품 $I{\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\$에 대해$,$ I $j{\displaystyle {}_{}}$ ${\$의 가장 왼쪽 점수를 포함하되 포함하지 않는 모든 점수의$$ 누적 총 ${\displaystyle L_{}}$ j ${\$$\}\},$ $그리고{\displaystyle {}_{}}$ $전체{\displaystyle {}_{}}$ R ${\displaystyle j_{}}$$$${\$ $R_{j}}$을 가장 오른쪽 점수로$$ 기록하십시오.$I_{j$

리스트는 처음에 비어 있다.점수는 왼쪽에서 오른쪽으로 읽고 다음과 같이 처리한다.부정점수는 특별한 처리가 필요하지 않기 때문에 다음 점수를 읽는다.긍정 점수는 길이 1의 새로운$$ 하위 순서 $I{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$에 통합되며, 그 다음 프로세스에 의해 목록으로 통합된다.

1. 목록 $I{\displaystyle }$ ${\displaystyle I}$을(를) 오른쪽에서 왼쪽으로 검색하여$$ < {\displaystyle $L_{j}<$을$$) 만족시키는 j ${\$$displaystyle$ $j}$의 최대값을 찾는다.$L_{k}}}$
2. 이러한 $j{\displaystyle }$ ${\displaystyle j}$이$($가) 없는 경우 목록 끝에$$ ${\displaystyle I_{}}$ k ${\$를 추가하십시오.
3. 이러한 $j{\displaystyle }$ ${\displaystyle j}$및 $R{\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle R_{}}$ ${\displaystyle {}_{}}$ ${\$이$($가) 있으면 목록 끝에$$ $I{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$를 추가하십시오.
4. 그렇지 않으면(즉, 그런 j지만, Rj<>Rk{\displaystyle R_{j}< 있다.나는}{\displaystyle I_{j}j R_{k}}), 왼쪽으로 걸어가서 그 제일 왼쪽의 점수 등 모든 것을 포함할 예정. 나는 j subsequences를 삭제하시오, 나는+1j,…, 나는 − 1{\displays k 나는{\displaystyle I_{km그리고 4.9초 만}k은 다음}을 연장한다.$tyle I_{j},$목록에서$$ $I_{j}+1,\ldots, I_{k}-1$}을$($를) 추가하고 목록 끝에$$ ${\displaystyle I_{}}$ k ${\$을(를) 추가하십시오.1단계에서와 같이 새로 확장된 하위열 $I{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$이제는 $번호{\displaystyle {}_{}}$ ${\displaystyle I_{}}$ j$${\$displaystyle I_{j$를 다시 생각해 보십시오.

입력의 끝에 도달하면 목록 $I{\displaystyle }$ ${\displaystyle I}$에 남아 있는 모든 반복이 최대값이다$$.^[1]

다음 파이톤 코드는 루조-톰파 알고리즘을 구현한다.

반항하다 루조_톰파(점수):     """루조-톰파 알고리즘."""     k = 0     총계 = 0     # 크기가 n인 배열 할당     I, L, R, 리덱스 = [[0] * 렌(점수) 을 위해 _ 에 범위(4)]     을 위해 i, s 에 열거하다(점수):         총계 += s         만일 s > 0:             # 점수의 (시작, 끝) 지수별로 I[k] 저장             I[k] = (i, i + 1)             리덱스[k] = i             L[k] = 총계 - s             R[k] = 총계             하는 동안에 진실의:                 맥스 = 없음                 을 위해 j 에 범위(k - 1, -1, -1):                     만일 L[j] < L[k]:                         맥스 = j                         부숴뜨리다                 만일 맥스 이다 아닌 없음 그리고 R[맥스] < R[k]:                     I[맥스] = (리덱스[맥스], i + 1)                     R[맥스] = 총계                     k = 맥스                 다른:                     k += 1                     부숴뜨리다     # 저장된 인덱스를 사용하여 최대 재속도를 얻음     돌아오다 [점수[I[l][0] : I[l][1]] 을 위해 l 에 범위(k)] 

참조