티스토리 뷰

공부

Suffix Array (접미사 배열)

구사과 2016. 8. 29. 08:32

다음과 같은 참고 자료들이 있으니 같이 보자.

http://web.stanford.edu/class/cs97si/suffix-array.pdf

http://web.stanford.edu/class/cs97si/10-string-algorithms.pdf

http://blog.myungwoo.kr/57

http://m.blog.naver.com/dark__nebula/220419358547



Suffix Array는 문자열과 부분문자열을 가지고 놀 수 있는 자료구조이다. 이름만 보면 도대체 어디에 쓰는 것인지 잘 이해도 안 가고 왜 배우는 지도 알 수 없을 것이다. 일단, Suffix Array를 통해서 쉽게 풀 수 있는 문제 몇가지를 나열하자면 :

 * 길이 |S|의 스트링 하나와, Q개의 길이 Ti의 스트링이 주어진다. O(Sum(|T|)) 즈음의 시간에 주어진 Q개의 스트링이 부분문자열인지 판별할 수 있는가? ( KMP 알고리즘으로는 O(|S|*Q)의 시간이 걸린다 )

 * 문자열 |S|의 위치 p1, p2가 있을 때, [p1, p1 + l - 1] == [p2, p2 + l - 1]을 만족하는 가장 긴 l을 쿼리당 빠르게 구할 수 있는가? (Longest common prefix라고도 불리는 문제이다)

Suffix Array로 풀리는 굉장히 유명한 문제들은 대충 이렇다. 보통 주어진 긴 문자열의 부분문자열과 관련된 문제에서 매우 유용하게 사용되는 자료구조이다.


먼저, Suffix Trie라는 자료구조를 소개하려고 한다. Suffix Trie는 문자열 S에 대해서, S의 접미사들을 모두 넣고 만든 trie이다. 시간 복잡도와 공간 복잡도는 대략 O(N^2) 정도이다. 이러한 자료구조가 만들어져 있다면, 위 두 문제는 다음과 같이 해결할 수 있다.

 * 1번 문제는 단순한 trie 순회로 해결 가능하다. 즉, O(Sum(|T|))

 * 2번 문제는, [p1, |S| - 1] suffix와 [p2, |S| - 1] suffix로 만들어 낸 path가 얼마나 겹치는지를 계산함으로써 풀 수 있다. 이 때, 이 과정이 트리의 LCA를 구하는 과정과 똑같다는 것을 알면, 시간 복잡도를 향상시킬 수 있다. (O(lgN))


애석하게도, Suffix Trie는 O(N^2)에서 시간 복잡도를 향상시키기 쉽지 않다. Suffix Tree라는, O(N)짜리 Suffix Trie의 변형이 있기는 한데 매우 복잡하니 그냥 모른척 해주자. 우리가 배울 Suffix Array는 Suffix Trie의 강력한 부분문자열 검색 능력을, O(N) 메모리와 O(NlgN) 시간 복잡도에 해주는 꿀같은 자료구조이다. (사실 Suffix Array도 O(N)에 계산 가능하지만 꽤 복잡하니 모른척 해주자...)


문자열 |S|의 Suffix Array sfx[]는, 모든 sfx[i]에 대해서, 사전순으로 (i+1)번째인 suffix가 S[sfx[i], N-1] 를 만족하는 자료구조이다. 이렇게 얘기하면 무슨 말인지 알기 쉽지 않지만, 쉽게 말해서 모든 suffix를 정렬했다고 생각하면 된다.

S = "banana" 일때, S의 suffix는 {"banana", "anana", "nana", "ana", "na", "a"} 이다. 이걸 토대로 suffix array를 만들면

sfx[0] = 5 ("a")

sfx[1] = 3 ("ana")

sfx[2] = 1 ("anana")

sfx[3] = 0 ("banana")

sfx[4] = 4 ("na")

sfx[5] = 2 ("nana")


sfx[i]에는, 각각의 부분 문자열의 시작 위치가 저장되어 있고, 이 suffix array를 따라 suffix를 찍어보면 모두 사전순 정렬되어 있다는 것을 알 수 있다. 이제 이러한 자료구조를 어떻게 O(NlgN)에 만드는 지가 관건이다.

Naive한 O(N^2lgN) 방법은, cmp 함수를 O(N)에 작동하게 한 후 단순히 sort를 함으로써 가능하다. 이를 O(NlgN)으로 줄이려면, 길이 K인 suffix를 정렬한 suffix array에서, 길이 2K인 suffix를 정렬한 suffix array를 O(N)에 유도할 수 있다는 것을 이해해야 한다. 길이를 2^K >= N까지 늘리면 suffix array를 만들 수 있으니, O(N)에 유도할 수 있으면 O(NlgN)에 해결할 수 있다.

먼저, O(NlgN)에 유도하는 법에 대해서 생각해보자. ord[i] = i에서 시작하는 suffix array의 순위라고 생각해보자. 순위라는 말이 참 애매하지만, 대충 "정렬 기준" 이라고 생각하면 편하겠다. 목표는, ord[sfx[i]] = i를 만족할 때까지, ord 배열을 계속 조정하는 것이다.

처음 ord[i] = str[i] 로 잡자. 즉, 각각의 suffix의 첫 글자를 기준으로 정렬 기준을 설정하는 것이다. 만약에 suffix의 첫 글자가 다르다면 순서가 맞겠지만 아닐 때는 순서를 구분할 수 없을 것이다. 이를 위해서, [0 ~ N-1] 까지의 숫자가 담긴 배열을 다음과 같은 정렬 함수로 정렬하자.

 ord[i] != ord[j]라면 ord[i] < ord[j] 순으로 정렬한다. 아닐 경우, ord[i+1] < ord[j+1] 순으로 정렬한다. 만약, ord[x]를 접근할 때 x >= |S|일 경우, ord[i] = -inf.

이렇게 suffix array를 만들었다면, suffix의 두 글자 까지는 순서를 구분할 수 있게 된다. 현재의 suffix array를 순서대로 순회하는데, ord[i] == ord[j] 이면서 ord[i+1] == ord[j+1] 일 경우 order 값을 같은 값을 주고, 아닐 경우 순서대로 증가하는 형태로 새로운 order를 주면 되기 때문이다. ( [0, 0, 0, 0, 1, 1, 2, 3, 4, 5.. ] 이런 느낌. ) 이제 1 -> 2 -> 4 -> 8로 이 값을 충분히 늘려나가면 O(Nlg^2N)에 문제를 해결할 수 있다. (https://gist.github.com/koosaga/44532e5dec947132ee55da0458255e05 코드의 33 - 42줄이 이러한 내용을 구현했다.)

이를 O(N)으로 줄이는 것이 관건인데, 이는 counting sort로 해결 가능하다. ord[i]의 값이 counting sort로 해결할 수 있는 범위이니, 위의 정렬을 O(N)에 해결하면 되는 것이다. 다만 두개의 인자를 봐야 하는 것이 문제인데, 아무 수열이나 잡고 ord[i+p]를 기준으로 counting sort를 먼저 해 둔 후, ord[i+p] 가 증가하는 순으로 보면서 ord[i]를 기준으로 또 counting sort를 하면 된다.

이러한 내용의 구현이 아래 파일에 적혀있다.

https://gist.github.com/koosaga/44532e5dec947132ee55da0458255e05


Suffix array를 만들었지만, 여전히 suffix trie를 어떻게 대체할 수 있는지는 감이 잡히지 않는다. 이를 위해서 LCP라는 배열을 또 하나 만들어야 한다. LCP[i] = 문자열의 [sfx[i-1], N-1] / [sfx[i], N-1] 이 있을 때, 겹치는 가장 긴 공통 prefix의 길이를 저장하는 것이다. 위에서 정의한 Longest common prefix 문제랑 상당히 유사한데, 이상하게 suffix array 상에서 인접한 것만 구한다. 이는, suffix array 상에서 인접한 것만 구한다면 모든 문자열의 LCP를 구할 수 있기 때문이다. 위에 정의한 longest common prefix가 이렇게 풀린다.

정확히는, s에서 시작하는 suffix와 t에서 시작하는 suffix를 생각해보자, rev[x] = (sfx[i] == x를 만족하는 i) 라고 정의했을 때, 일반성을 잃지 않고 rev[s] < rev[t]라고 생각해 보면, s와 t의 LCP는 Min(lcp[rev[s] + 1], lcp[rev[s] + 2] .. lcp[rev[e]]) 이다. 이는 구간에 대한 최솟값 문제(Range mininum query, RMQ) 이기 때문에, O(NlgN) / O(1) 전처리에 해결할 수 있다.

LCP는 O(N)에 짧은 코드로 구현할 수 있다. 이 부분에 대한 구현은 위 링크의 48 - 58줄에 적혀 있다. 알고리즘의 정당성에 관련된 부분은 이 블로그를 참고하라.


Suffix Array에 대한 정보를 알고 있으니, 이제 1번 문제를 풀기에는 충분하다. S $ T1 $ T2 $ T3 ... 의 형태로 모든 스트링을 붙여서 ($든 뭐든 원래 문자열에 안 나오는 문자면 상관이 없다.) suffix array를 만들고 LCP를 구하자. S에 있는 임의의 원소 p와, Ti과의 LCP가 |Ti| 이상이면 성공이다. 이 때, Ti의 LCP를 최대화 하려면 suffix array 상에서 가장 가까운 S의 원소를 보는 게 좋으므로, 왼쪽으로 가까운 / 오른쪽으로 가까운 S의 원소를 고르고, LCP를 구해서 하나라도 |Ti| 이상의 LCP를 가지는지 체크하면 전처리 후 쿼리당 O(1)에 문제를 해결할 수 있다. (온라인 풀이도 있다.)


몇가지 추가적인 연습 문제로 글을 마무리하겠다. 난이도순.

* BOJ 1605. 반복 문자열 https://www.acmicpc.net/problem/1605

* BOJ 9249. 최장 공통 부분 문자열

* Balkan OI 2015. Clarkson https://www.acmicpc.net/problem/11555

* Polish OI 2005. Templates https://www.acmicpc.net/problem/7966

* Baltic OI 2004. Repeats http://www.spoj.com/problems/REPEATS/


'공부' 카테고리의 다른 글

problem solving 2016.09.24  (0) 2016.09.24
BOJ 1209 단조수열 만들기 : O(NlgN)  (1) 2016.09.15
Suffix Array (접미사 배열)  (3) 2016.08.29
problem solving 20160828-1  (0) 2016.08.28
HDU 5306. Gorgeous Sequence  (0) 2016.06.30
Offline solution of Dynamic Connectivity Problem  (2) 2016.06.26
댓글
  • 프로필사진 plzrun 이제야 LCP까지 다 이해했네요. :D 저번 슬렉 답변 감사합니다 ㅎ 2016.09.21 20:56
  • 프로필사진 plzrun 근데 구사과님 suffix array 코드에 ord[n]이랑 nord[n]을 0으로 초기화 하지 않아도 괜찮은가요? 포인터로 넘겨받을때부터 0이 들어있는거죠? 2016.09.21 21:00
  • 프로필사진 구사과 답글 감사합니다 :)

    ord[n] = 0이라는 조건 필요합니다. memset으로 ord는 전부 0으로 초기화해놨습니다. nord는 임시 배열이라 필요 없습니다.
    2016.09.25 00:00 신고
댓글쓰기 폼
공지사항
Total
770,884
Today
518
Yesterday
1,620