접미사 트리

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

$문자열 S$에 대한 이러한 트리 구축에는 시간과 공간이 $S의$길이에 선형으로 소요됩니다$.$ 구축이 완료되면$S$의 서브스트링을 찾는 등 여러 작업을 신속하게 수행할 수 있습니다$.$ 예를 들어, 일정 수의 오류가 허용되면 하위스트링을 찾는 등$,$ locati.ng 정규 표현 패턴 등과 일치합니다.또한 접미사 트리는 가장 일반적인 서브스트링 문제에 대한 최초의 선형 시간 해결 방법 중 하나를 제공합니다.이러한 속도 향상에는 비용이 듭니다. 일반적으로 문자열의 접미사 트리를 저장하는 데는 문자열 자체를 저장하는 것보다 훨씬 더 많은 공간이 필요합니다.

역사

이 개념은 와이너(1973년)에 의해 처음 도입되었다.$접미사{\displaystyle S}$ [${\displaystyle }$.$]$ \ $displaystyle$S [$i$ . $n$가 아닌 Weiner는 각^[1] 위치의 프리픽스 식별자, 즉$$i { $displaystyle$ i$$}로$$ $시작$하여$$S { $displaystyle$ S$$}에서 단 한 번만 발생합니다.알고리즘 D는${\displaystyle }$S [ k${\displaystyle }$+ ${\displaystyle \mathrm{1]}}$에 $대해{\displaystyle }$ 압축되지^[2] 않은 트라이를 사용합니다.${\displaystyle n}$[ $display$ $style$S [$$${\displaystyle k}$+ 1 . ${\displaystyle n}$]$$extends$$ extends extends extends extends${\displaystyle }$S [ $k$.$n$ $]$의 trie로 확장합니다.이렇게 하면${\displaystyle }$S [${\displaystyle n}$. $n$의 trie에서 시작하여 S${\displaystyle }$[ ${\displaystyle 1}$. n$]$의 trie로 확장됩니다.${\displaystyle }$n${\displaystyle ]}${$displaystyle$ S$[1..n]}$는 알고리즘 D에 대한${\displaystyle }$n -$$({$displaystyle n-1$$\})$의 연속 호출에 $의해{\displaystyle }$ 구축될 수 있습니다.단, 전체 실행 $시간$은${\displaystyle }$O (${\displaystyle {n\mathrm{}}^{}}$2) {$displaystyle$ O$(n^{$2})입니다.Weiner's Algorithmithm B는 구성된 크기에서 몇 가지 보조 데이터 구조를 유지하기 위해 전체 실행 시간을 선형으로 합니다.후자는 여전히 O${\displaystyle }$($n$2)$${$displaystyle$ O$(n^{2})}$ ${\displaystyle {노드}^{}}$일 수 있다. 예를 들어, $S{\displaystyle }$ ${\displaystyle =}$ ${\displaystyle {}^{}{}^{}}$ ${\displaystyle b^{}}$ n $n$ n ${\displaystyle {}^{}{}^{}}$ n${\displaystyle }$$ .$${ $displaystyle$ S =$a$^ { $n } a$^ {$n$ } $b$^ { $n$} \ $ } Weiner$$'s Algorithmary C는 최종적으로 압축된 시간 ^[3]및 전체 크기를 달성하기 위해 사용된다.도날드 크누스는 후에 후자를 "올해의 알고리즘"^{[citation needed]}으로 규정했다.교과서 Aho, Hopcroft & Ullman(1974년, 제9.5장)은 Weiner의 결과를 단순하고 우아한 형태로 재현하여 포지션 트리를 소개했다.

McCreight(1976)는$S$의 $모든{\displaystyle }$ 접미사의 (압축된$)$ trie를 최초로 구축했다.i$\displaystyle$i로 $시작$하는 접미사는 보통 접두사 식별자보다 길지만 압축된 trie의 경로 표현은 크기가 다르지 않다.반면 McCreight는 Weiner의 보조 데이터 구조의 대부분을 제거할 수 있었고, 접미사 링크만 남아 있었다.

우코넨(1995년)은 건축을 ^[4]더욱 단순화했다.그는 현재 Ukkonen의 알고리즘으로 알려진 서픽스 트리를 당시 가장 빠른 알고리즘과 일치하는 실행 시간을 최초로 온라인으로 구축했다.이러한 알고리즘은 모두 일정한 크기의 알파벳에 대한 선형 시간으로${\displaystyle ,}$ 일반적으로 $최악$의 ${\displaystyle \mathrm{실행}}$ ${\displaystyle \mathrm{시간}}$은 O(${\displaystyle n}$ log${\displaystyle }$n${\displaystyle }$n $)(\displaystyle$ O$(n\log$ n$)$입니다.

Farach(1997)는 모든 알파벳에 최적인 첫 번째 접미사 트리 구성 알고리즘을 제공했다.특히, 이것은 다항식 범위의 정수 알파벳에서 추출된 문자열에 대한 첫 번째 선형 시간 알고리즘입니다.Farach의 알고리즘은 예를 들어 외부 메모리, 압축, 간결 등의 접미사 트리와 접미사 배열을 모두 구성하는 새로운 알고리즘의 기초가 되었습니다.

정의.

$문자열{\displaystyle }$$$S$${\$displaystyle$S$}$의 접미사 트리는 다음과 같이 ^[5]트리로 정의됩니다.

• 트리에는 1$(디스플레이 스타일$1)에서$$ n$(디스플레이 스타일$n$)$까지의 $번호$가 정확히 n개 붙어 있습니다.
• 루트를 제외한 모든 내부 노드에는 최소 2개의 하위 노드가 있습니다.
• 각 가장자리에는 S$(\displaystyle$ S$)$의 빈 $서브스트링$이 붙어 있습니다.
• 노드에서 시작하는 두 개의 에지는 동일한 문자로 시작하는 문자열 레이블을 가질 수 없습니다.
• 경로에서 발견된 모든 문자열 라벨을 루트에서 $리프{\displaystyle }$ i$(\displaystyle$ i$)$로 연결한 문자열은$$i$(\displaystyle$ i$)$에 $대해{\displaystyle }$ 1${\displaystyle (\backslash }$$displaystyle$1)에서$$n(\$displaystyle$ n$)$로 $서픽스{\displaystyle }$ S [${\displaystyle }$. $](i$ .${\displaystyle }$. $displaystyle S [ i$ . n$])$를 나타냅니다.

이러한 트리가 모든 문자열에 대해 존재하는 것은 아니기 때문에 $(\displaystyle$ S$)$에는 문자열에 표시되지 않는 단자 기호(일반적으로 표시됨)가 패딩되어 있습니다.$이렇게 하면 접미사가 다른 접미사가 되지 않고$$S의 n개(\$displaystyle$ S$)$의 $각{\displaystyle }$$n개$(\$displaystyle$ n$)$ 접미사에$$ 대해$$1개씩 $n개$(\$displaystyle$ n$)$ 리프$$ 노드가 $있습니다{\displaystyle }$. 내부 비루트 노드가 분기하므로 이러한 노드가 최대 n개(n - 1) + 1개(n개) 남아 있습니다.내부 비루트 노드 1개, 루트 1개).

접미사 링크는 오래된 선형 시간 구성 알고리즘의 핵심 기능이지만, Farach의 알고리즘을 기반으로 하는 대부분의 새로운 알고리즘에는 접미사 링크가 없습니다.완전한 서픽스 트리에서 루트 이외의 모든 내부 노드에는 다른 내부 노드에 대한 서픽스 링크가 있습니다.루트에서 노드까지의 경로에 문자열$$(\$displaystyle$$\chi$$\alpha$$)$가 입력되어 있는 경우, 여기서 $"\displaystyle$$\chi"$는 단일 문자,$$α$(아마$ 빈)는 내부 노드에 $대한{\displaystyle }$ 서픽스 링크가 있습니다.서픽스 링크 from을 참조하십시오.노드ANA을 위해 노드까지NA를 참조해 주세요.접미사 링크는 트리에서 실행되는 일부 알고리즘에서도 사용됩니다.

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

기능

$길이$가$n$인 $문자열{\displaystyle }$ S$(\$$displaystyle$$$n$)$의 서픽스 트리는 문자가 다항식 범위의 정수 알파벳에서 온 경우(특히 일정한 크기의 ^[6]알파벳에 해당) $n) 시간$ 내에 작성할 수 있습니다.알파벳이 클 경우 실행 시간은 알파벳을 먼저 정렬하여 O$)\displaystyle$ O$(n$displaystyle O($n)$의 범위로 만듭니다.일반적으로 이${\displaystyle \mathrm{작업}}$에는 O(${\displaystyle n}$ log$display$ n)\$displaystyle$O$(n\$log n$)}$ 시간이 걸립니다.아래 비용은 알파벳이 일정하다는 가정 하에 제시됩니다.

길이$n$의 $문자열{\displaystyle }$S(\$displaystyle$$$n$)$에 대해 서픽스 트리가 작성되었거나 $문자열{\displaystyle }$ D${\displaystyle =}$ { ${\displaystyle {}_{}{}_{}}$1 ,${\displaystyle {}_{}{S\mathrm{}}_{}}$ 2 , ${\displaystyle ...}$ , ${\displaystyle S_{}}$ K$$ { \ $displaystyle$ D = \ { $S$_ { 1$$} , S$_${ $2$} , \$dots$ \ $K$ } { \ \ displaystyle D } 、 { \ }$$} $assume$ assume assume assume assume assume of has of of of has has has has of of of has has has has has has has has has has has has has has has has has of has has has has has has has has has has has has has has has$displaystyle$ n$=n_{1}+n_{2}+\cdots +n_{K$ 다음 작업을 수행할 수 있습니다.

• 문자열 검색:
  • 길이 ${displaystyle$ m$}$의 $문자열$P${$$displaystyle$ P}가$$$$ O$($^[7]m)시간으로 서브스트링인지 확인합니다.
  • ${\displaystyle {O\mathrm{}}_{}}$${\displaystyle }$(${\displaystyle m}$) \ $display style$O ($m$ ) $time$ ${\displaystyle {}_{}}$ $substr{\displaystyle }$、${\displaystyle }$P$$ \ $display style$ P $_${1} \$dots$ , $P$_ {$q$ } $패턴$의 첫 번째 출현을 찾습니다.
  • $O{\displaystyle }$${\displaystyle }$(${\displaystyle m}$ +${\displaystyle z}$) ^[8]\ $display style$O ($m$ + z )$시간$으로 패턴$$$$${\displaystyle {P\mathrm{}}_{}}$1,${\displaystyle }$… , ${\displaystyle P_{}}$q \ $displaystyle P_{1},$ \ $dots$,$P_{q}$ 의$$ 모든 $(display style$ z$)$ 패턴을$$ 찾습니다.
  • n$\displaystyle$ n$\}$^[9]에서 예상되는 시간 내 정규식 P를 검색합니다.
  • $패턴{\displaystyle }$P의 각 서픽스({$displaystyle$$P$$\})$에 대해 $프리픽스{\displaystyle }$P${\displaystyle [i}$…m$]({displaystyle$ P$[i\dots$m])와$$ D$({displaystyle$ $D$$})$의 서브스트링 사이의 최장 일치 길이를$m)$ 단위로$$ ^[10]구합니다.이를 P$(\displaystyle$ P$)$의 일치 통계라고 합니다.
• 문자열 속성 찾기:
  • $문자열{\displaystyle \mathrm{}}$ ${\displaystyle S_{}}$i ( $n$${\displaystyle {}_{}{i}_{}}$ + ${\displaystyle n_{}}$j$$) \ $displaystyle$\ $Theta$( n$_$ { $i$} + n$_$$${ $j$ )^[11]의 가장 긴 공통 서브스트링을 찾습니다.
  • $\delta {\displaystyle \mathrm{}}$( n + z$$) {$displaystyle \Theta ( n$+$z$ ) ^[12]} 시간$$ 내에 모든 최대 쌍, 최대 반복 또는 초최대 반복을 찾습니다.
  • ${\displaystyle \delta }$ ( n ) \ displaystyle \ $Theta ( n$ ^[13]내에 Lempel-Ziv 분해를 구합니다.
  • $\delta {\displaystyle \mathrm{}}$(${\displaystyle n}$ )$$\ $displaystyle$\ $Theta ( n$ )시간$$ 중 가장 긴 반복 서브스트링을 찾습니다.
  • $최소{\displaystyle \mathrm{}}$ 길이의 서브스트링을${\displaystyle }$δ ($n$) \ displaystyle \$Theta ( n$ )시간$$ 내에 가장 빈번하게 검출합니다.
  • $D{\displaystyle \mathrm{}}$$(\displaystyle$ $D$$)$에서 발생하지 않는 최단 문자열$($${\displaystyle \backslash \mathrm{displaystyle}}$ z$)$이 $있는$ $경우$ $O$$($$n$${\displaystyle }$+${\displaystyle }$z$)$ 시간(\displaystyle O$(n+z)))$에서 찾습니다$.$
  • $\delta {\displaystyle \mathrm{}}$ ${\displaystyle (n}$ )$$\ $displaystyle$\ $Theta ($n )$시간$ 내에 발생하는 최단 서브스트링을 찾습니다.
  • $i$에 대해$$D의$$다른 $부분$에서는 $발생$하지 않는 $Si의$$$최단 서브스트링을 $)$ \$displaystyle \Theta(n)$ 시간$$ 단위로 찾습니다.

접미사 트리는 노드 간의 공통 상위 항목 검색 시간을${\displaystyle \delta }$( n$$) {$displaystyle$ \$Theta$( n$$) ^[14]}시간으로$$ 일정하게 설정할 수 있습니다.그 후, 다음과 같이 할 수 있습니다.

• $접미사{\displaystyle {}_{}}$ ${\displaystyle S_{}}$i [${\displaystyle p}$. ${\displaystyle {}_{}{i}_{}}$ $]\displaystyle S_{i}$ [$p..$$n_{i}}$ $및$ ${\displaystyle S_{}}$j [${\displaystyle {}_{}.}$ n${\displaystyle {}_{}{j}_{}}$]({$displaystyle S_{j}[q..$$n_{j},$${\displaystyle }\theta$ (${\displaystyle 1}$ $), \displaystyle$ \$Theta$ ($1)$^[15]。
• ${\displaystyle O}$(k n + z${\displaystyle )}$ {$displaystyle$ O$(kn+$ $시간{\displaystyle }$ $내$에 m 길이의 $패턴$ P를 검색합니다$$. 여기서 z는 ^[16]히트 수입니다.
• $g$( ${\displaystyle n}$)$$\ $displaystyle$$$$\ Theta ( n$ )$$^[17]$display{\displaystyle \mathrm{}}$${\displaystyle }$${\displaystyle (}$ ${\displaystyle \mathrm{gn}}$ \ $displaystyle$\ $Theta$$$$( gn$)$display$ display $、$ k $style$$$kn$$$$${\displaystyle \mathrm{displaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplay}}$ displaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplay kstyle $displaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplay{\displaystyle }$
• $모든$ \$displaystyle$ z$$탠덤 반복을${\displaystyle }$O ( ${\displaystyle n}$log$n$n +${\displaystyle z}$)$$$repeats$ 、 k - mismatch 탠덤 $반복$을${\displaystyle }$O ( ${\displaystyle \mathrm{kn}}$ log ${\displaystyle (}$ (${\displaystyle n}$ /${\displaystyle k}$) +${\displaystyle z}$ )$$\ $displaystyle$O ( $\ log$ ($n$ /$k$ ) +$z$ )$$^[19]。
• $display$${\displaystyle }$(${\displaystyle n}$) \ $displaystyle$ \$Theta ( n$ )$시간$에서 k ^[20]${\displaystyle =2}$, ${\displaystyle ...}$ , ${\displaystyle K}${ $displaystyle$ k =$$2$,$ \ $displaystyle$ , $K$}에$$ $대해{\displaystyle }$ D ${\$ $displaystyle$$$k$}$ $문자열$에서 가장 긴 공통 서브스트링을 찾습니다.
• 주어진 문자열의 가장 긴 회문 서브스트링(문자열의 일반화된 접미사 트리 및 그 반대)을 선형 ^[21]시간으로 찾습니다.

적용들

접미사 트리는 텍스트 편집, 자유 텍스트 검색, 계산 생물학 및 기타 응용 ^[22]분야에서 발생하는 많은 문자열 문제를 해결하기 위해 사용할 수 있습니다.주요 어플리케이션은 다음과 같습니다.^[22]

• 문자열 검색(O(m) 복잡도). 여기서 m은 하위 문자열의 길이입니다(단, 문자열의 서픽스 트리를 구축하기 위해 초기 O(n) 시간이 필요합니다).
• 가장 오래 반복되는 하위 문자열 찾기
• 가장 긴 공통 부분 문자열 찾기
• 문자열에서 가장 긴 회문 찾기

접미사 트리는 DNA 또는 단백질 배열에서 패턴을 검색하는 생물 정보학 응용 분야에서 종종 사용됩니다(이것은 긴 문자열로 볼 수 있습니다.불일치를 효율적으로 검색할 수 있는 능력은 그들의 가장 큰 강점으로 여겨질 수 있다.접미사 트리는 데이터 압축에도 사용된다. 반복 데이터를 찾는 데 사용할 수 있으며 버로우스의 분류 단계에 사용할 수 있다.휠러 트랜스폼LZW 압축 방식의 바리안트에서는 서픽스 트리(LZSS)를 사용합니다.접미사 트리는 일부 검색 ^[23]엔진에서 사용되는 데이터 클러스터링 알고리즘인 접미사 트리 클러스터링에도 사용됩니다.

실행

각 노드와 엣지를${\displaystyle \mathrm{\theta }}$ (${\displaystyle }$1 )$$\ $displaystyle$ \ Theta (1)$$$공간$에 표시할$$ 수 있는 경우 트리 전체를 $\theta {\displaystyle \mathrm{}}$($$n ) \ $displaystyle$\ $Theta$( n$$$$)공간에 표시할 수 있습니다.트리의 모든 에지에 있는 모든 문자열의 총 길이는 O${\displaystyle ({n\mathrm{}}^{}}$ 2)$${$displaystyle$ O$(n^{2$입니다. 단, 각 에지는 S의 서브스트링의 위치와 길이로 저장할 수 있으며, 총 공간 사용량은${\displaystyle \mathrm{of}}$( n ) \ $displaystyle$\$Theta$ ( n $)$ 。접미사 트리의 최악의 공간 사용은 fibonacci 워드와 함께 표시되며, $전체{\displaystyle \mathrm{}}$ $(\displaystyle 2n)$ 노드를 제공합니다$$.

접미사 트리를 구현할 때 중요한 선택은 노드 간의 부모-자녀 관계입니다.가장 일반적인 방법은 형제 목록이라고 불리는 링크된 목록을 사용하는 것입니다.각 노드에는 첫 번째 아이에 대한 포인터가 있으며 자녀 목록의 다음 노드에 대한 포인터가 포함되어 있습니다.효율적인 실행 시간 속성을 가진 다른 구현에서는 해시 맵, 정렬 또는 정렬되지 않은 배열(배열을 두 배로 함) 또는 균형 잡힌 검색 트리를 사용합니다.델의 관심사는 다음과 같습니다.

• 특정 캐릭터에서 아이를 찾기 위한 비용입니다.
• 아이를 삽입하는 데 드는 비용입니다.
• 노드의 모든 하위 항목을 등록하는 비용(아래 표의 하위 항목 수로 나눗셈).

be는 알파벳 크기로 해 주세요.그러면 다음과 같은 비용이 발생합니다.

${\displaystyle {begin {array} {rll}&{\text {Lookup}}&{\text}삽입}}&{\text{Traversal}}\hline{text{Sibling lists/unsorted arrays}}&O(\sigma)&\\Theta (1)&\Theta (1)\{\text{Bitwise 형제 트리}}&O(\log \sigma)&\Theta (1)&\Theta (1)\{\text{해시맵}}\\Theta (1)&\Theta (1) & O ( \ sigma ) \ { \ text { 균형검색 트리 } \ O ( \ log \ sigma ) & O ( \ log \ sigma ) & O ( \ log \ sigma ) & O ( \ log \ sigma ) } \ \ { \ \ \ \ \ \ \ \ \ \ \ { text mapsigma \ lists lists sibling + + + + + + + + + + sibling sibling sibling + + + sibling sibling sibling sibling sibling sibling sibling sibling sibling sibling sibling sibling sibling sibling sibling sibling sibling sibling + + + sibling sibling sibling sibling sibling sibling sibling$

삽입원가는 상각하고 해싱원가는 완벽한 해싱을 위해 부여한다.

각 엣지와 노드에 대량의 정보가 있기 때문에 서픽스 트리는 매우 비싸고, 적절한 구현에서는 소스 텍스트의 약 10~20배의 메모리 크기를 소비합니다.서픽스 배열은 이 요건을 8의 배수로 줄입니다(32비트 주소 공간 및8비트 문자 내에 구축된 LCP 값을 포함한 배열).이 계수는 속성에 따라 다르며 32비트 시스템에서 4바이트 와이드 문자(일부 UNIX 유사 시스템에서는 기호 포함 필요, wchar_t 참조)를 사용하면 2에 이를 수 있습니다.연구자들은 더 작은 색인 구조를 계속해서 찾아냈다.

병렬 구조

접미사 트리 구축 속도를 높이기 위한 다양한 병렬 알고리즘이 ^{[24][25][26][27][28]}제안되었습니다.최근에는 O${\displaystyle }$(${\displaystyle n}$ )$$\ $displaystyle$O ($n$ ) work ( sequential time )$및$ O ( ${\displaystyle {log\mathrm{}}^{}}$ 2${\displaystyle {}^{}n}$n$$) \ $displaystyle$ O ( \ $log$^ {$2 n$)스팬을 사용한 접미사트리 구축의 실용적인 병렬 알고리즘이 개발되었습니다.이 알고리즘은 공유 메모리 멀티 코어 머신에서 뛰어난 병렬 확장성을 실현하고 40 코어 ^[29]머신을 사용하여 3분 이내에 인간 게놈(약 3GB)을 인덱싱할 수 있습니다.

외부 시공

선형이지만 접미사 트리의 메모리 사용량이 시퀀스 컬렉션의 실제 크기보다 훨씬 높습니다.큰 텍스트의 경우 구축 시 외부 메모리 접근법이 필요할 수 있습니다.

외부 메모리에 서픽스 트리를 구성하기 위한 이론적 결과가 있습니다.Farach-Colton, Ferragina 및 Muthukrishnan(2000)의 알고리즘은 이론적으로 최적이며 I/O 복잡도는 정렬과 동일합니다.그러나 이 알고리즘의 전반적인 복잡성으로 인해 지금까지 실제 ^[30]구현이 방해되어 왔습니다.

한편, (시간당) GB까지 확장 가능한 디스크 기반 서픽스 트리를 구축하기 위한 실용적인 작업이 있었습니다.최신 방식은 TDD,^[31] TRELLIS,^[32] DiGeST ^[33]및 ^[34]BST입니다².

TDD와 TRELLIS는 인간 게놈 전체를 확장하여 수십 ^[31][32]기가바이트 크기의 디스크 기반 접미사 트리를 생성합니다.그러나 이 방법으로는 ^[33]3GB를 초과하는 시퀀스의 수집을 효율적으로 처리할 수 없습니다.DiGeST는 성능이 크게 향상되어 약 6시간 ^[33]만에 6GB의 시퀀스를 처리할 수 있습니다.이러한 모든 방법을 통해 트리가 메인 메모리에 맞지 않지만 입력이 필요한 경우 서픽스 트리를 효율적으로 구축할 수 있습니다.최신 방법인 BST는^{2 [34]}메인 메모리에 맞지 않는 입력을 처리하도록 확장됩니다.ERA는 상당히 빠른 최신 병렬 접미사 트리 구축 방법입니다.ERA는 16GB RAM을 탑재한 8코어 데스크톱 컴퓨터에서 19분 만에 전체 인간 게놈을 인덱싱할 수 있습니다.16개의 노드(노드당 4GB RAM)를 갖춘 단순한 Linux 클러스터에서는 ERA는 전체 인간 게놈을 9분 이내에 ^[35]인덱싱할 수 있습니다.

「 」를 참조해 주세요.

• 서픽스 오토마톤

메모들

레퍼런스

• 를 클릭합니다Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974), The Design and Analysis of Computer Algorithms, Reading/MA: Addison-Wesley, ISBN 0-201-00029-6.
• 를 클릭합니다Apostolico, A.; Iliopoulos, C.; Landau, G. M.; Schieber, B.; Vishkin, U. (1988), "Parallel construction of a suffix tree with applications", Algorithmica, 3 (1–4): 347–365, doi:10.1007/bf01762122, S2CID 5024136.
• 를 클릭합니다Baeza-Yates, Ricardo A.; Gonnet, Gaston H. (1996), "Fast text searching for regular expressions or automaton searching on tries", Journal of the ACM, 43 (6): 915–936, doi:10.1145/235809.235810, S2CID 1420298.
• 를 클릭합니다Barsky, Marina; Stege, Ulrike; Thomo, Alex; Upton, Chris (2008), "A new method for indexing genomes using on-disk suffix trees", CIKM '08: Proceedings of the 17th ACM Conference on Information and Knowledge Management (PDF), New York, NY, USA: ACM, pp. 649–658.
• 를 클릭합니다Barsky, Marina; Stege, Ulrike; Thomo, Alex; Upton, Chris (2009), "Suffix trees for very large genomic sequences", CIKM '09: Proceedings of the 18th ACM Conference on Information and Knowledge Management (PDF), New York, NY, USA: ACM.
• 를 클릭합니다Farach, Martin (1997), "Optimal Suffix Tree Construction with Large Alphabets" (PDF), 38th IEEE Symposium on Foundations of Computer Science (FOCS '97), pp. 137–143.
• 를 클릭합니다Farach, Martin; Muthukrishnan, S. (1996), "Optimal Logarithmic Time Randomized Suffix Tree Construction", International Colloquium on Automata Languages and Programming (PDF).
• 를 클릭합니다Farach-Colton, Martin; Ferragina, Paolo; Muthukrishnan, S. (2000), "On the sorting-complexity of suffix tree construction.", Journal of the ACM, 47 (6): 987–1011, doi:10.1145/355541.355547, S2CID 8164822.
• 를 클릭합니다Giegerich, R.; Kurtz, S. (1997), "From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction" (PDF), Algorithmica, 19 (3): 331–353, doi:10.1007/PL00009177, S2CID 18039097, archived from the original (PDF) on 2016-03-03, retrieved 2012-07-13.
• 를 클릭합니다Gusfield, Dan (1997), Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Cambridge University Press, ISBN 0-521-58519-8.
• 를 클릭합니다Hariharan, Ramesh (1994), "Optimal Parallel Suffix Tree Construction", ACM Symposium on Theory of Computing (PDF).
• 를 클릭합니다Iliopoulos, Costas; Rytter, Wojciech (2004), "On Parallel Transformations of Suffix Arrays into Suffix Trees", 15th Australasian Workshop on Combinatorial Algorithms, CiteSeerX 10.1.1.62.6715.
• 를 클릭합니다Mansour, Essam; Allam, Amin; Skiadopoulos, Spiros; Kalnis, Panos (2011), "ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings" (PDF), Proceedings of the VLDB Endowment, 5 (1): 49–60, arXiv:1109.6884, Bibcode:2011arXiv1109.6884M, doi:10.14778/2047485.2047490, S2CID 7582116.
• 를 클릭합니다McCreight, Edward M. (1976), "A Space-Economical Suffix Tree Construction Algorithm", Journal of the ACM, 23 (2): 262–272, CiteSeerX 10.1.1.130.8022, doi:10.1145/321941.321946, S2CID 9250303.
• 를 클릭합니다Phoophakdee, Benjarath; Zaki, Mohammed J. (2007), "Genome-scale disk-based suffix tree indexing", SIGMOD '07: Proceedings of the ACM SIGMOD International Conference on Management of Data, New York, NY, USA: ACM, pp. 833–844, CiteSeerX 10.1.1.81.6031.
• Sahinalp, Cenk; Vishkin, Uzi (1994), "Symmetry breaking for suffix tree construction", ACM Symposium on Theory of Computing, doi:10.1145/195058.195164, S2CID 5985171
• 를 클릭합니다Smyth, William (2003), Computing Patterns in Strings, Addison-Wesley.
• 를 클릭합니다Shun, Julian; Blelloch, Guy E. (2014), "A Simple Parallel Cartesian Tree Algorithm and its Application to Parallel Suffix Tree Construction", ACM Transactions on Parallel Computing, 1: 1–20, doi:10.1145/2661653, S2CID 1912378.
• 를 클릭합니다Tata, Sandeep; Hankins, Richard A.; Patel, Jignesh M. (2003), "Practical Suffix Tree Construction", VLDB '03: Proceedings of the 30th International Conference on Very Large Data Bases (PDF), Morgan Kaufmann, pp. 36–47.
• 를 클릭합니다Ukkonen, E. (1995), "On-line construction of suffix trees" (PDF), Algorithmica, 14 (3): 249–260, doi:10.1007/BF01206331, S2CID 6027556.
• 를 클릭합니다Weiner, P. (1973), "Linear pattern matching algorithms" (PDF), 14th Annual IEEE Symposium on Switching and Automata Theory, pp. 1–11, doi:10.1109/SWAT.1973.13.
• 를 클릭합니다Zamir, Oren; Etzioni, Oren (1998), "Web document clustering: a feasibility demonstration", SIGIR '98: Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, New York, NY, USA: ACM, pp. 46–54, CiteSeerX 10.1.1.36.4719.

외부 링크

• Sartaj Sahni의 서픽스 트리
• NIST의 사전 알고리즘 및 데이터 구조물의:.접미사 트리
• Burrows-Wheeler 변환에 기반한 범용 데이터 압축: 이론과 실천, BWT에서의 서픽스 트리 적용
• 간결한 데이터 구조의 이론과 실천, 압축 접미사 트리의 C++ 구현
• Ukonen의 서픽스 트리의 구현(C Part 1 Part 2 Part 3 Part 4 Part 5 Part 6)
• 온라인 데모:우코넨의 서픽스 트리 시각화