ps:접미사_배열
접미사 배열 (Suffix Array)
- 참고
- 주어진 한개의 문자열에서 어떤 정보를 뽑아내야 할 때 사용할수 있는 가장 강력한 알고리즘이다
- 어떤 부분 문자열은 어떤 접미사의 접두사이기 때문에, 모든 접미사를 효율적으로 잘 관리해서 접두사에 대한 정보를 잘 뽑을수 있게 하면, 부분 문자열에 대한 정보를 잘 처리할수 있다
- 모든 접미사를 뽑았을다고 치면, 사실 이렇게 여러개의 문자열을 처리할수 있는 가장 강력한 도구는 트라이 (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줄도 안될정도로 간단하지만, 성능은 굉장히 좋다고 한다.
-
- 코드 자체는 정말로 길지 않다. 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나 맨버-마이어스랑 비교해서 속도가 어떤지는 확인 못해봄.
LCP 배열
- Kasai's algoritm은 Suffix array 에서 LCP array를 O(n)에 구한다.
- 알고리즘 자체는 매우 간단하다. 정당성은 조금 생각해봐야 할수도 있다.
ps/접미사_배열.txt · 마지막으로 수정됨: 2023/01/11 15:54 저자 teferi
토론