Dot Algo∙ DS/알고리즘 개념

[알고리즘] 접미사 배열(Suffix Array)와 LCP 배열(Lognest Common Prefix Array) (Java)

루지 2022. 4. 7. 17:42

    접미사(Suffix)

    접미사(suffix)는 파생어를 만드는 접사로 단어 뒤에 붙어 새로운 단어가 되게 하는 말이다.  문자열 s의 i번째 접미사란, s 의 i번째 글자부터 마지막 글자까지 포함되는 부분문자열을 뜻한다.

     

    문자열 "alohomora"

    A[i] S[A[i]···]
    0 a l o h o m o r a
    1 l o h o m o r a
    2 o h o m o r a
    3 h o m o r a
    4 o m o r a
    5 m o r a
    6 o r a
    7 r a
    8 a

     

    접미사 배열(Suffix Array)

    문자열을 다룰 때 빼놓을 수 없는 자료 구조로 접미사 배열(Suffix Array)가 있다. 접미사 배열은 흔히 '문자열의 맥가이버 칼'이라고 불리며, 굉장히 다양한 문제를 푸는 데 쓸 수 있다.

     

    접미사 배열은 사실 아주 간단한 자료 구조로, 어떤 문자열 S의 모든 접미사를 사전순으로 정렬해 둔 것이다. 물론 이 말이 곧이 곧대로 접미사들을 문자열 배열에 저장하면 문자열 길이의 제곱에 비례하는 메모리가 필요하기 때문에, 대개 접미사 배열은 각 접미사의 시작 위치를 담는 정수 배열로 구현된다.

     

    문자열 "alohomora"

    "alohomora"의 접미사 배열 A[]와 각 위치에서 시작하는 접미사들을 보여준다. 사전순으로 정렬되어 있다.

     

    i A[i] S[A[i]···]
    0 8 a
    1 0 a l o h o m o r a
    2 3 h o m o r a
    3 1 l o h o m o r a
    4 5 m o r a
    5 2 o h o m o r a
    6 4 o m o r a
    7 6 o r a
    8 7 r a

     

    접미사 배열을 이용한 문자열 검색

    접미사 배열을 이용해 할 수 있는 대표적인 일로 문자열 검색이 있다. 접미사 배열을 이용한 문자열 검색은 짚더미 H가 바늘 N을 포함한다면 항상 N은 H의 어떤 접미사의 접두사라는 점을 이용한다.

    • H: "alohomora"에서 N: "homo"를 찾고 있다.
    • N: "homo"는 A[2] "homora"의 접두사이다.

     

    모든 부분 문자열에 대해 이 속성이 성립함을 알 수 있다. 이 속성을 이용하면 H의 접미사 배열을 이진 탐색해서 각 문자열이 출현하는 위치를 찾을 수 있다. 접미사 배열의 길이는 항상 |H|이므로 이진 탐색의 내부는 O(lg|H|)번 수행된다. 각 문자열 비교에 O(|N|) 시간이 걸리기 때문에 이 이진 탐색의 수행 시간은 O(|N|lg|H|)이 된다.

     

     

    접미사 배열 만들기 - 정렬 알고리즘

    접미사 배열을 만드는 가장 간단한 방법은 정렬 알고리즘을 사용하는 것이다. 문자열의 길이가 n일 때, [0, n-1] 범위의 정수를 모두 담은 정수 배열을 정렬하되, 두 정수를 비교할 때 해당 위치에서 시작하는 접미사들을 비교한다. 그러면 해당 코드는 두 원소의 비교에 상수 시간이 걸릴 때 O(nlgn)이 걸리고 최악의 경우 두 문자열 비교에 O(n)이 걸리게 되면 O(n^2lgn)이 된다. 

    • "aaaa···aaa" 같은 문자열은 모든 비교가 끝까지 이루어지기 때문에 아주 오랜 시간이 걸린다.
    /**
 * Suffix Array 정렬 알고리즘으로 생성하기
 * 값 비교 O(n)
 * 값 정렬 O(nlgn) 
 * 시간복잡도 O(n^2*lgn)
 */

public class SuffixArray_Sort {
   public static void main(String[] args) {
      String text = "alohomora";
      List<Integer> suffix = getSuffixArray(text);

      for(int i : suffix){
         System.out.println(i + " - " + text.substring(i));
      }
   }

   private static List<Integer> getSuffixArray(String text) {
      int n = text.length();
      // 접미사 배열이 될 반환 값
      List<Integer> perm = new ArrayList<>();
      for (int i = 0; i < n; i++) {
         perm.add(i);
      }
      Collections.sort(perm, Comparator.comparing(text::substring));
      return perm;
   }
}

     

    접미사 배열 만들기 - 멘버 마이어스 알고리즘

    정렬 알고리즘을 사용하기에는 너무 느려서 사용하기에는 무리가 있다. 접미사 배열을 생성하는 가장 빠른 알고리즘은 선형 시간 즉, O(n)에 접미사 배열을 만들 수 있지만 과정이 너무 복잡하다. 

     

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

    1. 처음에는 접미사의 첫 한글자만을 기준으로 정렬하고,
    2. 그 다음에는 접미사의 첫 네 글자를 기준으로 정렬한다.
    3. 이렇게 lgN번의 정렬을 하고 나면 원하는 접미사 배열을 얻게 된다.

     

    문자열 "mississipi"

    "mississipi"의 접미사들을 첫 한 글자, 두 글자, 네 글자, 여덟 글자를 보고 정렬한다. 

     

    첫 한 글자 기준 첫 두 글자 기준 첫 네 글자 기준 첫 여덟 글자 기준
    ississipi
    issipi
    ipi
    i    		 i i i
    ipi ipi ipi
    ississipi
    issipi    		 ississipi
    issipi    		 issipi
    ississipi
    mississipi mississipi mississipi mississipi
    pi pi pi pi
    ssissipi
    sissipi
    ssipi
    sipi    		 sissipi
    sipi    		 sipi sipi
    sissipi sissipi
    ssissipi
    ssipi    		 ssipi ssipi
    ssissipi ssissipi

     

    이렇게 여러 번 정렬하는데도 더 빠르게 동작하는 이유는 이전 정렬에서 얻은 정보를 이용해 두 문자열의 대소 비교를 O(1)에 할 수 있기 때문이다.

    • 첫 글자를 기준으로 접미사들을 정렬한 결과를 가지고 있다고 하자.
    • 각 접미사들을 첫 글자가 같은 것들끼리 그룹으로 묶고, 각 그룹마다 0부터 시작하는 번호를 매긴다. 맨 왼쪽 표는 첫 글자를 기준으로 문자열들을 어떻게 묶을 수 있는지 보여준다.
    • i로 시작하는 접미사들은 0번 그룹, m은 1번 그룹, p는 2번 그룹, s는 3번 그룹으로 묶이게 된다.

     

    이렇게 묶은 결과로 group[] 배열을 만든다. 

    • group[i] = S[i···]가 속한 그룹의 번호 

     

    접미사들을 맨 앞에서부터 순회하면서 각 접미사에 그룹 번호를 부여해주면 된다.

    1. 첫 접미사는 항상 0을 주고, 그 이후부터는 이전 접미사와 첫 글자가 같으면 이전 접미사의 그룹 번호를,
    2. 아니면 이전 접미사의 그룹 번호에 1을 더한 번호를 부여한다.

     

    첫 t글자를 기준으로 만든 group[]이 있으면 두 접미사 S[i···], S[j···] 중 첫 t글자를 기준으로 어느 쪽이 앞에 오는지 쉽게 알 수 있다. group[i]와 group[j] 중 어느 쪽이 더 작은지 비교해주면 되기 때문이다. 이것만 있으면 S[i···], S[j···] 중 첫 2t 글자를 기준으로 어느 쪽이 사전에서 앞에 오는지도 상수 시간에 판단할 수 있다.

    • S[i···], S[j···]가 주어질 때, 우선 첫 t글자를 비교한다. 만약 이들이 서로 다르다면 나머지는 볼 것도 없이 어느 쪽이 앞에 오는지 결정할 수 있다.
    • 만약 두 접미사가 같은 그룹에 속한다면 S[i+t···]와 S[j+t···]의 첫 t글자를 서로 비교하면 된다.

     

    시뮬레이션

    "banana"가 문자열이 단순해서 시뮬레이션을 돌리기 좋다. 멘버 마이어스 알고리즘으로 접미사 배열을 구해보자. 

     

    먼저, sa에 저장된 첫 글자로 그룹을 나눠준다. 첫 그룹은 text가 소문자로만 이루어져있다는 가정하에 text.charAt(i)-'a'값을 대입한다.

     

    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

     

    t=1

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

    • 만약 첫 글자가 같은 경우 (S[i...] == S[j...]), t를 더해 첫 S[i+t...], S[j+t...]글자에 해당하는 group 값을 비교해주면 된다. 예로, S[1] =1, S[2] =2 의 비교는 group[1] = 0 vs group[2] =13으로 해주면 된다.
    • 그리고나서 정렬된 sa을 순차대로 비교하여 next group을 재정렬한다. 이도 마찬가지로 i, j 글자가 같다면 i+t, j+t의 group 값을 비교해주면 된다. 이렇게 구한 next group은 다음 sa를 재정렬할 때 사용한다.
    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

     

    t=2

    다음은 i + 두 글자로 나눠진 그룹으로 다시 sa를 정렬한다. 과정은 위와 같다.

    • 예를 들어, 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] 값을 통해 정렬해주면 된다. 
    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

     

    t=4

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

     

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

     

    t = 8은 텍스트 길이보다 크므로 비교를 중단한다. 이와 같은 과정으로 접미사 배열 sa = [5 3 1 0 4 2]라는 값을 구할 수 있다. 이와 같은 비교 방식을 사용하면 첫 2t글자를 기준으로 해서 접미사들을 O(nlgn)시간에 정렬할 수 있다. 그러고 나면 다시 이들을 순회하면서 O(n)시간에 그룹을 지을 수 있다.

    /**
 * Suffix Array 멘버-마이어스 알고리즘으로 생성하기
 * while문 내부 시간복잡도 O(nlgn)
 * 배열 lgn번 정렬
 * 전체 시간복잡도 O(n*(lgn)^2)
 */

public class SuffixArray_Manber_Myers {
   public static void main(String[] args) {
		String text = "banana";
		List<Integer> suffix = getSuffixArray(text);

		for (int i : suffix) {
			System.out.println(i + " - " + text.substring(i));
		}
	}

	private static List<Integer> getSuffixArray(String text) {
		int n = text.length();
		int t = 1;

		// 접미사 배열이 될 반환 값 (이 동적 배열을 log(n)번 정렬)
		List<Integer> perm = new ArrayList<>();
		// group
		int[] group = new int[n + 1];
		for (int i = 0; i < n; i++) {
			perm.add(i);
			// text가 영어 소문자로만 이루어졌다고 가정
			group[i] = text.charAt(i) - 'a';
		}
		group[n] = -1;

		CompUsing2T compUsing2T = new CompUsing2T(n, t, group);
		while (t < n) {
			// group[]은 첫 t글자를 기준으로 계산해뒀다. 첫 2t글자를 기준으로 perm을 다시 정렬한다.
			Collections.sort(perm, compUsing2T.comparator);
			t *= 2;
			if (t >= n) break;

			int[] newGroup = new int[n + 1];
			newGroup[perm.get(0)] = 0;
			newGroup[n] = -1;

			for (int i = 1; i < n; i++) {
				if (compUsing2T.comparator.compare(perm.get(i - 1), perm.get(i)) < 0) {
					newGroup[perm.get(i)] = newGroup[perm.get(i - 1)] + 1;
				} else {
					newGroup[perm.get(i)] = newGroup[perm.get(i - 1)];
				}
			}
			group = newGroup;
			compUsing2T.changeValues(t, group);
		}
		return perm;
	}

	static class CompUsing2T {
		private int n;
		private int t;
		private int[] group;

		public CompUsing2T(int n, int t, int[] group) {
			this.n = n;
			this.t = t;
			this.group = Arrays.copyOf(group, group.length);
		}

		public void changeValues(int t, int[] group) {
			this.t = t;
			this.group = Arrays.copyOf(group, group.length);
		}

		private Comparator<Integer> comparator = new Comparator<>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				if (group[o1] != group[o2]) {
					return group[o1] - group[o2];
				}
				int left = o1 + t, right = o2 + t;
				if (o1 + t > n) {
					left = n;
				}
				if (o2 + t > n) {
					right = n;
				}
				return group[left] - group[right];
			}
		};
	}
}

     

    LCP 배열 (Lognest Common Prefix Array)

    LCP(Longest Common Prefix) 배열은 접미사 배열에서 이웃한 두 접미사 간의 최장 공통 접두사(Longest Common Prefix)의 길이를 저장한 배열이다. "mississipi"에 대한 접미사와 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's algorithm을 사용하면 O(n)에 계산할 수 있다.

    Kasai’s algorithm

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

     

    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]
    4 4 (i+1 = 4)    a na -
    5 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 역함수 배열을 초기화한다.
      • isa[i] = rank 접미사 시작위치 i가 사전순으로 몇 번째(rank)인지 저장한다.
    2. 가장 긴 접미사 isa[0]부터 길이가 짧아지는 순서대로 접미사를 탐색하여 lcp를 구한다.
      1. i와 사전순으로 인접해 있는 접미사를 구한다. j = sa.get(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 배열을 반환한다.
    static int[] getLCP(String text, List<Integer> sa){
    int n = sa.size();
    int[] lcp = new int[n-1];

    // sa의 역함수 배열 isa[sa[i]] = i
    int[] isa = new int[n];

    for(int i=0; i<n; i++) {
        isa[sa.get(i)] = i;
    }

    int k = 0;
    for(int i=0; i<n; i++) {
        int idx = isa[i];
        if(idx == n-1) continue;

        int j = sa.get(idx+1);
        while(i+k < n && j+k < n) {
            if(text.charAt(i+k) != text.charAt(j+k)) break;
            k++;
        }

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

     

    참고

    알고리즘 문제해결전략 2

    http://www.mi.fu-berlin.de/wiki/pub/ABI/RnaSeqP4/suffix-array.pdf