접미사 배열

접미사 배열
유형	배열
발명된 사람	맨버앤마이어스(1990년)
시간 복잡성 큰 O자로 표기하여
평균 최악의 경우 공간 ${\displaystyle {\mathcal {O}(n)}$ ${\displaystyle {\mathcal {O}(n)}$ 건설 ${\displaystyle {\mathcal {O}(n)}$ ${\displaystyle {\mathcal {O}(n)}$

컴퓨터 과학에서 접미사 배열은 문자열의 모든 접미사의 정렬된 배열이다.그것은 무엇보다도 전체 텍스트 색인, 데이터 압축 알고리즘, 서지학 분야에서 사용되는 데이터 구조다.

접미사 배열은 접미사 나무의 단순하고 공간 효율적인 대안으로 Manber & Myers(1990)에 의해 도입되었다.이들은 1987년 개스톤 곤넷에 의해 PAT 어레이(Gonnet, Baeza-Yates & Snider 1992)라는 이름으로 독자적으로 발견되었다.

어디 저장은 알고리즘만 O(1){\displaystyle{{O\mathcal}}(1)입력 문자열과 출력 접미사를 넘어선}일 경우 추가 공간을 필요로 한다는 뜻 시간과 공간, 둘 다에 최적인 Li는 Li&, Huo(2016년)첫번째 저장하는 O(n){\displaystyle{{O\mathcal}을 주었다}(n)}시간 접미사 배열 구조 알고리즘입니다.array

향상된 접미사 배열(ESAs)은 접미사 트리의 전체 기능을 동일한 시간과 메모리 복잡성을 보존하는 추가 테이블이 있는 접미사 배열이다.^[1]문자열의 모든 접미사 부분 집합에 대한 접미사 배열을 스파스 접미사 배열이라고 한다.^[2]최적의 시간과 메모리 알고리즘을 포함한 추가 메모리 사용을 최소화하기 위해 다중 확률 알고리즘이 개발되었다.^[3]

정의

$Let{\displaystyle }$ S${\displaystyle }$= ${\displaystyle S}$[ ${\displaystyle 1}$ ${\displaystyle ]}$ S${\displaystyle }$[ ${\displaystyle 2}$ ${\displaystyle ]}$.${\displaystyle }$. . ${\displaystyle S}$[ ${\displaystyle n}$ ${\displaystyle ]}$ $[\displaystyle S=S[1]S[2]...$$S[n]}$은(는) $n$ ${\textstyle n}$ - 문자열이며$$, $S{\displaystyle }$[${\displaystyle }$i , ${\displaystyle j}$]$${\$displaystyle$ S$[i,j]}$은(는) ${\displaystyle i}$$${\$displaystyle i}$에서 j$${\$displaysty j}$까지의 S ${\displaystytype S}$의 하위 문자열을 나타낸다$$.

$이제{\displaystyle }$ S$${\$displaystyle$S}의$$ 접미사 $배열{\displaystyle }$ A$${\$displaystyle A$}은 사전순으로 S ${\displaystyle S}$의 접미사 시작 위치를 제공하는 정수 배열로 정의된다$$.This means, an entry ${\displaystyle A[i]}$ contains the starting position of the ${\displaystyle i}$-th smallest suffix in ${\displaystyle S}$ and thus for all ${\displaystyle 1<i\leq n}$: ${\displaystyle S[A[i-1],n]<$$S[A][i]n]}$

$S{\displaystyle }$ ${\displaystyle S}$의 각 접미사는 $A{\displaystyle }$ ${\displaystyle A}$에 정확히$$ 한 번 나타난다$$.접미사는 간단한 문자열이다.이러한 문자열은 $시작{\displaystyle }$ 위치(정수자 색인)가 A {\displaystyle $A}$에 저장되기 전에 (종이 사전과 같이) 정렬된다$.$

예

$S{\displaystyle }$ ${\displaystyle S}$= 텍스트 고려banana$인덱싱할 항목:

i	1	2	3	4	5	6	7
$S[i]}$	b	a	n	a	n	a	$

텍스트는 특수 sentinel 문자로 끝난다.$그것은 독특하고 사전 편찬적으로 다른 어떤 문자보다 작다.텍스트에는 다음과 같은 접미사가 있다.

이러한 접미사는 오름차순으로 정렬할 수 있다.

접미사 배열 $A{\displaystyle }$ ${\displaystyle A}$에는 다음과 같은 정렬된 접미사의 시작 위치가 포함되어$$ 있다.

i =	1	2	3	4	5	6	7
${\displaystyle A}$[ ${\displaystyle i}$ ${\displaystyle ]}$ ${\displaystyle A[i]}$ $$=	7	6	4	2	1	5	3

명확하게 하기 위해 아래에 수직으로 표시된 접미사가 있는 접미사 배열:

i =	1	2	3	4	5	6	7
${\displaystyle A}$[ ${\displaystyle i}$ ${\displaystyle ]}$ ${\displaystyle A[i]}$ $$=	7	6	4	2	1	5	3
1	$	a	a	a	b	n	n
2		$	n	n	a	a	a
3			a	a	n	$	n
4			$	n	a		a
5				a	n		$
6				$	a
7					$

$예$를 들어 $A{\displaystyle }$[ ${\displaystyle 3}$ ${\displaystyle ]}$ ${\displaystyle A[3]}$은(는) 값 4를 포함하므로$$ S ${\displaystyle S}$ 내의 위치 4에서 시작하는 접미사를 가리킨다$.$ana$.

접미사 트리에 대한 대응

접미사 배열은 접미사 트리와 밀접한 관련이 있다.

• 접미사 배열은 접미사 트리의 깊이 첫 번째 통과를 수행하여 구성할 수 있다.접미사 배열은 첫 번째 문자의 사전순으로 가장자리가 방문되는 경우, 이러한 라벨이 횡단하는 동안 방문되는 순서에 따라 주어진 잎 라벨에 해당한다.
• 접미사 트리는 접미사 배열과 LCP 배열의 조합을 이용하여 선형적으로 구성할 수 있다.알고리즘에 대한 설명은 LCP 어레이 문서의 해당 섹션을 참조하십시오.

모든 접미사 트리 알고리즘은 추가 정보(예: LCP 어레이)로 강화된 접미사 배열을 사용하는 알고리즘으로 체계적으로 대체할 수 있으며, 같은 문제를 동시에 복잡성으로 해결할 수 있는 것으로 나타났다.^[1]접미사 트리에 비해 접미사 배열의 장점으로는 공간 요구사항 개선, 선형 시간 구축 알고리즘(예: Ukkonen 알고리즘과 비교), 캐시 인접성 개선 등이 있다.^[4]

공간효율

접미사 배열은 접미사 나무의 공간 요구사항을 개선하기 위해 Manber & Myers(1990)에 의해 도입되었다.접미사 배열은 $n{\displaystyle }$ ${\displaystyle n}$의 정수를 저장한다.정수에 $4{\displaystyle \mathrm{}}$ ${\displaystyle 4}$바이트가$$ 필요하다고 가정하면 접미사 배열에는 총 ${\displaystyle \mathrm{4n}}$ ${\displaystyle 4n}$바이트가$$ 필요하다.이는 조심스러운 접미사 트리 구현에 필요한 ${\displaystyle \mathrm{20n}}$ ${\displaystyle 20n}$바이트보다$$ 훨씬 적다.^[5]

그러나 특정 애플리케이션에서 접미사 배열의 공간 요구사항은 여전히 엄청나게 많을 수 있다.비트로 분석된 접미사 배열은 $O{\displaystyle \mathcal{}(n}$ ${\displaystyle \log }$ ${\displaystyle n}$) ${\displaystyle {\mathcal{O}(n\log n)}$개의$$ 공간이 필요한 반면, 크기 $\sigma {\displaystyle }$ ${\displaystyle \sigma}$의 알파벳 문자 위에 있는 원본 텍스트는 $O{\displaystyle \mathcal{}(n}$ ${\displaystyle \log }$ ${\displaystyle \sigma }$ $){\mathcal$ {$O}(n\log \sigmathcal)$만 있으면$$ 된다$.$$\sigma {\displaystyle }$= ${\displaystyle 4}$ ${\displaystyle$$$$\sigma =4}$ 및 $n$ = 3${\displaystyle .4}$ ${\displaystyle \times }$ ${\displaystyle {10}^{}}$ ${\displaystyle {9\mathrm{}}^{}}$ ${\$ 인간 게놈의 경우.$따라서$ 접미사$$ $배열$은 게놈 자체보다 약 16배 많은 메모리를 차지할 것이다$.$

이러한 불일치는 압축 접미사 배열과 FM-지수와 같은 BWT 기반 압축 전체 텍스트 지수에 대한 추세를 자극했다.이러한 데이터 구조는 텍스트 크기 내에서 또는 심지어 더 적은 공간만 필요로 한다.

시공 알고리즘

A suffix tree can be built in ${\displaystyle {\mathcal {O}}(n)}$ and can be converted into a suffix array by traversing the tree depth-first also in ${\displaystyle {\mathcal {O}}(n)}$, so there exist algorithms that can build a suffix array in ${\displaystyle {\mathcal {O}}(n)}$.

접미사 배열을 구성하는 순진한 접근법은 비교 기반 정렬 알고리즘을 사용하는 것이다.These algorithms require ${\displaystyle {\mathcal {O}}(n\log n)}$ suffix comparisons, but a suffix comparison runs in ${\displaystyle {\mathcal {O}}(n)}$ time, so the overall runtime of this approach is ${\displaystyle {\mathcal {O}}(n^{2}\log n)}$.

보다 고급 알고리즘은 정렬할 접미사가 임의의 문자열이 아니라 서로 연관되어 있다는 점을 활용한다.이러한 알고리즘은 다음과 같은 목표를 달성하기 위해 노력한다.^[6]

• 최소 무증상 복잡성 $\theta {\displaystyle \mathrm{}(n}$) ${\displaystyle \Teta(n)}$
• 텍스트와 접미사 배열 자체 옆에 있는 작업 메모리가 거의 또는 전혀 필요 없는 공간에서의 경량
• 연습이 빠른.

모든 목표를 달성한 최초의 알고리즘 중 하나가 농, 장, 찬의 SA-IS 알고리즘(2009)이다.알고리즘은 다소 단순하며(< 100 LOC) LCP 어레이를 동시에 구성하도록 향상시킬 수 있다.^[7]SA-IS 알고리즘은 가장 빨리 알려진 접미사 배열 구조 알고리즘 중 하나이다.유타 모리의 신중한 구현은 대부분의 다른 선형 또는 초선형 건설 접근법을 능가한다.

시간 및 공간 요구사항 외에도 접미사 배열 구성 알고리즘은 지원되는 알파벳으로 구분된다. $알파벳{\displaystyle }$ 크기가 상수인 상수 알파벳 문자,$$n {\$displaystyle$n}에 따라 범위의 정수인 정수 문자 및 문자$$ 비교만 a인 일반 문자.재허가를 ^[8]받다

대부분의 접미사 배열 구성 알고리즘은 다음 방법 중 하나를 기반으로 한다.^[6]

• 접두사 더블링 알고리즘은 Karp, Miller & Rosenberg(1972)의 전략에 기초한다.그 아이디어는 접미사의 사전 순서를 존중하는 접두사를 찾는 것이다.평가된 접두사 길이는 접두사가 고유하고 관련 접미사의 순위를 제공할 때까지 알고리즘의 각 반복에서 두 배가 된다.
• 재귀 알고리즘은 Farach(1997)에 의한 접미사 트리 구성 알고리즘의 접근에 따라 접미사의 하위 집합을 재귀적으로 정렬한다.이 부분집합은 나머지 접미사의 접미사 배열을 유추하는 데 사용된다.그런 다음 이 두 접미사 배열을 병합하여 최종 접미사 배열을 계산한다.
• 유도복사 알고리즘은 이미 정렬된 부분집합을 사용하여 나머지 접미사의 빠른 종류를 유도한다는 점에서 재귀 알고리즘과 유사하다.차이점은 이러한 알고리즘이 선택한 접미사 부분 집합을 정렬하기 위해 반복보다 반복을 선호한다는 것이다.퍼글리시, 스미스 & 터핀(2007)에 의해 이 다양한 알고리즘 그룹에 대한 조사가 이루어졌다.

정수 알파벳에 대해 잘 알려진 재귀 알고리즘은 Kerkkhainen & Sanders(2003)의 DC3/꼬치 알고리즘이다.선형시간에 실행되며 병렬^[9] 및 외부 메모리^[10] 접미사 배열 알고리즘의 기반으로 성공적으로 사용되어 왔다.

Salson 외 연구진(2010)의 최근 연구는 처음부터 새로운 접미사 배열을 재구성하는 대신 편집된 텍스트의 접미사 배열을 업데이트하기 위한 알고리즘을 제안한다.이론적으로 최악의 경우 시간 복잡성이 $O{\displaystyle \mathcal{}(n}$ ${\displaystyle \log }$ $){\displaystyle {\mathcal{O}(n\log$ n$)\}$인 경우에도 실제로 잘 수행되는 것으로 보인다:저자의 실험 결과는 합리적인 접미사 배열의 삽입을 고려할 때 일반적으로 리빌딩보다 동적 접미사 배열의 구현이 더 효율적이라는 것을 보여주었다.원본 텍스트의 문자 수.

실제 오픈 소스 작업에서 접미사 배열 구성에 일반적으로 사용되는 루틴은 1999년 Larsson-Sadakane 알고리즘에 기반한 Qsufsort였다.^[11]이 루틴은 2017년 현재 "메인메모리 중 가장 빠른 것으로 알려진 접미사 정렬 알고리즘"인 유타 모리의 DivSufSort로 대체되었다.또한 LCP 어레이를 계산하도록 수정할 수 있다.이토-타나카와 결합한 유도 복사를 사용한다.^[12]2021년 Ilya Grebnov에 의해 알고리즘의 더 빠른 구현이 제시되었는데, 이는 Silesia Corpus에서 DivSufSort 구현에 비해 평균 65%의 성능 향상을 보였다.^[14]

일반화 접미사 배열

접미사 배열의 개념은 둘 이상의 문자열로 확장할 수 있다.This is called a generalized suffix array (or GSA), a suffix array that contains all suffixes for a set of strings (for example, ${\displaystyle S=S_{1},S_{2},S_{3},...,S_{k}}$ and is lexicographically sorted with all suffixes of each string.^[15]

적용들

문자열의 접미사 배열을 인덱스로 사용하여 $문자열{\displaystyle }$ S ${\displaystyle S}$ 내에서$$ 하위 문자열 $패턴{\displaystyle }$ P ${\displaystyle P}$의 모든 발생을 신속하게 찾을 수 있다$.$ 패턴의 모든 발생을 찾는 것은 하위 문자열에서 시작하는 모든 접미사를 찾는 것과 같다.사전순서 덕분에 이들 접미사는 접미사 배열에서 함께 그룹화되며 2개의 이진 검색으로 효율적으로 찾을 수 있다.첫 번째 검색은 간격의 시작 위치를 찾고 두 번째 검색은 끝 위치를 결정한다.^{[citation needed]}

n = 렌(S) 반항하다 샅샅이 뒤지다(P: 발을 동동 구르다) -> 투플레[인트로, 인트로]:     """ 구간 A[s:r](끝 포함)와 같은 지수(s, r) 반환 지수)는 패턴 P로 시작하는 S의 모든 접미사를 나타낸다. """     # 간격의 시작 위치 찾기     l = 0  # Python에서 어레이는 0부터 인덱싱됨     r = n     하는 동안에 l < r:         중앙의 = (l + r) // 2  # 가장 가까운 정수로 반올림         # 접미사At(A[i])는 가장 작은 접미사다.         만일 P > 접미사 At(A[중앙의]):             l = 중앙의 + 1         다른:             r = 중앙의     s = l          # 간격의 끝 위치 찾기     r = n     하는 동안에 l < r:         중앙의 = (l + r) // 2         만일 접미사 At(A[중앙의]).로부터 시작하다(P):             l = 중앙의 + 1         다른:             r = 중앙의     돌아오다 (s, r) 

$길이{\displaystyle }$ n {\$displaystyle{\displaystyle }$ n} 문자열 S {\displaystyle $S$$}$에서 길이 $m{\displaystyle }$ ${\displaystyle$ m$}$의 하위 문자열 $패턴{\displaystyle }$ P ${\displaystyle$ ${\displaystyle P\}}$을(를$)$ 찾으려면 단일 접미사 비교가 m ${\stylematcal$ {$O$$}(m\displaystylem$$})$ 문자를$$ 비교해야 하므로 O($시간$)이 소요된다$.$Manber & Myers(1990)는 LCP 정보를 사용하여 이 바인딩을 $O{\displaystyle \mathcal{}(m}$+ ${\displaystyle \log }$ ${\displaystyle n}$) ${\displaystyle {\mathcal {O}(m+\log n)}$시간으로$$ 개선할 수 있는 방법을 설명한다.패턴 비교가 패턴의 가장 긴 공통 접두사 및 현재 검색 간격의 일부라는 것이 이미 알려진 상황에서 특정 문자를 다시 비교할 필요가 없다는 생각이다.아부엘호다, 쿠르츠 & 올레부슈(2004)는 바운드를 한층 더 개선하고 접미사 나무에서 알려진$$ $){\displaystyle {\mathcal{O}(m)}$의 검색 시간을 달성한다.

접미사 정렬 알고리즘을 사용하여 버로우스를 계산할 수 있음-휠러 변환(BWT).BWT는 문자열의 모든 주기적 순열의 정렬을 요구한다.이 문자열이 다른 모든 문자(예: $)보다 사전순으로 작은 특수 문자열 끝 문자로 끝나는 경우 정렬된 회전 BWT 행렬의 순서는 접미사 배열의 접미사 순서에 해당한다.따라서 BWT는 먼저 텍스트의 접미사 배열을 구성한 다음 BWT 문자열: ${\displaystyle \mathrm{BWT}}$[ ${\displaystyle i}$ ${\displaystyle ]}$= ${\displaystyle S}$[ ${\displaystyle A}$[ i${\displaystyle }$] - ${\displaystyle 1}$]$${\$displaystyle BWT$[i$]=$를 추론하여 선형 시간으로 계산할 수 있다.$S[A[i$]-1$]\}.$

접미사 배열은 또한 예시 기반 기계 변환에서 하위 문자열을 검색하는 데 사용될 수 있으며, 통계 기계 변환에서 사용된 전체 구문 표보다 훨씬 적은 저장 공간을 요구한다.

접미사 어레이의 많은 추가 애플리케이션에는 LCP 어레이가 필요하다.이들 중 일부는 후자의 적용 부분에 자세히 설명되어 있다.

향상된 접미사 배열

접미사 트리는 패턴과 문자열 매칭, 인덱싱 및 텍스트 통계 영역에 광범위하게 적용되는 강력한 데이터 구조다.그러나, 그것은 상당한 공간을 차지하기 때문에 게놈 분석과 같은 상당히 많은 양의 데이터를 처리해야 하는 많은 실시간 애플리케이션에서 단점이 있다.이러한 단점을 극복하기 위해 접미사 배열로 구성된 데이터 구조와 접미사 트리 내 노드 간의 부모-자녀 관계에 대한 정보를 포함하는 하위 테이블이라는 추가 테이블을 개발했다.이 트리의 노드 분기 데이터 구조는 링크된 목록이다.강화된 접미사는 공간 효율성과 시간 복잡성 측면에서 모두 우수하며 구현이 용이하다.더욱이 추상 개념 lcp-간격 트리를 사용하여 접미사 트리를 사용하는 알고리즘에는 어떤 것이든 적용할 수 있다.확장 접미사 배열에서 패턴을 검색하기 위한 시간 복잡도는 O(m σ )이다.

문자열의 접미사 배열은 특수 문자 #를 포함한 문자열의 n+1 접미사를 나타내는 0~n 범위의 n 정수 배열이다.

접미사 배열은 두 개의 배열로 구성된다.

1. pos 어레이 pos[1,...n]: 모든 S 접미사의 정렬된 목록을 나타낸다.접미사가 너무 크기 때문에 공간 복잡성을 줄이기 위해 접미사의 초기 위치만 배열로 저장된다.
2. lcp 어레이 lcp[1,...n]:pos 배열에 저장된 두 연속 접미사의 가장 긴 공통 접두사 길이를 유지하는 n 정수의 배열이다.

lcp 간격 구성

S의 접미사 배열의 경우, S의 접미사 트리의 해당 노드와 관련된 lcp-간격은 다음과 같이 정의할 수 있다.

구간 [i, ..j], 0 ≤ i ≤ j ≤ n은 lcp-값의 lcp-interval이다.

1. lcptab[i] < l,

2. 모든 i에 대한 lcptab[k] l + 1 ≤ k ≤ j,

3. lcptab[k] = l 일부 i의 경우 l + 1 k k j j, l = n - i + 1 i = j,

4. lcptab[j + 1] < l.

pos[i - 1]와 pos[i]의 가장 긴 공통 접두사 길이는 lcp[i]에 저장되며, 여기서 2 ≤ i ≤ n이 된다.lcp-간격은 S의 접미사 트리에 있는 관련 노드 사이의 것과 동일한 부모-자녀 관계를 나타낸다.이는 [i..]의 해당 노드가 다음과 같은 것을 보여준다.j]는 lcp-cp[i..l]의 해당 노드[k..l]j]는 다른 lcp-cp[k..l]의 자식 간격이다.[k..l]이 [i..j]의 하위 간격인 경우, lcp-interval [i...j]는 lcp-cp[k..l]의 상위 간격이다.

하위 테이블 구성

하위 테이블 cldtab은 up, down 및 nextlIndex의 세 개의 배열로 구성된다.해당 접미사 트리의 가장자리에 대한 정보는 위쪽 및 아래쪽 배열로 유지 관리되며 에 저장된다.nextlIndexarray는 접미사 트리를 분기하는 노드에 사용되는 링크된 목록에 링크를 저장한다.

up, down 및 nextlIndex 배열은 다음과 같이 정의된다.

1. 소자는 지수 i-1에서 끝나는 가장 긴 lcp 초 간격의 자식 간격의 시작 지수를 기록한다.
2. 가장 긴 lcp-interval의 두 번째 자식 간격(index i)의 초기 지수는 아래[i] 요소에 저장된다.
3. 구간이 부모의 첫 번째 자식 또는 마지막 자식이 아닌 경우에만 nextlIndex[i] 요소는 지수 i에서 시작하여 가장 긴 lcp-interval의 다음 형제 간격의 첫 번째 인덱스를 포함한다.

트리의 lcp-간격의 상향 횡단을 수행함으로써 하위 테이블을 선형 시간으로 구성할 수 있다.위/아래 값과 다음 lIndex 값은 두 개의 구별되는 알고리즘을 사용하여 별도로 계산할 수 있다.

접미사 링크 테이블 구성

확장 접미사 배열에 대한 접미사 링크는 사전 처리 중에 각 [i, ..j] 간격에 대해 접미사 링크 간격[1, ..,r]을 생성하여 계산할 수 있다.구간의 좌우 요소 l와 r은 [i, ..,j]의 첫 번째 지수에서 유지된다.이 간격의 표는 0에서 n까지입니다.접미사 링크 테이블은 lcp-interval 트리의 왼쪽에서 오른쪽으로 첫 번째 통과에 의해 구성된다.l-간격이 계산될 때마다 l-간격 목록에 추가되는데, 이를 l-list라고 한다.lcp-값 > 0이 되면 목록의 l-interval[i, ..,j]마다 링크[i]가 계산된다.구간[l, ..,r]은 (l-1)-list의 이진 검색에 의해 계산되며, 여기서 l은 모든 l-1 구간 중에서 가장 큰 왼쪽 경계다.[i, ..j]의 접미사 링크 간격이 이 구간[l, ..,r]으로 표시된다.l과 r 값은 궁극적으로 [i, ..,j]의 첫 번째 색인에 저장된다.

메모들

참조

• Manber, Udi; Myers, Gene (1990). Suffix arrays: a new method for on-line string searches. First Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 319–327.
• Manber, Udi; Myers, Gene (1993). "Suffix arrays: a new method for on-line string searches". SIAM Journal on Computing. 22 (5): 935–948. doi:10.1137/0222058. S2CID 5074629.
• Gawrychowski, Paweł; Kociumaka, Tomasz (January 2017). "Sparse Suffix Tree Construction in Optimal Time and Space". Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics: 425–439. arXiv:1608.00865. doi:10.1137/1.9781611974782.27. ISBN 9781611974782. S2CID 6608776.
• Li, Zhize; Li, Jian; Huo, Hongwei (2016). Optimal In-Place Suffix Sorting. Proceedings of the 25th International Symposium on String Processing and Information Retrieval (SPIRE). Lecture Notes in Computer Science. Vol. 11147. Springer. pp. 268–284. arXiv:1610.08305. doi:10.1007/978-3-030-00479-8_22. ISBN 978-3-030-00478-1.
• Shi, Fei (1996). Suffix arrays for multiple strings: A method for on-line multiple string searches. Lecture Notes in Computer Science. Vol. 1179. Springer Berlin Heidelberg. pp. 11–22. doi:10.1007/BFb0027775. ISBN 978-3-540-62031-0.
• Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2002). The Enhanced Suffix Array and Its Applications to Genome Analysis. Algorithms in Bioinformatics. Lecture Notes in Computer Science. Vol. 2452. doi:10.1007/3-540-45784-4_35. ISBN 978-3-540-44211-0.
• Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (March 2004). "Replacing suffix trees with enhanced suffix arrays". Journal of Discrete Algorithms. 2 (1): 53–86. doi:10.1016/S1570-8667(03)00065-0. ISSN 1570-8667.
• Gonnet, G.H; Baeza-Yates, R.A; Snider, T (1992). "New indices for text: PAT trees and PAT arrays". Information Retrieval: Data Structures and Algorithms.
• Kurtz, S (1999). "Reducing the space requirement of suffix trees". Software: Practice and Experience. 29 (13): 1149–1171. doi:10.1002/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O. hdl:10338.dmlcz/135448.
• Puglisi, Simon J.; Smyth, W. F.; Turpin, Andrew H. (2007). "A taxonomy of suffix array construction algorithms". ACM Computing Surveys. 39 (2): 4. doi:10.1145/1242471.1242472. S2CID 2653529.
• Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009). Linear Suffix Array Construction by Almost Pure Induced-Sorting. 2009 Data Compression Conference. p. 193. doi:10.1109/DCC.2009.42. ISBN 978-0-7695-3592-0.
• Fischer, Johannes (2011). Inducing the LCP-Array. Algorithms and Data Structures. Lecture Notes in Computer Science. Vol. 6844. p. 374. arXiv:1101.3448. doi:10.1007/978-3-642-22300-6_32. ISBN 978-3-642-22299-3.
• Salson, M.; Lecroq, T.; Léonard, M.; Mouchard, L. (2010). "Dynamic extended suffix arrays". Journal of Discrete Algorithms. 8 (2): 241. doi:10.1016/j.jda.2009.02.007.
• Burkhardt, Stefan; Kärkkäinen, Juha (2003). Fast Lightweight Suffix Array Construction and Checking. Combinatorial Pattern Matching. Lecture Notes in Computer Science. Vol. 2676. p. 55. doi:10.1007/3-540-44888-8_5. ISBN 978-3-540-40311-1.
• Karp, Richard M.; Miller, Raymond E.; Rosenberg, Arnold L. (1972). Rapid identification of repeated patterns in strings, trees and arrays. Proceedings of the fourth annual ACM symposium on Theory of computing - STOC '72. p. 125. doi:10.1145/800152.804905.
• Farach, M. (1997). Optimal suffix tree construction with large alphabets. Proceedings 38th Annual Symposium on Foundations of Computer Science. doi:10.1109/SFCS.1997.646102. ISBN 0-8186-8197-7.
• I, Tomohiro; Kärkkäinen, Juha; Kempa, Dominik (2014). Faster Sparse Suffix Sorting. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 25. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik. pp. 386–396. doi:10.4230/LIPIcs.STACS.2014.386. ISBN 978-3-939897-65-1.
• Kärkkäinen, Juha; Sanders, Peter (2003). Simple Linear Work Suffix Array Construction. Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 2719. doi:10.1007/3-540-45061-0_73. ISBN 978-3-540-40493-4.
• Dementiev, Roman; Kärkkäinen, Juha; Mehnert, Jens; Sanders, Peter (2008). "Better external memory suffix array construction". Journal of Experimental Algorithmics. 12: 1–24. doi:10.1145/1227161.1402296. S2CID 12296500.
• Kulla, Fabian; Sanders, Peter (2007). "Scalable parallel suffix array construction". Parallel Computing. 33 (9). doi:10.1016/j.parco.2007.06.004.
• 모하메드 이브라힘 아부엘호다, 스테판 쿠르츠, 엔노 올레부쉬."접미사 배열이 강화된 접미사 트리 교체." 이산 알고리즘 저널 2:1:53–86, 2004.
• 김동규, 정은전, 박희진."접미사 트리와 접미사 배열의 기능을 갖춘 효율적인 인덱스 데이터 구조로, 비접미성 크기의 알파벳을 위한 것이다."String Processing and Information Research Listen Note in Computer Science, 138–149, 2004.

외부 링크

위키미디어 커먼스는 접미사 배열과 관련된 미디어를 가지고 있다.

• Java의 접미사 배열
• BWT용 접미사 정렬 모듈(C 코드)
• 루비에서 접미사 배열 구현
• 배열 라이브러리 및 도구 접미사
• 다양한 접미사 어레이 c/c++ 통합 인터페이스를 사용한 구현이 포함된 프로젝트
• 접미사 어레이를 구성하기 위한 빠르고 가볍고 강력한 C API 라이브러리
• Python의 접미사 어레이 구현
• 접미사 트리를 사용하여 C에서 선형 시간 접미사 배열 구현