접미사 배열 (Suffix Array)

참고
주어진 한개의 문자열에서 어떤 정보를 뽑아내야 할 때 사용할수 있는 가장 강력한 알고리즘이다
prefix에 관한 정보는 KMP 알고리즘이나 Z 알고리즘으로 대충 해결되는 경우가 많지만, 일반적인 부분문자열에 관한 것은 접미사 배열이 필요한 경우가 많다.
어떤 부분 문자열은 어떤 접미사의 접두사이기 때문에, 모든 접미사를 효율적으로 잘 관리해서 접두사에 대한 정보를 잘 뽑을수 있게 하면, 부분 문자열에 대한 정보를 잘 처리할수 있다
모든 접미사를 뽑았을다고 치면, 사실 이렇게 여러개의 문자열을 처리할수 있는 가장 강력한 도구는 트라이 (Trie)이다. 하지만, 진짜로 모든 접미사로 트라이를 만들면, 메모리가 O(n^2)이 되어서 터진다.
이것을 좀더 개선해서 효율적으로 O(n)에 자료를 저장하게 만든 suffix tree 라는 구조가 있다고 한다. 그리고 어떻게어떻게 해서 이것을 O(n) 시간에 구축하는 알고리즘도 있다고 한다.
하지만.. 이것보다 더 간단한 구조인, 접미사 배열과 lcp 배열을 사용해서 문제를 풀수도 있다.
- 접미사 배열은 각 접미사들이 정렬되었을때 몇번째에 오는지 하는 랭크들만 저장해놓은 구조이다. lcp배열은 접미사 배열에서 인접한 접미사들끼리의 LCP를 저장해놓은 구조이다.
- 따라서 접미사 배열과 lcp 배열은 전부 길이 n까지 정수 배열에 불과하다. 공간복잡도가 suffx tree와 똑같은 O(n)이지만 상수가 훨씬 작다.
- 접미사 배열과 lcp 배열을 구축하는 것은 일반적으로는 O(nlogn)의 시간복잡도가 걸리지만, suffix tree에 비하면 알고리즘이 훨씬 간단하다.
  - 실제로는 O(n)에 구축하는 알고리즘이 많이 있다.
접미사 배열과 lcp 배열만 있으면 suffix tree로 할수 있는 태스크를 거의 다 (전부라고 어디서 봤던거 같기도 한데 가물가물..) 할수 있다고 한다.
- 예를 들면 어떤 두 부분문자열의 LCP를 찾는 쿼리를 해결하는 문제..는 suffix tree에서의 LCA 쿼리를 처리하는 것으로 쿼리당 O(1)이 걸리는데, 접미사배열과 LCP배열이 있다면, LCP배열에서 RMQ쿼리를 처리하는 문제가 되어서 역시 쿼리당 O(1)이 걸린다.
- 두번 이상 등장하는 가장 긴 부분문자열은 suffix tree에서 depth가 가장 큰 non-leaf 노드를 찾는 방식으로 풀수 있다. 접미사 배열에서는 LCP 배열의 최댓값을 찾는 것으로 풀수있다.

사실 suffix tree에서 dfs를 하면 접미사 배열을 O(n)에 구할수 있다. 또 접미사 배열을 suffix tree로 O(n)에 변환하는 알고리즘도 있다

알고리즘

접미사 배열

위키피디에아 따르면, O(n)에 구축하는 알고리즘이 다양하게 있다고 한다.
- Prefix doubling, Recursive algorithms, Induced copying algorithms 이렇게 크게 세가지 분류가 있다고 한다
- 심지어는 2016년에는 in-place로 만드는 알고리즘도 나왔다고 한다
하지만, 인터넷에서 이런 O(n)알고리즘에 대한 강의 자료를 찾기는 쉽지 않다. 한국어로 된 자료는 전혀 찾을수 없었다.
보통 널리 알려진 알고리즘은 O(nlog^2n)의 Manber-Myers 알고리즘이다. 카운팅소트로 바꾸면 O(nlogn)까지 시간복잡도를 줄일수 있다.

Manber-Myers 알고리즘

참고자료: plzrun
맨버-마이어스 알고리즘이란 이름이 그렇게 유명하지는 않다. 그냥 서픽스 어레이 알고리즘이라고 퉁치고 설명하는 곳들도 많다.
정렬에 일반 O(nlogn) 정렬 알고리즘을 사용하면 전체 시간 복잡도가 O(nlog^2n)이 된다. O(n)짜리 카운팅 소트로 대체하면 O(nlogn)이 된다.

O(nlog^2n) 코드는 간단하다. 내가 작성한 것은 대충 이런식.

def suffix_array(s):
    n = len(s)
    sa = list(range(n))
    g = [ord(x) for x in s] + [0] * n
    d = 1
    while True:
        sa.sort(key=lambda i: (g[i], g[i + d]))
        t = [0] * (n + n)
        t[sa[0]] = 1
        for prev, cur in itertools.pairwise(sa):
            t[cur] = t[prev] + (g[cur] > g[prev] or g[cur + d] > g[prev + d])
        if t[sa[-1]] == n:
            break
        g = t
        d *= 2
    return sa

비교할때 배열 범위가 넘어가는 것을 처리하는 것이 귀찮아서, 그냥 배열 크기를 2배로 늘려 잡았다.
루프를 d가 len(s)보다 커질때까지 돌리지 않아도, 모든 접미사가 다른 번호를 갖게 되었는지를 t[sa[-1]] == n으로 체크해서 종료시킬수 있다.

O(nlogn) 코드는 작성 안해봤다. 아래 말할 SAIS코드를 쓰기로 결정했기 때문에..
python에서 내장 sort가 엄청 빠른것을 생각하면, 카운팅소트로 바꿔도 기대보다는 그닥 성능 향상이 별로 크지 않을거 같다는 추측을 해본다

SA-IS 알고리즘

Induced Sorting 을 이용하는 알고리즘이다.
위키피디아에 따르면 코드가 100줄도 안될정도로 간단하지만, 성능은 굉장히 좋다고 한다.
코드 구현체는 여기저기서 찾을수 있다. PyRival에도 있고, Library checker에서 코드들을 뒤져봐도 몇몇 구현체를 찾을수 있다. 주석이 달린 버전도 있다
- 코드 자체는 정말로 길지 않다. PS에서 충분히 사용할수 있는 크기이다.
문제는.. 알고리즘에 대해서 풀어서 설명을 해놓은 것을 찾기가 너무 힘들다.
대충 여기저기서 본것들을 종합하면, suffix들을 l-type과 s-type으로 분류하고, 그것들을 이용해서 문자열을 여러개의 LMS라 불리는 부분문자열로 나눈다. 그리고 각각의 LMS를 (재귀적으로) 정렬하고, 전체를 정렬한다..는 방식인거 같다
근데 이렇게 하면 왜 되는지..에 관한 것들을 알기 위해서는 그냥 논문을 찾아보는 방법밖에 없을것 같다..
설명을 찾았다!! 그것도 무려 한국어. https://infossm.github.io/blog/2021/11/21/linear-suffix-array/ 를 참고하자. 이거 진짜 귀한 자료다.. 영어로도 이런 설명 찾기 어렵다..

DC3 알고리즘

또다른 O(n)알고리즘이다. 위키피디아에서 3가지로 분류했던것중 Recursive algorithms 에 해당되는 알고리즘.
Skew 알고리즘이라고도 ㅂ른다
이거는 그나마 좀 뒤져보면 설명해놓은 자료가 좀 있긴 하다. 자세히 읽지는 않았지만, 시작위치가 3의 배수가 아닌 서픽스들을 정렬하고 나면, 그것을 이용해서 O(n)에 3의 배수 서픽스를 정렬하고 머지할수 있다고 한다. 3의 배수가 아닌 서픽스들을 정렬하는 것을 재귀적으로 처리한다면 T(n) = T(2n/3)+O(n) 형태로 최종적으로 O(n)이 된다고 한다.
하지만, 이쪽은 굴러다니는 코드를 찾기가 쉽지 않다; 실제로 SA-IS나 맨버-마이어스랑 비교해서 속도가 어떤지는 확인 못해봄.
이것도 https://infossm.github.io/blog/2021/11/21/linear-suffix-array/에 설명되어있다!!

LCP 배열

Kasai's algoritm은 Suffix array 에서 LCP array를 O(n)에 구한다.
알고리즘 자체는 매우 간단하다. 정당성은 조금 생각해봐야 할수도 있다.
https://cp-algorithms.com/string/suffix-array.html#longest-common-prefix-of-two-substrings-without-additional-memory 참고

목차

접미사 배열 (Suffix Array)

알고리즘

접미사 배열

Manber-Myers 알고리즘

SA-IS 알고리즘

DC3 알고리즘

LCP 배열