접미사 트리

컴퓨터 과학에서 접미사 트리, 서픽스 트리(suffix tree), PAT 트리 또는 이전 형태로는 위치 트리(position tree)는 주어진 텍스트의 모든 접미사를 키로, 텍스트 내 위치를 값으로 포함하는 압축된 트라이이다. 접미사 트리는 많은 중요한 문자열 연산을 특히 빠르게 구현할 수 있게 한다.

텍스트 BANANA의 접미사 트리. 각 부분 문자열은 특수 문자 $로 끝난다. 루트에서 리프(상자로 표시됨)까지의 6개 경로는 A$, NA$, ANA$, NANA$, ANANA$, BANANA$의 6개 접미사에 해당한다. 리프의 숫자는 해당 접미사의 시작 위치를 나타낸다. 점선으로 그려진 접미사 링크는 구성 중에 사용된다.

문자열 ${\displaystyle S}$에 대한 이러한 트리의 구성은 ${\displaystyle S}$의 길이에 비례하는 시간과 공간을 차지한다. 일단 구성되면, ${\displaystyle S}$에서 서브스트링을 찾거나, 특정 수의 오류가 허용될 경우 서브스트링을 찾거나, 정규 표현식 패턴에 대한 일치를 찾는 것과 같은 여러 연산을 빠르게 수행할 수 있다. 접미사 트리는 또한 최장 공통 부분 문자열 문제에 대한 최초의 선형 시간 솔루션 중 하나를 제공했다.^[2] 이러한 속도 향상은 비용을 수반한다. 문자열의 접미사 트리를 저장하는 것은 일반적으로 문자열 자체를 저장하는 것보다 훨씬 더 많은 공간을 필요로 한다.

역사

이 개념은 Weiner (1973)에 의해 처음 소개되었다. 위너는 접미사 ${\displaystyle S[i..n]}$ 대신, 그의 트라이^[3]에 각 위치에 대한 접두사 식별자를 저장했다. 즉, ${\displaystyle i}$에서 시작하여 ${\displaystyle S}$에 한 번만 나타나는 가장 짧은 문자열이다. 그의 알고리즘 D는 ${\displaystyle S[k+1..n]}$에 대한 비압축^[4] 트라이를 받아 ${\displaystyle S[k..n]}$에 대한 트라이로 확장한다. 이러한 방식으로, ${\displaystyle S[n..n]}$에 대한 자명한 트라이에서 시작하여, ${\displaystyle n-1}$번의 알고리즘 D의 연속적인 호출로 ${\displaystyle S[1..n]}$에 대한 트라이를 구축할 수 있다. 그러나 전체 실행 시간은 ${\displaystyle O(n^{2})}$이다. 위너의 알고리즘 B는 구성된 트라이의 크기에 비례하는 전체 실행 시간을 달성하기 위해 여러 보조 데이터 구조를 유지한다. 후자는 ${\displaystyle S=a^{n}b^{n}a^{n}b^{n}\$.}$의 경우처럼 여전히 ${\displaystyle O(n^{2})}$ 노드가 될 수 있다. 위너의 알고리즘 C는 최종적으로 압축된 트라이를 사용하여 선형 전체 저장 공간 및 실행 시간을 달성한다.^[5] 도널드 커누스는 나중에 후자를 그의 학생인 본 프랫에 따르면 "1973년의 알고리즘"으로 특징지었다.^{[독자연구?][6]} Aho, Hopcroft & Ullman (1974, Sect.9.5) 교과서는 위너의 결과를 단순하고 더 우아한 형태로 재현하며, 위치 트리(position tree)라는 용어를 도입했다.

McCreight (1976)는 ${\displaystyle S}$의 모든 접미사에 대한 (압축된) 트라이를 구축한 최초의 인물이었다. ${\displaystyle i}$에서 시작하는 접미사는 일반적으로 접두사 식별자보다 길지만, 압축된 트라이에서 이들의 경로 표현은 크기가 다르지 않다. 반면에 McCreight는 위너의 보조 데이터 구조 대부분을 없앨 수 있었고, 접미사 링크만 남았다.

Ukkonen (1995)는 구성을 더욱 단순화했다.^[6] 그는 현재 우코넨 알고리즘으로 알려진, 당시 가장 빠른 알고리즘과 실행 시간이 일치하는 접미사 트리의 최초 온라인 구성을 제공했다. 이러한 알고리즘은 모두 상수 크기 알파벳에 대해 선형 시간이며, 일반적으로 최악의 경우 ${\displaystyle O(n\log n)}$의 실행 시간을 가진다.

Farach (1997)는 모든 알파벳에 대해 최적의 접미사 트리 구성 알고리즘을 제시했다. 특히, 이는 다항 범위의 정수 알파벳에서 파생된 문자열에 대한 최초의 선형 시간 알고리즘이다. Farach의 알고리즘은 외부 메모리, 압축, 간결한 접미사 트리 및 접미사 배열을 구성하기 위한 새로운 알고리즘의 기반이 되었다.

정의

길이 ${\displaystyle n}$인 문자열 ${\displaystyle S}$에 대한 접미사 트리는 다음과 같은 트리로 정의된다.^[7]

1. 트리는 ${\displaystyle 1}$부터 ${\displaystyle n}$까지 번호가 매겨진 정확히 ${\displaystyle n}$개의 리프를 가진다.
2. 루트를 제외한 모든 내부 노드는 적어도 두 개의 자식을 가진다.
3. 각 엣지는 ${\displaystyle S}$의 비어 있지 않은 부분 문자열로 레이블이 지정된다.
4. 노드에서 시작하는 두 엣지가 같은 문자로 시작하는 문자열 레이블을 가질 수 없다.
5. 루트에서 리프 ${\displaystyle i}$까지의 경로에서 발견되는 모든 문자열 레이블을 연결하여 얻은 문자열은 ${\displaystyle i}$가 ${\displaystyle 1}$부터 ${\displaystyle n}$까지의 접미사 ${\displaystyle S[i..n]}$을 나타낸다.

${\displaystyle S}$의 한 접미사가 다른 접미사의 접두사이기도 한 경우, 해당 문자열에 대한 이러한 트리는 존재하지 않는다. 예를 들어, 문자열 abcbc에서 접미사 bc는 접미사 bcbc의 접두사이기도 하다. 이러한 경우, bc를 나타내는 경로는 리프에서 끝나지 않아 다섯 번째 규칙을 위반한다. 이 문제를 해결하기 위해 ${\displaystyle S}$는 문자열에 나타나지 않는 터미널 기호(일반적으로 $로 표시됨)로 채워진다. 이렇게 하면 어떤 접미사도 다른 접미사의 접두사가 되지 않으며, ${\displaystyle S}$의 ${\displaystyle n}$개 접미사 각각에 대해 ${\displaystyle n}$개의 리프 노드가 존재한다.^[8] 모든 내부 비루트 노드는 분기하므로, 이러한 노드는 최대 ${\displaystyle n-1}$개가 있을 수 있으며, 총 ${\displaystyle n+(n-1)+1=2n}$개의 노드(${\displaystyle n}$개의 리프, ${\displaystyle n-1}$개의 내부 비루트 노드, 1개의 루트)가 있다.

접미사 링크는 이전의 선형 시간 구성 알고리즘의 핵심 기능이지만, Farach's algorithm을 기반으로 하는 대부분의 새로운 알고리즘은 접미사 링크를 사용하지 않는다. 완전한 접미사 트리에서 모든 내부 비루트 노드는 다른 내부 노드로의 접미사 링크를 가진다. 루트에서 노드까지의 경로가 문자열 ${\displaystyle \chi \alpha }$를 나타내고, 여기서 ${\displaystyle \chi }$는 단일 문자이고 ${\displaystyle \alpha }$는 문자열(비어 있을 수 있음)인 경우, 해당 노드는 ${\displaystyle \alpha }$를 나타내는 내부 노드로의 접미사 링크를 가진다. 예를 들어, 위 그림에서 ANA 노드에서 NA 노드로의 접미사 링크를 참조하라. 접미사 링크는 트리에서 실행되는 일부 알고리즘에서도 사용된다.

일반화된 접미사 트리는 단일 문자열 대신 문자열 집합을 위해 만들어진 접미사 트리이다. 이는 이 문자열 집합의 모든 접미사를 나타낸다. 각 문자열은 다른 종료 기호로 끝나야 한다.

기능

길이 ${\displaystyle n}$인 문자열 ${\displaystyle S}$에 대한 접미사 트리는 문자가 다항 범위의 정수 알파벳에서 오는 경우 ${\displaystyle \Theta (n)}$ 시간에 구축할 수 있다(특히 상수 크기 알파벳의 경우).^[9] 더 큰 알파벳의 경우, 실행 시간은 문자를 ${\displaystyle O(n)}$ 크기 범위로 가져오기 위해 먼저 정렬하는 데 지배된다. 일반적으로 이는 ${\displaystyle O(n\log n)}$ 시간이 걸린다. 아래 비용은 알파벳이 상수라는 가정하에 주어진다.

길이 ${\displaystyle n}$인 문자열 ${\displaystyle S}$에 대한 접미사 트리가 구축되었거나, 총 길이 ${\displaystyle n=n_{1}+n_{2}+\cdots +n_{K}}$인 문자열 집합 ${\displaystyle D=\{S_{1},S_{2},\dots ,S_{K}\}}$에 대한 일반화된 접미사 트리가 구축되었다고 가정하자. 다음 작업을 수행할 수 있다:

• 문자열 검색:
  • 길이 ${\displaystyle m}$인 문자열 ${\displaystyle P}$가 ${\displaystyle O(m)}$ 시간 내에 부분 문자열인지 확인한다.^[10]
  • 총 길이 ${\displaystyle m}$인 패턴 ${\displaystyle P_{1},\dots ,P_{q}}$의 첫 번째 발생을 ${\displaystyle O(m)}$ 시간 내에 부분 문자열로 찾는다.
  • 총 길이 ${\displaystyle m}$인 패턴 ${\displaystyle P_{1},\dots ,P_{q}}$의 모든 ${\displaystyle z}$개 발생을 ${\displaystyle O(m+z)}$ 시간 내에 부분 문자열로 찾는다.^[11]
  • 정규 표현식 P를 ${\displaystyle n}$에 대해 하위 선형으로 예상되는 시간 내에 검색한다.^[12]
  • 패턴 ${\displaystyle P}$의 각 접미사에 대해 ${\displaystyle P[i\dots m]}$의 접두사와 ${\displaystyle D}$의 부분 문자열 간의 가장 긴 일치 길이를 ${\displaystyle \Theta (m)}$ 시간 내에 찾는다.^[13] 이를 ${\displaystyle P}$에 대한 매칭 통계라고 한다.
• 문자열의 속성 찾기:
  • 문자열 ${\displaystyle S_{i}}$와 ${\displaystyle S_{j}}$의 최장 공통 부분 문자열을 ${\displaystyle \Theta (n_{i}+n_{j})}$ 시간 내에 찾는다.^[14]
  • 모든 maximal pairs, 최대 반복 또는 슈퍼최대 반복을 ${\displaystyle \Theta (n+z)}$ 시간 내에 찾는다.^[15]
  • 렘펠-지프 분해를 ${\displaystyle \Theta (n)}$ 시간 내에 찾는다.^[16]
  • 최장 반복 부분 문자열을 ${\displaystyle \Theta (n)}$ 시간 내에 찾는다.
  • 최소 길이의 가장 자주 나타나는 부분 문자열을 ${\displaystyle \Theta (n)}$ 시간 내에 찾는다.
  • ${\displaystyle \Sigma }$에서 ${\displaystyle D}$에 나타나지 않는 가장 짧은 문자열을 ${\displaystyle z}$개의 문자열이 있는 경우 ${\displaystyle O(n+z)}$ 시간 내에 찾는다.
  • 한 번만 나타나는 가장 짧은 부분 문자열을 ${\displaystyle \Theta (n)}$ 시간 내에 찾는다.
  • 각 ${\displaystyle i}$에 대해 ${\displaystyle S_{i}}$의 다른 ${\displaystyle D}$에 나타나지 않는 가장 짧은 부분 문자열을 ${\displaystyle \Theta (n)}$ 시간 내에 찾는다.

접미사 트리는 노드 간의 상수 시간 최소 공통 조상 검색을 위해 ${\displaystyle \Theta (n)}$ 시간 내에 준비될 수 있다.^[17] 그러면 다음 작업도 수행할 수 있다.

• 접미사 ${\displaystyle S_{i}[p..n_{i}]}$와 ${\displaystyle S_{j}[q..n_{j}]}$ 간의 최장 공통 접두사를 ${\displaystyle \Theta (1)}$ 시간 내에 찾는다.^[18]
• 길이 ${\displaystyle m}$인 패턴 P를 최대 ${\displaystyle k}$개의 불일치를 허용하며 ${\displaystyle O(kn+z)}$ 시간 내에 검색한다. 여기서 z는 일치하는 횟수이다.^[19]
• 모든 ${\displaystyle z}$개의 최대 회문을 ${\displaystyle \Theta (n)}$ 시간 내에 찾거나,^[20] ${\displaystyle g}$ 길이의 간격이 허용되는 경우 ${\displaystyle \Theta (gn)}$ 시간 내에, 또는 ${\displaystyle k}$개의 불일치가 허용되는 경우 ${\displaystyle \Theta (kn)}$ 시간 내에 찾는다.^[21]
• 모든 ${\displaystyle z}$개의 tandem repeat를 ${\displaystyle O(n\log n+z)}$ 시간 내에 찾고, k-불일치 tandem repeat를 ${\displaystyle O(kn\log(n/k)+z)}$ 시간 내에 찾는다.^[22]
• ${\displaystyle k=2,\dots ,K}$에 대해 ${\displaystyle D}$의 최소 ${\displaystyle k}$개 문자열에 대한 최장 공통 부분 문자열을 ${\displaystyle \Theta (n)}$ 시간 내에 찾는다.^[23]
• 주어진 문자열의 최장 회문 부분 문자열을 (문자열과 그 역순의 일반화된 접미사 트리를 사용하여) 선형 시간 내에 찾는다.^[24]

응용 분야

접미사 트리는 텍스트 편집, 자유 텍스트 검색, 계산생물학 및 기타 응용 분야에서 발생하는 많은 문자열 문제를 해결하는 데 사용될 수 있다.^[25] 주요 응용 분야는 다음과 같다.^[25]

• 문자열 검색, O(m) 복잡도로, 여기서 m은 부분 문자열의 길이 (그러나 문자열에 대한 접미사 트리를 구축하는 데 초기 O(n) 시간이 필요함)
• 최장 반복 부분 문자열 찾기
• 최장 공통 부분 문자열 찾기
• 문자열에서 가장 긴 회문 찾기

접미사 트리는 생물정보학 응용 분야에서 DNA 또는 단백질 서열(긴 문자열로 간주될 수 있음)에서 패턴을 검색하는 데 자주 사용된다. 불일치를 효율적으로 검색하는 능력은 가장 큰 강점으로 간주될 수 있다. 접미사 트리는 데이터 압축에도 사용된다. 반복되는 데이터를 찾는 데 사용될 수 있으며, 버로우즈-휠러 변환의 정렬 단계에 사용될 수 있다. LZW 압축 방식의 변형은 접미사 트리를 사용한다(LZSS). 접미사 트리는 또한 일부 검색 엔진에서 사용되는 데이터 클러스터링 알고리즘인 접미사 트리 클러스터링에도 사용된다.^[26]

구현

각 노드와 엣지를 ${\displaystyle \Theta (1)}$ 공간으로 표현할 수 있다면, 전체 트리는 ${\displaystyle \Theta (n)}$ 공간으로 표현될 수 있다. 트리 내 모든 엣지의 모든 문자열 길이의 총합은 ${\displaystyle O(n^{2})}$이지만, 각 엣지는 S의 부분 문자열의 위치와 길이로 저장될 수 있어 총 공간 사용량은 ${\displaystyle \Theta (n)}$ 컴퓨터 워드가 된다. 접미사 트리의 최악의 공간 사용량은 피보나치 워드에서 볼 수 있으며, 전체 ${\displaystyle 2n}$ 노드를 제공한다.

접미사 트리를 구현할 때 중요한 선택은 노드 간의 부모-자식 관계이다. 가장 일반적인 방법은 형제 리스트라고 불리는 연결 리스트를 사용하는 것이다. 각 노드는 첫 번째 자식에 대한 포인터와 자신이 속한 자식 리스트의 다음 노드에 대한 포인터를 가진다. 효율적인 실행 시간 속성을 가진 다른 구현은 해시 맵, 정렬되거나 정렬되지 않은 배열 (배열 두 배 확장과 함께), 또는 균형 탐색 트리를 사용한다. 우리는 다음에 관심이 있다.

• 주어진 문자에서 자식을 찾는 비용.
• 자식을 삽입하는 비용.
• 노드의 모든 자식을 나열하는 비용 (아래 표에서 자식 수로 나눔).

σ를 알파벳의 크기라고 하자. 그러면 다음과 같은 비용이 발생한다.

	찾기	삽입	순회
형제 리스트 / 정렬되지 않은 배열	O(σ)	Θ(1)	Θ(1)
비트 단위 형제 트리	O(log σ)	Θ(1)	Θ(1)
해시 맵	Θ(1)	Θ(1)	O(σ)
균형 탐색 트리	O(log σ)	O(log σ)	O(1)
정렬된 배열	O(log σ)	O(σ)	O(1)
해시 맵 + 형제 리스트	O(1)	O(1)	O(1)

삽입 비용은 상각되며, 해싱 비용은 완전 해싱에 대해 주어진다.

각 엣지와 노드의 방대한 정보로 인해 접미사 트리는 매우 비싸며, 좋은 구현에서는 원본 텍스트 메모리 크기의 약 10~20배를 소비한다. 접미사 배열은 이 요구 사항을 8배로 줄인다(32비트 주소 공간과 8비트 문자로 구축된 LCP 값을 포함하는 배열의 경우). 이 인자는 속성에 따라 다르며 32비트 시스템에서 4바이트 너비의 문자(일부 유닉스 계열 시스템에서 모든 기호를 포함하는 데 필요하며, wchar_t 참조)를 사용할 경우 2에 도달할 수 있다. 연구자들은 더 작은 인덱싱 구조를 계속 찾아왔다.

병렬 구성

접미사 트리 구성 속도를 높이기 위한 다양한 병렬 알고리즘이 제안되었다.^{[27][28][29][30][31]} 최근에는 ${\displaystyle O(n)}$ 작업 (순차 시간)과 ${\displaystyle O(\log ^{2}n)}$ 스팬을 가진 접미사 트리 구성을 위한 실용적인 병렬 알고리즘이 개발되었다. 이 알고리즘은 공유 메모리 멀티코어 머신에서 좋은 병렬 확장성을 달성하며, 40코어 머신을 사용하여 인간 유전체 – 약 3GB –를 3분 이내에 인덱싱할 수 있다.^[32]

외부 구성

접미사 트리의 메모리 사용량은 선형적이지만 실제 시퀀스 컬렉션의 크기보다 상당히 크다. 큰 텍스트의 경우 구성에 외부 메모리 접근 방식이 필요할 수 있다.

외부 메모리에서 접미사 트리를 구성하는 이론적 결과가 있다. Farach-Colton, Ferragina & Muthukrishnan (2000)의 알고리즘은 정렬과 동일한 I/O 복잡도를 가지므로 이론적으로 최적이다. 그러나 이 알고리즘의 전체적인 복잡성으로 인해 지금까지 실용적인 구현이 이루어지지 못했다.^[33]

반면에, (몇) GB/시간으로 확장 가능한 디스크 기반 접미사 트리를 구성하기 위한 실제 작업이 있었다. 최신 방법은 TDD,^[34] TRELLIS,^[35] DiGeST,^[36] 및 B²ST이다.^[37]

TDD와 TRELLIS는 전체 인간 유전체까지 확장되어 수십 기가바이트 크기의 디스크 기반 접미사 트리를 생성한다.^[34][35] 그러나 이러한 방법은 3GB를 초과하는 시퀀스 컬렉션을 효율적으로 처리할 수 없다.^[36] DiGeST는 훨씬 더 나은 성능을 보이며 약 6시간 내에 약 6GB 크기의 시퀀스 컬렉션을 처리할 수 있다.^[36]

이러한 모든 방법은 트리가 주 메모리에 맞지 않지만 입력은 맞는 경우에 접미사 트리를 효율적으로 구축할 수 있다. 가장 최근의 방법인 B²ST^[37]는 주 메모리에 맞지 않는 입력을 처리할 수 있도록 확장된다. ERA는 훨씬 빠른 최근 병렬 접미사 트리 구성 방법이다. ERA는 16GB RAM이 장착된 8코어 데스크톱 컴퓨터에서 19분 만에 전체 인간 유전체를 인덱싱할 수 있다. 16개 노드(노드당 4GB RAM)가 있는 단순한 Linux 클러스터에서 ERA는 9분 이내에 전체 인간 유전체를 인덱싱할 수 있다.^[38]

같이 보기

• 접미사 오토마톤