Suffix Array란
Suffix Array란 모든 접미사로 이루어진 배열을 의미한다. 모든 접미사로 이루어진 배열이라고 하면 잘 이해가 안될 수가 있는데, 여기서 접미사는 특정 문자열에서 끝에 붙는 모든 문자열의 경우의 수라고 할 수 있다. 예를 들면 banana라고 하는 문자열에서는 접미사는 a, na, ana, nana, anana, banana 6가지 경우가 존재한다. 이것들을 사전 순으로 정렬한 것이 Suffix Array라고 부르는 것이다.
SuffixArray를 문자열 간의 단순 비교하는 방식으로 정렬을 하려고 한다면 비교를 위해서 문자열을 담는 과정에서만 O(N^2)이 걸리고 sorting은 O(logN)만큼 걸리므로 총 O(N^2logN) 만큼 걸린다. 때문에 조금 더 효율적인 알고리즘을 필요로 한다.
자 그럼 여기서 SA를 구하는 데에는 O(Nlog^2N)로 개선 할 수 있는 방법이 있다. 그 방법에 대해서 이 글에서 다루고자한다. 일단 앞에 사용했던 예시를 사용해보면 banana에는 6개의 접미사가 존재한다.
처음에는 왼쪽 배열처럼 정렬되어 있지 않은 배열을 이걸 사전 순으로 정렬한 배열은 오른쪽과 같다. 그럼 이걸 어떻게 하면 정렬할 수 있을까
초기에는 첫단어만을 가지고 그룹으로 만든다. 그룹은 사전 순으로 index 값을 가지는데 첫단어가 같다면 같은 index값을 갖도록 한다. 그 후에는 자기 자신을 1칸 뒤에 있는 단어까지 비교하면서 같다면 같은 그룹에 다르다면 다른 그룹에 저장하는 방식을 선택한다. 비교하는 단어의 수를 2배 씩 늘려가며 이 방식을 반복한다.
위와 같은 방식으로 정렬의 과정이 이루어지고 여기서 모든 접미사가 정렬이 되었다면 정렬을 종료한다. 즉 그룹의 개수가 접미사의 개수와 같아지면 이 과정을 종료하게된다. 여기까지만 들으면 도대체 어떻게 정렬하는 개수를 2배씩 늘려서 정렬한다는거야? 라는 생각이 들 수 있다.
여기서부터가 핵심적인 부분이다. 바로 여기를 이해하는 것이 여기서 가장 핵심적인 부분이라고 할 수 있다. 지금 위의 그림처럼 각각의 단계 별로 비교를 할 때, 첫 번째 단계에서는 자기자신 즉 첫번째 글자만을 가지고 그룹을 나누었다. 이후에 자신과 자기 뒤의 1칸만큼 떨어진 문자까지 포함하여 다른 suffix들과 비교한다. 여기서 우리는 결과물로써 새로운 그룹 집합을 얻을 수 있는데, 이것은 각 suffix에 대해서 앞에서 2칸까지의 문자들을 기준으로 그룹을 나눈 것이다. 이 다음에는 4칸만큼 비교를 할 것이다. 여기서 ana와 anana를 비교하는 과정을 살펴보자
ana와 anana는 현재 둘 다 1번 그룹에 속해 있다. 여기서 4칸만큼 비교를 한다고 한다면 우리는 단순하게 2개의 그룹만을 비교하면 된다. 바로 자기자신의 그룹과 자기자신의 index에서 2칸 만큼 떨어진 index 2가지이다. 왜냐, 이미 an과 an을 비교하고 그룹으로 나누어 놨고 aX와 an은 그룹으로 비교를 해놨기 때문이다. 때문에 2가지의 값을 비교하면 총 4개의 문자를 비교할 수 있다.
이 과정을 반복하면 모든 접미사들을 정렬할 수 있다는 사실을 알 수 있다. 그리고 2배씩 증가하면서 확인하기 때문에 O(NlogN)에 가능하다는 사실을 알 수 있다.
자 우리는 여기서는 suffix Array를 O(Nlog^2N)에 구할 수 있었다. 하지만 suffix Array자체는 아무런 의미가 없다. 그럼 우리는 suffix Array의 의미가 되어줄 LCP배열을 만나러 가보자
LCP 배열이란
LCP 배열은 suffix Array를 만든 목적이라고 할 수 있다. longest common prefix라는 의미로 이름 그대로 가장 긴 공통 접두사를 구하는 배열이라고 할 수 있다. 여기서 우리는 이런 의문이 들 수 있다. 왜 가장 긴 공통 접두사를 구함? 아무런 의미가 없잖아. 의미가 있다! 모든 접미사들의 모든 접두사를 찾으면 모든 부분 문자열을 찾을 수 있게 된다. 간단하게 생각 해보면 특정 접미사의 모든 접두사는 그 접미사의 첫 글자로 시작하는 모든 접두사를 찾을 수 있게 된다. 그럼 모든 접미사에서 모든 접두사를 찾으면 모든 부분 문자열을 찾을 수 있게 되는 것이다.
그럼 우리는 여기서 가장 긴 공통 접두사를 찾는다면, 여기서 가장 긴 공통 문자열을 찾을 수 있게 되는 것이다. 그럼 여기서 공통 접두사를 도대체 어떻게 찾는다는 것일까? 여기서 우리가 탐색한 방식을 떠올리면 된다. 우리는 기본적으로 사전 순으로 정렬했다. 사전 순으로 정렬했다는 것은 접두사가 같은 접미사들은 SA상에서 붙어있다는 사실이 보장된다는 것이다. 그렇기 때문에 사전 순으로 정렬했을 때 서로 인접해 있는 접미사들끼리만 비교하면 된다.
비교하는 데에도 중요한 문제가 있다. 그냥 단순하게 인접한 문자열을 모두 비교해버리면 O(N^2)에 LCP 배열을 찾을 수 있다. 하지만 LCP 배열을 O(N)에 구하는 방법이 있다. 우리의 친구 banana와 함께 확인해보자
ana
anana
LCP배열 값 = 3
na
nana
LCP배열 값 = 2
여기서 우리는 1가지 사실을 생각해볼 수 있는데 만약 어떤 suffix의 LCP배열의 값이 x라고 한다면 앞에서 1글자를 제외한 suffix, 즉 문자열 상에서 다음 index에 들어가는 suffix의 LCP배열은 최소 x-1을 보장한다. 때문에 그 다음 index부터 suffix가 같음을 찾으면 된다. 그렇기 때문에 상수 시간안에 LCP배열을 찾을 수 있다.
LCP배열의 활용
LCP배열은 단순히 가장 긴 문자열을 찾는데에 있지 않다. 기본적으로 LCP를 구했다는 사실은 우리가 중복되는 문자열을 모두 찾았다고 할 수 있다. 가장 긴 문자열의 길이를 구했기 때문에 그보다 짧은 접두사들은 모두 중복된다는 사실을 이용하면 모든 부분 문자열을 구할 수 있는데, 우리는 이를 이용하여 모든 중복되는 문자열의 개수를 알 수 있다. 이를 이용하면 우리는 다양한 값을 구할 수 있다. 왜냐하면 우리는 중복되는 문자열의 개수를 알고 있고 모든 부분 문자열의 개수를 둘다 알고 있으므로, 중복만을 제거한다면 모든 부분 문자열의 종류, 중복을 두 번 제거 한다면 중복되지 않는 부분 문자열의 개수 등, LCP배열을 활용하면 문자열의 다양한 값을 구할 수 있게된다.
