가장 긴 공통 하위 문자열 문제

컴퓨터 과학에서 가장 긴 공통의 하위 문자열 문제는 둘 이상의 하위 문자열인 가장 긴 줄을 찾는 것이다.그 문제에는 여러 가지 해결책이 있을 수 있다.애플리케이션에는 데이터 중복 제거와 표절 탐지가 포함된다.

예

문자열 "ABABC", "BABCA" 및 "ABCB"의 가장 긴 공통 하위 문자열A는 길이 3의 문자열 "ABC"이다.다른 일반적인 하위 문자열은 "A", "AB", "B", "BA", "BC" 및 "C"이다.

ABABC BABCA ABCBA

문제 정의

$길이$ $m$ {\ $displaystyle$ m}의S ${\displaystyle$ S $}$ 과 $m$ 길이 $n$ $n$ 의 $T$ $S$ T ${\displaystyle T$ $}$ 두 개의 문자열을 지정하면 $n$ S $S$ 과 T ${\displaystyt$ }의 하위 문자열 중 가장 긴 문자열을 찾으십시오 $T$

일반화는 k-공통 하위 문자열 문제다.Given the set of strings $S=\{S_{1},...,S_{K}\}$ , where $S_{i} =n_{i}$ and $\Sigma n_{i}=N$ . Find for each $2\leq k\leq K$ , the longest strings which occur as substrings of at최소 k $([\displaystyle k}$ 개 $k$ .

알고리즘

일반화 접미사 트리의 도움으로 $\Theta$ ${\displaystyle \Theta$ $(n+m)$ + $(n+m)$ ) $(n+m)$ {\ $displaystyle(n+m)$ 시간에서 $T$ $(n+m)$ $S$ {\ $displaystyle S}$ 및 $T$ ${\displaystytle T$ }의 $S$ 가장 긴 공통 서브스트링의 길이와 시작 위치를 찾을 수 있다.A faster algorithm can be achieved in the word RAM model of computation if the size $\sigma$ of the input alphabet is in $2^{o({\sqrt {\log(n+m)}})}$ . In particular, this algorithm runs in ${\displaystyle O((n+m)\log$ $\sigma /{\sqrt {\\log(n+m)}}}$ $O((n+m)\log \sigma /\log(n+m))$ $O((n+m)\log \sigma /\log(n+m))$ O $O((n+m)\log \sigma /\log(n+m))$ + $O((n+m)\log \sigma /\log(n+m))$ ) $O((n+m)\log \sigma /\log(n+m))$ / log $O((n+m)\log \sigma /\log(n+m))$ ( $O((n+m)\log \sigma /\log(n+m))$ + $O((n+m)\log \sigma /\log(n+m))$ ) $O(n+m)\log \sigma /\log(n+m)$ 공간을 $O((n+m)\log \sigma /\log(n+m))$ 사용한다.^[1]동적 프로그래밍을 통한 문제 해결 비용은 $\Theta (nm)$ ( $\Theta (nm)$ $\Theta (nm)$ ) $\Theta (nm)$ 입니다 $\Theta (nm)$ 일반화된 문제에 대한 해결책은 $\Theta (n_{1}+...+n_{K})$ ( $\Theta (n_{1}+...+n_{K})$ 1 $\Theta (n_{1}+...+n_{K})$ + $\Theta (n_{1}+...+n_{K})$ . $\Theta (n_{1}+...+n_{K})$ . $\Theta (n_{1}+...+n_{K})$ . + n $\Theta (n_{1}+...+n_{K})$ $){\displaystyle \Theta (n_{1}+...)$ 를 취한다. $+n_{K}}$ 공간 $\Theta (n_{1}+...+n_{K})$ 및 $\Theta (n_{1}$ $\Theta (n_{1}$ ${\$ ·... $\Theta (n_{1}$ · n $n_{K})$ ) $n_{K})$ {\ $displaystyle n_{K}}$ 동적 프로그래밍의 $\Theta (N*K)$ $\Theta (N*K)$ k $\Theta (N*K)$ ) $\Theta (N*K)$ {\ $displaystyle \Theta(N*K)}$ 시간을 $\Theta (N*K)$ 일반화 접미사 트리로 가져간다.

접미사 트리

"ABAB", "BABA" 및 "ABBA" 문자열의 일반화 접미사 트리는 0, 1, 2로 번호가 매겨졌다.

문자열 집합의 가장 긴 공통 하위 문자열은 문자열의 일반화된 접미사 트리를 만든 다음 그 아래 하위 트리의 모든 문자열에서 리프 노드가 있는 가장 깊은 내부 노드를 찾는 방법으로 찾을 수 있다.오른쪽 그림은 고유한 문자열 터미네이터로 패딩된 'ABAB', 'BABA', 'ABBA' 문자열의 접미사 트리로, 'ABAB$0', 'BA$1', 'ABBA$2'가 된다."A", "B", "AB" 및 "BA"를 나타내는 노드는 모두 모든 문자열에서 0, 1, 2의 하위 잎을 가진다.

접미사 트리를 작성하려면 $\Theta (N)$ ) $\Teta(N)$ 시간이 $\Theta (N)$ 소요된다(문자 크기가 일정한 경우).각 노드 아래에 어떤 문자열이 보이는지 알려주는 비트 벡터로 트리를 아래에서 위로 가로지르면 k-공통 하위 문자열 문제는 $\Theta (NK)$ $\Theta (NK)$ ) ${\displaystyle \Theta($ NK $)}$ 시간에 해결할 $\Theta (NK)$ 수 있다.접미사 트리가 일정 시간 가장 낮은 공통 조상 검색을 위해 준비되면 $\Theta (N)$ {( $\Theta (N)$ ) $\Teta(N)$ 시간에 해결할 $\Theta (N)$ 수 있다.^[2]

동적 프로그래밍

다음은 동적 프로그래밍이 있는 두 문자열 사이에서 가장 긴 공통 하위 문자열 집합을 찾는 유사 코드:

기능 LCSubstr(S[1..r], T[1..n])L:=array(1..r, 1..n)z:=0물에 담그다:나를 위하여{}:=1..r j:=1..n 만약 S[나는])T[j]만약 내 정도 1또는 j-1L[나는, j]:=1 다른 L[나는, j]:)L[나는 1, j− 1−]+1만약 L[나는, j]>zz.:)L[i, j] ret := {S[i - z + 1..i]} L[i, j] = z ret := ret ∪ {S[i - z + 1..i]} 다른 L[i, j] := 0 반환 재시도

이 알고리즘은 $O(nr)$ $O(nr)$ ) $O(nr)$ 시간 $O(nr)$ 단위로 실행된다.배열L접두사의 가장 긴 공통 부분을 저장하다.S[1..i]그리고T[1..j]어느 쪽이 그 위치에서 끝나는가. S[i],T[j], resp. 변수z지금까지 발견된 가장 긴 공통 하위 문자열의 길이를 유지하는 데 사용된다.세트ret길이가 긴 문자열 세트를 고정하는 데 사용됨z. 세트ret인덱스를 저장하기만 하면 효율적으로 저장할 수 있다.i, 즉, 가장 긴 공통 하위 문자열(z 크기)의 마지막 문자 입니다.S[i-z+1..i]따라서 모든 가장 긴 공통 기둥이 각각의 I에 대해ret,S[(ret[i]-z)..(ret[i])].

구현의 메모리 사용을 줄이기 위해 다음과 같은 방법을 사용할 수 있다.

메모리를 저장하려면 DP 테이블의 마지막 행과 현재 행만 유지하십시오 $O(nr)$ $O(\min(r,n))$ ( $O(\min(r,n))$ $O(nr)$ ( , $O(\min(r,n))$ ) $O(\min(r,n))$ {\ $displaystyle O(\min(r$ ,n $)})$ 대신 $O(\min(r,n))$ $O(nr)$ {\ $O(nr)$ O(\ $displaysty$ O $(nr)}).$
0이 아닌 값만 행에 저장하십시오.이것은 배열 대신 해시태블을 사용하여 할 수 있다.이것은 큰 알파벳에 유용하다.

참고 항목

가장 긴 팔린드로믹 하위 문자열
n-그램, 문자열에 포함된 모든 가능한 길이 n의 하위 문자열

참조

^ Charalampopoulos, Panagiotis, Kociumaka, 토머스, 피시스 솔론은 P.;Radoszewski Jakub(8월 2021년).Mutzel, 페트라, Pagh, 라스 머스, 허먼, Grzegorz(eds.).더 빨리 달려 알고리즘 가장 긴 공통 Substring.유럽 심포지엄 알고리즘에.라이프니츠 국제 담론 정보 과학(LIPIcs)에서.Vol204.슐로스 Dagstuhl.doi:10.4230/LIPIcs.ESA.2021.30.여기:정리 1, p.30:2.
^ Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8.

외부 링크

[CKPR21-1] Charalampopoulos, Panagiotis, Kociumaka, 토머스, 피시스 솔론은 P.;Radoszewski Jakub(8월 2021년).Mutzel, 페트라, Pagh, 라스 머스, 허먼, Grzegorz(eds.).더 빨리 달려 알고리즘 가장 긴 공통 Substring.유럽 심포지엄 알고리즘에.라이프니츠 국제 담론 정보 과학(LIPIcs)에서.Vol204.슐로스 Dagstuhl.doi:10.4230/LIPIcs.ESA.2021.30.여기:정리 1, p.30:2.

[Gus97-2] Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8.

[1]

[2]

v t 줄들
문자열 메트릭	대략적인 문자열 일치 비트맵 알고리즘 다메라우-레벤슈테인 거리 거리 편집 게슈탈트 패턴 매칭 해밍 거리 자로-윙클러 거리 리 거리 레벤슈테인 오토매틱 레벤슈테인 거리 바그너-피셔 알고리즘
문자열 검색 알고리즘	아포토리코-지안카를로 알고리즘 보이어-무어 문자열 검색 알고리즘 보이어-무어-호스풀 알고리즘 크누스-모리스-프라트 알고리즘 라빈-카프 알고리즘
다중 문자열 검색	아호코라식 코멘트-발터 알고리즘
정규식	정규 표현 엔진의 비교 정규문법 톰프슨의 건설 비결정론적 유한자동화
시퀀스 정렬	허슈베르크 알고리즘 니들먼-운슈 알고리즘 스미스-워터맨 알고리즘
데이터 구조	DAFSA 접미사 배열 자동 접미사 접미사 트리 일반화 접미사 트리 밧줄 3차 검색 트리 트라이
기타	파싱 패턴 매칭 압축 패턴 매칭 가장 긴 공통 부분 가장 긴 공통 하위 문자열 순차 패턴 마이닝 정렬

Search