접미사 트리 (파트 1: 정의와 응용)
이 글은 트라이(trie) 자료구조에 대한 배경지식을 전제로 합니다.
부분문자열에 대한 다양한 문제를 선형 시간에 해결할 수 있는 접미사 트리 자료구조를 소개합니다. 이론 및 구현은 쉽지 않지만, 여러 문자열 문제들을 자명하게 만들거나 더 어려운 문자열 문제들을 해결하는 데 유용하게 쓸 수 있습니다.
문자열 $S$의 길이를 $m$이라고 하고, $i$번째부터 $j$번째까지 글자로 이루어진 부분문자열을 $S[i..j]$로 표기하겠습니다.
접미사 트라이
먼저, $S$의 모든 접미사로 이루어진 트라이를 생각해 봅시다. 이를 접미사 트라이(suffix trie)라고 합니다. 예를 들어 아래는 문자열 banana에 대한 접미사 트라이입니다.
<root>
/ | \
a b n
/ | \
n a a
/ | |
a n n
| | |
n a a
| |
a n
|
a
생각을 좀 더 편하게 하기 위해, 각 접미사가 트라이의 리프 노드에 해당한다고 생각합시다. $S$의 끝에 끝 문자(termination symbol)를 추가하면 됩니다. 이 끝 문자는 원본 문자열 $S$에만 나타나지 않으면 무엇이든 가능하고, 여기서는 $을 사용했습니다. 아래는 문자열 banana$에 대한 접미사 트라이입니다.
(※ “끝 문자”는 널리 합의된 번역이 아니라 제가 임의로 한 번역입니다.)
<root>
/ | \
a b n
/ \ | \
n $ a a
/ | |\
a n n $
|\ | |
n $ a a
| | |
a n $
| |
$ a
|
$
접미사 트라이의 공간 복잡도는 최악의 경우 $O(m^2)$이기 때문에, 시간 복잡도를 $O(m^2)$보다 빠르게 할 수는 없습니다. 따라서 접미사 트라이의 구현은 매우 쉽습니다. 그냥 트라이와 똑같은 방법으로 만들면 됩니다.
접미사 트리
접미사 트라이에서, 어떤 노드의 자식이 하나뿐일 경우 그 자식을 자신과 합칩니다. 즉,
- 노드 B의 부모가 A이고, 자식이 C라고 합시다.
- 또한 A에서 B로 가는 간선의 레이블이 X, B에서 C로 가는 간선의 레이블이 Y라고 합시다.
- 이제 B를 지우고, A에서 C로 간선을 긋고 XY라는 레이블을 답니다. B는 이 간선 안에 들어있는 숨은 노드(implicit node)라고 할 수 있습니다.
(※ “숨은 노드”는 제가 임의로 한 번역입니다.)
모든 노드에 대해 이 과정을 적용하면 접미사 트리(suffix tree)가 됩니다.
<root>
/ | \
a banana$ na
/ \ | \
na $ na$ $
/ \
na$ $
이러면 노드의 개수는 최대 $2m$이 됩니다. (최악의 케이스의 예시로 끝 문자 제외한 모든 글자가 같은 문자열이 있습니다.) 왜냐하면,
- 리프 노드는 접미사에 일대일 대응되므로 $m$개 존재합니다.
- 리프가 아닌 노드는 루트를 제외하면 두 갈래 이상으로 나뉩니다. 리프 노드의 개수 만큼만 갈라질 수 있으므로, 리프가 아닌 노드는 최대 $m$개입니다.
하지만 트리가 압축될 수록 레이블이 길어지기 때문에, 공간 복잡도는 여전히 $O(m^2)$입니다. 그래서 레이블 전체를 기록하는 게 아니라, 각 간선의 레이블이 $S$의 어느 부분을 나타내는지를 기록합니다. 예를 들어, 아래 그림에서 [5..7]은 5번째 글자부터 7번째 글자까지인 na$입니다. 이제 공간 복잡도는 $O(m)$입니다.
<rootrootroot>
/ | \
[2..2] [1..7] [3..4]
/ \ | \
[3..4] [7..7] [5..7] [7..7]
| \
[5..7] [7..7]
물론 시간 복잡도는 여전히 $O(m^2)$입니다. 이를 $O(m)$으로 줄이는 방법은 후술합니다. 저의 $O(m)$ 구현은 https://github.com/jh05013/PythonAlgorithms/blob/master/cpp05013/SuffixTree.cpp에서 볼 수 있습니다.
일반화된 접미사 트리
문자열 $S_1, S_2, \cdots, S_k$의 접미사로 이루어진 하나의 접미사 트리를 만들 수도 있습니다. 이것을 일반화된 접미사 트리(generalized suffix tree)라고 합니다. 일반화된 접미사 트리를 만드는 흔한 방법은 각 문자열마다 서로 다른 끝 문자를 붙이고, 이를 모두 일렬로 이어붙인 다음 그 문자열의 접미사 트리를 만드는 것입니다. 아래는 sec과 mem의 일반화된 접미사 트리로, 두 문자열을 sec$mem%로 이어붙여서 만들었습니다. 편의를 위해 [l..r] 형태가 아니라 부분문자열 전체를 레이블로 사용했습니다.
<rootrootrootrootrootroot>
/ | | | | \
c$mem% e m sec$mem% $mem% %
/ \ / \
c$mem% m% em% %
그런데 이러면 문자열 sec$만 볼 때에도 그 뒤에 mem%이 따라붙게 됩니다. 이걸 지우려면, 끝 문자가 레이블에서 하나라도 나오면 그 뒷부분을 모두 지우면 됩니다. 그런 레이블의 자식 서브트리들을 지울 필요는 없는데, 끝 문자는 항상 리프 노드에만 등장하여 자식 서브트리가 없기 때문입니다.
왜일까요? 일반화된 접미사 “트라이”를 생각해 봅시다. 각각의 끝 문자는 유일하기 때문에, 그 밑으로는 계속 자식이 하나만 나옵니다. 자식이 하나이면 접미사 트리에서는 합쳐지므로, 결국 리프 노드까지 쭉 합쳐집니다. 따라서 레이블에 끝 문자가 있는 노드는 리프 노드입니다.
<rootrootrootroot>
/ | | | | \
c$ e m sec$ $ %
/ \ / \
c$ m% em% %
접미사 트리로 무엇을 할 수 있는가?
중요한 점은, 접미사 트리에는 사실 모든 부분문자열이 들어있다는 것입니다. 접미사 트라이의 루트를 제외한 각 노드는 모든 서로 다른 부분문자열과 일대일 대응되고, 마찬가지로 접미사 트리의 루트를 제외한 노드 및 숨은 노드는 모든 서로 다른 부분문자열과 일대일 대응됩니다.
그 이유는 부분문자열이 접미사의 접두사이기 때문입니다. 예를 들어, banana에는 부분문자열 na가 있고, 이것은 접미사 nana 또는 na의 접두사입니다. 접미사 트리의 루트에서 nana 접미사로 내려가는 길의 중간에 멈추면 na가 됩니다. (다만, 꼭 실제로 존재하는 노드에서 멈추는 것은 아니고 숨은 노드에서 멈출 수도 있습니다.) 그래서 접미사 트리는 부분문자열 관련 문제에서 유용하게 쓸 수 있습니다.
접미사 트리로 몇 가지 문제를 풀어봅시다. 접미사 트라이를 사용하는 풀이를 먼저 생각한 다음에, 그 풀이를 접미사 트리로 옮기는 것을 추천드립니다.
부분문자열 판별
문제: $S$를 $O(m)$에 전처리한 후, 길이 $k$의 문자열 $P$가 들어왔을 때 $P$가 $S$의 부분문자열인지 $O(k)$만에 판별하세요. 즉 $P$가 들어올 때마다 $S$ 전체를 훑어볼 필요가 없습니다.
트라이 풀이: $S$의 접미사 트라이의 루트에서 시작해서, $P$의 각 글자를 따라 내려갑니다. 내려갈 노드가 없는 경우가 한 번이라도 발생하면 $P$는 $S$의 부분문자열이 아니고, 모든 글자를 따라 내려갈 수 있으면 부분문자열입니다.
트리 풀이: 위와 같지만, 숨은 노드도 하나씩 거쳐가야 합니다.
부분문자열 위치
문제: $S$를 $O(m)$에 전처리한 후, 길이 $k$의 문자열 $P$가 들어왔을 때 $P$가 $S$ 안에 등장하는 횟수, 첫 위치, 마지막 위치를 모두 $O(k)$만에 판별하세요.
트라이 풀이: 위와 같은 방식으로 내려갑니다. 도착한 노드를 루트로 하는 서브트리에 있는 리프 노드의 개수, 리프 노드 번호의 최솟값, 최댓값이 답입니다. 이는 트리 DP로 간단하게 전처리할 수 있습니다.
트리 풀이: 같은 방식으로 내려갑니다. 숨은 노드에서 멈췄으면, 쭉 내려가서 실제로 존재하는 노드로 갑니다. 이제 그 서브트리에서 위와 같이 풀면 됩니다.
서로 다른 부분문자열
문제: $S$의 서로 다른 부분문자열의 개수를 $O(m)$에 구하세요.
트라이 풀이: $S$에 끝 문자를 추가하지 않은 채로 접미사 트라이를 만듭니다. 루트를 제외한 노드의 개수가 답입니다.
트리 풀이: 모든 레이블의 길이의 합이 답입니다.
하지만 접미사 트리는 메모리 사용량이 꽤 크기 때문에, 백준 온라인 저지 11479에서 테스트하는 것은 권장하지 않습니다. 입력 크기는 100만인데 메모리 제한은 256 MB입니다…
접미사 배열
문제: $S$의 접미사 배열을 $O(m)$에 구하세요.
트라이 풀이: 트라이를 DFS 순회하되, 레이블이 사전 순으로 작은 것부터 큰 순서대로 방문합니다. 방문한 리프 노드의 순서가 곧 접미사 배열이 됩니다.
트리 풀이: 트라이 풀이와 같습니다.
참고로 이를 응용하여 수열과 쿼리 40을 풀 수 있습니다. 자세한 내용은 제 블로그에 따로 작성했습니다.
공통 접두사
문제: $S$를 $O(m \log m)$에 전처리한 후, $(i, j)$가 들어왔을 때 두 접미사 $S[i..m]$과 $S[j..m]$의 가장 긴 공통 접두사의 길이를 $O(\log m)$에 구하세요. (접미사 배열과 세그먼트 트리로도 충분히 풀 수 있지만, 접미사 트리에 익숙해지도록 하기 위해 가져왔습니다.)
트라이 풀이: $i$번째와 $j$번째 리프 노드의 LCA의 깊이가 답입니다.
트리 풀이: 숨은 노드는 LCA가 될 수 없습니다. 따라서 노드의 깊이를 “루트에서 그 노드까지 경로에 있는 모든 레이블의 길이의 합”으로 정의하고 똑같이 풀면 됩니다.
공통 부분문자열
문제: 길이의 합이 $M$인 문자열 $S_1, \cdots, S_k$가 주어졌을 때, $i$개 이상의 $S$에 등장하는 가장 긴 부분문자열의 길이를 모든 $i$에 대해 총합 $O(Mk)$에 구하세요. (따라서 가장 긴 공통 부분문자열도 $O(Mk)$에 알아낼 수 있습니다.) bitset으로 구현 가능하기 때문에 실제로 $k$의 영향은 작습니다.
트라이 풀이: 일반화된 접미사 트라이를 만들고, 각 서브트리마다 길이 $k$의 이진수를 저장합니다. 이 이진수의 $i$번째 비트는 $S_i$의 리프 노드가 있으면 1, 아니면 0입니다. 이는 간단한 트리 DP로 계산할 수 있습니다. 이제 $i$개 이상의 비트가 1인 가장 깊은 서브트리를 찾으면 됩니다.
트리 풀이: 노드의 깊이를 “루트에서 그 노드까지 경로에 있는 모든 레이블의 길이 합”으로 정의하고 똑같이 풀면 됩니다.
좋은 부분 문자열
문제: 백준 온라인 저지 13432를 $O(m)$에 해결하세요.
트라이 풀이: 각 서브트리마다 리프 노드 번호의 최솟값과 최댓값을 저장합니다. (리프 노드 번호의 최댓값과 최솟값의 차이)가 (루트 노드의 깊이)보다 크거나 같은 서브트리의 개수가 답입니다.
트리 풀이: 트라이에서 자식 노드가 하나면 (리프 노드 번호의 최댓값과 최솟값의 차이)는 유지되고 (루트 노드의 깊이)만 하나 늘어납니다. 이를 이용하여 트리의 각 레이블마다 몇 개의 숨은 노드가 조건을 만족하는지 $O(1)$에 계산할 수 있습니다.
그 외
그리고 다음 문제들은 저도 풀이를 모르지만, 접미사 트리로 해결할 수 있음이 알려져 있습니다.
- 위의 “공통 부분문자열” 문제를 $O(M)$에 풀 수 있습니다.
- 위의 “공통 접두사” 문제를 $O(m)$의 전처리 이후 $O(1)$에 풀 수 있습니다.
- 길이가 각각 $n$과 $m$인 문자열 $T$와 $S$가 주어졌을 때, $T[i..j]$가 $S$의 부분문자열인 가장 큰 $j$를 모든 $i$에 대해 총합 $O(n+m)$에 구할 수 있습니다. 이를 matching statistics라고 합니다.
- 모든 $i, j$에 대해, $S_i$의 접두사이면서 $S_j$의 접미사인 가장 긴 문자열의 길이를 총합 $O(M + k^2)$에 알아낼 수 있습니다.
- $P$를 $S$ 내에서 찾되, 모든 글자가 일치하는 것을 찾는 게 아니라 최대 $k$개의 글자가 일치하지 않는 것을 $O(mk)$에 찾을 수 있습니다.
예고편
지금까지 접미사 트리가 무엇이고, 어디에 사용할 수 있는지를 다뤘습니다. 하지만 이 모든 것은 접미사 트리를 정말로 $O(m)$에 만들었을 때에만 의미가 있습니다. 다음 글에서는 대표적인 접미사 트리 알고리즘인 Ukkonen의 알고리즘에 대해 다루겠습니다.
참고 문헌
Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge: Cambridge University Press. doi:10.1017/CBO9780511574931