멘버 마이어스 알고리즘과 Kasai 알고리즘

문자열을 다룰 때 빼놓을 수 없는 자료 구조인 접미사 배열(Suffix Array)은 다양한 문제를 푸는데 사용 가능하다.

이 접미사 배열은 어떤 문자열 S의 모든 접미사를 사전순으로 정렬해둔 것으로 기본적으로 문자열 길이의 제곱에 비례하는 메모리가 필요하기 때문에 보통 각 접미사의 시작 위치를 담는 정수 배열로 구현된다.

 

예를 들어, 문자열 S = banana의 접미사 배열은 다음과 같다.

Suffix	index
a	6
ana	4
anana	2
banana	1
na	5
nana	3

 

접미사 배열은 위에서 말했듯 각 접미사의 시작 위치를 담는 정수 배열로 구현되며, 이를 사용해 문자열 검색에 사용할 수 있다.

 

접미사 배열을 정렬 알고리즘으로 구현할 경우 구현은 매우 쉽다. 그러나 시간 복잡도가 O(nLogn)이 걸리고 최악의 경우 O(n^2Logn)이 걸린다. 이렇듯 정렬 알고리즘은 구현은 쉬우나 너무 느리기 때문에 다른 알고리즘을 써야한다. 가장 빠른 알고리즘을 사용할 경우 시간 복잡도는 O(n)으로 접미사 배열을 만들 수 있으나 이 방법은 구현이 매우 복잡하다. 그래서 나온 것이 멘버 마이어스 알고리즘이다.

 

 

---

멘버 마이어스 알고리즘

접미사 배열에서 처음 제안한 논문에서 제시한 알고리즘으로, 정렬하는 문자열들이 한 문자열의 접미사라는 점을 이용해 수행시간을 낮춘다. 이 알고리즘은 접미사들의 목록을 여러 번 정렬하는데, 매번 그 기준을 바꾼다.

1. 접미사 첫 한 글자만을 기준으로 정렬한다.
2. 이후 접미사의 첫 네 글자를 기준으로 정렬한다.
3. 이렇게 LogN번의 정렬 끝에 원하는 접미사 배열을 얻는다.

멘버 마이어스 알고리즘은 한 글자, 두 글자, 네 글자, 여덟 글자, ... 를 보고 정렬한다.

 

 

S = banana를 예로 멘버 마이어스 알고리즘을 시뮬레이션 해보자.

i	sa	S[sa[i]...]	group[sa[i]]
0	0	banana	1
1	1	anana	0
2	2	nana	13
3	3	ana	0
4	4	na	13
5	5	a	0

 

먼저, sa에 저장된 첫 글자로 그룹을 나눈다.

첫 그룹은 text가 소문자로만 이루어져있다는 가정하에 text[index] - 'a'를 대입한다.

 

 

t = 1

i	sa	S[sa[i]...]	next group[sa[i]]
0	5	a	0
1	1	anana	1
2	3	ana	1
3	0	banana	2
4	2	nana	3
5	4	na	3

 

index + 첫 글자로 나뉜 그룹으로 sa를 정렬한다. 글자 비교는 직접 문자를 비교하는 것이 아니라 group에 저장된 수로 비교한다.

• 만약 첫 글자가 같은 경우 (S[i..] == S[j..]), t를 더해 첫 S[i+t..], S[j+t..] 글자에 해당하는 group 값을 비교해주면 된다. 예를들어, S[1] = 1, S[2] = 2의 비교는 group[1] = 0, group[2] = 13으로 해주면 된다.
• 이후 정렬된 sa를 순차대로 비교하여 next group을 재정렬한다. 이것도 마찬가지로 i, j 글자가 같다면 i + t, j + t의 group 값을 비교해준다. 이렇게 구한 next group은 다음 sa를 재정렬할 때 사용한다.

 

 

t = 2

i	sa	S[sa[i]...]	next group[sa[i]]
0	5	a	0
1	3	ana	1
2	1	anana	2
3	0	banana	3
4	4	na	4
5	2	nana	5

 

다음은 i + 두 글자로 나뉜 그룹으로 다시 sa를 정렬한다. 과정은 t = 1에서 한 것과 동일하다.

• 예를 들어, 3번과 1번의 그룹은 둘다 group[3] = 1, group[1]이 같기 때문에 group[5] = 0, group[3] = 1로 비교해야한다. group[3]이 더 크므로 3, 1번 순으로 정렬된다.
• next group 재정렬 또한 마찬가지로, sa[ 5 3 1 0 4 2]값을 통해 정렬한다.

 

 

t = 4

i	sa	S[sa[i]...]
0	5	a
1	3	ana
2	1	anana
3	0	banana
4	4	na
5	2	nana

 

다음은 i + 네 글자로 나눠진 그룹으로 다시 sa를 정렬한다.

이 다음인 t = 8의 경우, 주어진 text의 길이보다 크게 되므로 비교를 중단한다. 이와 같은 과정으로 접미사 배열 sa = [5 3 1 0 4 2]라는 값을 구할 수 있다.

 

이 비교 방식을 사용해 첫 2t글자를 기준으로 접미사들을 O(nLogn) 시간에 정렬할 수 있다.

이후 다시 이들을 순회하며 O(n) 시간에 그룹을 지을 수 있다.

 

fun getSuffixArray(input: String): ArrayList<Int> {
    val n = input.length
    var t = 1
    val perm = ArrayList<Int>()
    var group = IntArray(n + 1)

    for (i in 0 until n) {
        perm += i
        group[i] = input[i] - 'a'
    }

    group[n] = -1

    val compareUsing2T = CompareUsing2T(n, t, group)
    while (t < n) {
        Collections.sort(perm, compareUsing2T.comparator())
        t *= 2
        if (t >= n) break

        val newGroup = IntArray(n + 1).also {
            it[perm[0]] = 0
            it[n] = -1
        }

        for (i in 1 until n) {
            if (compareUsing2T.comparator().compare(perm[i - 1], perm[i]) < 0) newGroup[perm[i]] = newGroup[perm[i - 1]] + 1
            else newGroup[perm[i]] = newGroup[perm[i - 1]]
        }

        group = newGroup
        compareUsing2T.changeValues(t, group)
    }

    return perm
}

class CompareUsing2T(private val n: Int, private var t: Int, private var group: IntArray) {
    fun changeValues(t: Int, group: IntArray) {
        this.t = t
        this.group = group.copyOf(group.size)
    }

    fun comparator() = Comparator<Int> { o1, o2 ->
        if (group[o1] != group[o2]) return@Comparator group[o1] - group[o2]

        var left = o1 + t
        var right = o2 + t

        if (o1 + t > n) left = n
        if (o2 + t > n) right = n

        group[left] - group[right]
    }
}

 

 

---

LCP 배열 (Lognest Common Prefix Array)

LCP배열은 접미사 배열에서 이웃한 두 접미사 간의 최장 공통 접두사의 길이를 저장한 배열이다.

• sa[i]: 사전순으로 i번째에 위치하는 접미사의 시작 위치를 저장한다.
  • ex) sa[0] = 5, 사전순 0번째로 위치하는 접미사(a) 시작위치는 5이다.
• isa[i]: sa[i] 배열의 역함수 (isa[sa[i]] = i)로 초기화하여, 접미사 시작위치 i가 사전순으로 몇 번째인지 저장한다.
  • ex) isa[5] = 0, 5번부터 시작하는 접미사의 사전순은 0번째이다.

i	sa	S[sa[i]...]	isa[sa[i]]
0	5	a	0
1	3	ana	1
2	1	anana	2
3	0	banana	3
4	4	na	4
5	2	nana	5

 

접미사 배열을 무작위로 구하면 시간복잡도는 O(n^2)이지만, 접미사 배열 성질을 이용한 Kasai 알고리즘을 사용하면 O(n)에 계산 가능하다.

 

 

---

Kasai 알고리즘

Kasai 알고리즘은 접미사 배열이 사전순으로 정렬되어 있다는 특성을 이용한 알고리즘이다. 이 알고리즘은 가장 긴 접미사(원본 문자열)부터 길이가 짧아지는 순서대로 접미사를 탐색하며 최장공통접두사의 길이를 구한다.

 

i번째 접미사의 LCP 값이 k일때, i + 1번째 접미사의 LCP 값은 최소 k - 1일 것이다. 그 이유는 문자의 상대적인 순서가 동일하게 유지되기 때문이다. 두 접미사에서 첫 번째 문자를 삭제하면 최소 k문자가 일치한다는 것을 알 수 있다.

 

예를 들어, 다음과 같이 i번째 접미사와 j번째 접미사가 사전순으로는 1, 2번째로 연속해 있을 때, j번째 접미사 3을 구했다고 하자.

i	sa[i]	S[sa[i]..]	lcp[i]
1	i (= 3)	ana	-
2	j (= 1)	anana	3

 

 

각 접미사의 첫 글자를 지우면 i + 1번째 접미사와 j + 1번째 접미사가 되고 LCP의 길이는 최소 2(=3 - 1)이 된다. 둘 사이에 있는 접미사에 따라 2 이상이 될 수도 있으므로 그 경우 LCP의 길이를 갱신하면 된다.

i	sa[i]	S[sa[i]..]	lcp[i]
1	4 (i + 1 = 4)	a na	-
2	2 (j + 1 = 2)	a nana	2

 

위와 같은 방식으로 sa 역함수로 초기화한 isa 배열을 이용하여 이웃한 두 접미사 간의 최장 공통 접두사(LCP)의 길이를 구할 수 있다.

 

• idx = isa[i] = 접미사 시작위치 i가 사전순으로 몇번째 인지 구한다.
  • 만약 isa[i] = n - 1이라면 사전에서 가장 마지막에 위치하므로 비교하지 않고 넘긴다.
• i = 3일때, 3번째부터 시작하는 접미사와 j = 1번째부터 시작하는 접미사와 비교한다.
  • idx = isa[3] = 1, j = sa[idx + 1] = sa[2] = 1
  • i = 3 vs j = 1
  • ana vs anana
  • ana가 일치하므로 k = 3
• i = 4일때, 4번째부터 시작하는 접미사와 j = 2번째부터 시작하는 접미사와 비교한다.
  • idx = isa[4] = 4, j = sa[idx + 1] = sa[5] = 2
  • i = 4 vs j = 2
  • na vs nana
  • 3번째 접미사 lcp 값이 3이기에 4번째 접미사 lcp 값은 최소 2여야한다.
  • na가 일치하므로 k = 2

i	isa[i] = idx	j = sa[idx + 1]	i vs j	lcp[idx]
0	3	4	banana vs na	0
1	2	0	anana vs banana	0
2	5	-	nana vs -	-
3	1	1	ana vs anana	3
4	4	2	na vs nana	2
5	0	3	a vs ana	1

 

이는 sa = [5 3 1 0 4 2] 접미사 배열을 참고하여 각 이웃한 접미사 배열을 비교한 것이다. 이와 같이하면 문자열 "banana"의 최장 공통 접두사 길이를 저장한 lcp 배열 [1 3 0 0 2]를 구할 수 있다.

 

1. 접미사 배열 sa로 isa 역함수 배열을 초기화한다.
   1. isa[i] = rank 접미사 시작위치 i가 사전순으로 몇 번째 rank인지 저장한다.
2. 가장 긴 접미사 isa[0]부터 길이가 짧아지는 순서대로 접미사를 탐색하여 lcp를 구한다.
   1. i와 사전순으로 인접한 접미사를 구한다. j = sa[isa[i] + 1]
   2. i부터 시작하는 접미사 vs j부터 시작하는 접미사를 비교하여 lcp를 구한다. while문 ~ lcp[idx] = k
3. k가 0보다 클 경우 k - 1로 줄여준다. (다음 접미사의 최소 길이 (k - 1)부터 탐색하기 위해) if (k >0) k--
4. 모든 접미사를 비교한 후 lcp 배열을 반환한다.

fun getLCPArray(input: String, sa: ArrayList<Int>): IntArray {
    val n = sa.size
    val lcp = IntArray(n - 1)
    val isa = IntArray(n)

    for (i in 0 until n) {
        isa[sa[i]] = i
    }

    var k = 0
    for (i in 0 until n) {
        val idx = isa[i]
        if (idx == n - 1) continue

        val j = sa[idx + 1]
        while (i + k < n && j + k < n) {
            if (input[i + k] != input[j + k]) break
            k++
        }

        lcp[idx] = k
        if (k > 0) k--
    }

    return lcp
}