1. 접미사 배열
접미사 배열은 문자열 형태의 데이터가 갖는 모든 접미사를 사전 순 정렬한 것을 의미한다.
접미사 배열은 문자열 검색, 전문 검색 등에 활용하기 위해서 많이 쓰인다.
접미사 배열로 검색하면 아래와 같은 예시를 가장 많이 볼 수 있다. 이를 통해 간단히 이해해보자.
| 기존 배열(original array) | 접미사 배열(suffix array) |
| banana | a |
| anana | ana |
| nana | anana |
| ana | banana |
| na | na |
| a | nana |
이해하기 어렵지 않다. banana 라는 문자열의 모든 접미사는 자기 자신을 포함해, 뒤에서 부터 한 글자씩 잘라낸 부분이라고 보면 된다.
위의 표를 보면 좌측의 기존 접미사를 저장한 배열이 정렬 후 우측과 같이 정렬 상태가 됨을 알 수 있다.
이제 보니, 단순히 문자열 잘라서 정리한 것이다. 아니 그렇다면, 지금까지 포스팅했던 정렬 알고리즘을 사용해서 단순히 정렬하면 되는 문제 아닐까?
하지만 문제가 있다. 문자열 비교 시, 숫자와 달리 길이가 N인 문자열이라면 1회 비교에 최악의 경우 O(n)이 소요될 수 있다. 왜냐하면 문자열의 한 문자씩 비교해야 할 수 있기 때문이다. 가장 빠른 정렬 알고리즘을 사용하더라도 O(nlogn)의 수준이다.
따라서, 문자열 비교에 최대 O(n) 만큼 소요하고, 가장 빠른 정렬 알고리즘이 보통 O(nlogn)이므로 전체 정렬 시간복잡도가 O(n^2logn)이 될 수 있다.
위와 같은 경우보다 우리는 O(nlogn) 수준으로 접미사 배열을 구성할 수 있는 코드를 짜볼 것이다.
2. 단순히 구현하기
시간복잡도가 O(n^2 * logn)이나 걸릴 수 있지만 일단은 만들어보는 걸 우선으로 해보자.
아래의 코드를 통해 간단히 알아보자.
package com.test;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class SuffixArray {
public static void main(String[] args){
String text = "banana";
ArrayList<Integer> suffixes = makeSuffixArray(text); // 접미사 배열을 생성함
printSuffixes(text, suffixes); // 콘솔에 출력
}
// 접미사 배열을 만드는 메소드
public static ArrayList<Integer> makeSuffixArray(String text){
int len = text.length();
// 접미사 내역을 저장하는 배열을 생성, 길이는 현재 text의 길이만큼만 하면 모두 저장이 가능함함
// index값만 저장함으로써 메모리 낭비를 막을 수 있음
// String 값을 모두 저장 시, 글자가 크면 클수록 메모리 낭비가 심함(N^2 수준)
ArrayList<Integer> suffixes = new ArrayList<>();
for(int i=0; i < len; i++){
suffixes.add(i);
}
// Index만 String 값 기반으로 정렬하여 사용할 것임.
// Collections.sort를 사용하여 O(nlogn)의 시간복잡도를 갖는 정렬 방식 사용
// Comparator를 구현하여 index값에 해당하는 substring된 문자열을 비교함.
Comparator<Integer> comp = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
String a = text.substring(o1);
String b = text.substring(o2);
return a.compareTo(b);
}
};
Collections.sort(suffixes, comp);
return suffixes;
}
// 접미사 내역을 printing
public static void printSuffixes(String text, ArrayList<Integer> suffixes){
// 정렬된 Index 출력
for(int i : suffixes){
System.out.print(i + ", ");
}
System.out.println();
// 정렬된 Index를 가진 ArrayList를 기반으로 String을 SubString하여 출력
for(int i : suffixes){
System.out.print(text.substring(i) + ", ");
}
System.out.println();
}
}
/*
결과
5, 3, 1, 0, 4, 2,
a, ana, anana, banana, na, nana,
Process finished with exit code 0
*/
위에서 보이듯이, 접미사 배열에는 ArrayList<Integer> 형태로 생성하여 Index 값만 넣었고 그 값을 정렬하였다. 실제 문자열을 넣게 되면 메모리 낭비가 심하기 때문이다.
위와 같은 방식을 Naive algorithm for construction Suffix Array 라고 부른다.
시간복잡도 : O(n^2 * logn)
3. 효율적으로 구현하기(맨버-마이어스 알고리즘)
위에서 보면 Collections.sort() 를 사용하여 String을 기반으로 index 값들을 정렬한 것을 알 수 있다. 하지만 이렇게 한다고 하더라도 여전히 너무나 오랜 시간이 걸린다.
만약 문자열의 길이인 n = 1,000,000 이라고 가정한다면, O(n^2 * logn)에서 n^2 * logn 은 컴퓨터가 1초에 약 1억회의 연산을 할 수 있으므로 60,000초.. 즉 17시간 정도가 소요될 수 있다.(이 계산이 정확한지는 모르겠다.)
따라서, 시간을 효율적으로 사용하여 문자열 처리를 할 수 있는 알고리즘을 사용하여 구현한다.
아래의 내용은 O(n * logn * logn) 수준에서 동일한 처리를 할 수 있는 알고리즘을 설명한다. 단순히 n 하나가 logn이 되었다고 볼 수도 있지만 실제로 처리 속도 차이는 어마어마하다. 기존의 17시간 정도 소요되는 작업을 몇 초만에 작업을 완료할 수 있다.
① 알고리즘 아이디어 설명
문자열의 각 문자 하나 하나를 단일 문자열로 보고 정렬을 수행한다. 처음 0번째(index 기준)으로 정렬하고, 다음엔 0~1번째, 0~3번째, 0~7번째와 같이 2배로 길이를 늘리고 정렬 시 같은 순서라면 그룹으로 묶어가며 정렬을 수행한다.
즉, 정렬 시 2^i - 1번째 문자를 기준으로 수행한다.(0, 1, 3, 7, 15, 31..)
예를 들어, "banana"라는 문자는 아래와 같이 비교하여 정렬할 수 있다.
1) 0번째 index를 기준으로 정렬 시
| 인덱스 | 현재 접미사 내역 | 0번째 index 기준 Rank* | 정렬 후 접미사 내역 |
| 0 | banana | 1 | anana |
| 1 | anana | 0 | ana |
| 2 | nana | 13 | a |
| 3 | ana | 0 | banana |
| 4 | na | 13 | nana |
| 5 | a | 0 | na |
* Rank : 첫 번째 문자가 a, b, n이므로 character형으로 변환 시 각 문자에서 a를 빼주면 몇 번째 숫자인지 알 수 있음('a'는 97번째 아스키 코드이므로 'a'를 차감 시 0이며 n은 110번째 이므로 'a'를 차감 시 13이 됨)
2) 1번째 index를 기준으로 정렬 수행
위에서 정렬하였다면 0번째 문자 기준 같은 것들은 같은 그룹으로 묶는다. 그룹화 되어 묶으면 아래 내역과 같이 3개의 그룹으로 분할된다.
| 인덱스 | 현재 접미사 내역 | 1번째 index 기준 Rank | 정렬 후 접미사 내역 |
| 1 | anana | 13 | a |
| 3 | ana | 13 | anana |
| 5 | a | -1* | ana |
| 인덱스 | 현재 접미사 내역 | 1번째 index 기준 Rank | 정렬 후 접미사 내역 |
| 0 | banana | 0 | banana |
| 인덱스 | 현재 접미사 내역 | 1번째 index 기준 Rank | 정렬 후 접미사 내역 |
| 2 | nana | 0 | nana |
| 4 | na | 0 | na |
* Rank가 -1이라는 것은 문자열의 끝을 넘어가서 더 이상 Rank를 결정할 수 없는 경우를 의미함
3) 3번째 index를 기준으로 정렬 수행
위에서 정렬 후 1번째 문자 기준 같은 것들을 다시 그룹으로 묶는다. 그룹화 되면 아래와 같이 4개의 그룹으로 분할된다.
| 인덱스 | 현재 접미사 내역 | 3번째 index 기준 Rank | 정렬 후 접미사 내역 |
| 5 | a | -1 | a |
| 인덱스 | 현재 접미사 내역 | 3번째 index 기준 Rank | 정렬 후 접미사 내역 |
| 1 | anana | 13 | ana |
| 3 | ana | -1 | anana |
| 인덱스 | 현재 접미사 내역 | 3번째 index 기준 Rank | 정렬 후 접미사 내역 |
| 0 | banana | 0 | banana |
| 인덱스 | 현재 접미사 내역 | 3번째 index 기준 Rank | 정렬 후 접미사 내역 |
| 2 | nana | 0 | na |
| 4 | na | -1 | nana |
길게 쓰게 되었는데, 다음의 경우는 더 이상 쓸 필요가 없다. 모든 문자열이 각각의 그룹에 속하게 되어 더 이상 비교가 필요없기 때문이다.
위와 같이 index 비교할 위치를 2씩 곱해가며 수행하기에 전체 비교에 O(logn)이 소요되며, 정렬 알고리즘을 가장 빠른 O(nlogn)을 사용할 것이므로 전체 시간복잡도는 O(n * logn * logn)이 된다.
② 알고리즘 코드로 구현하기
아래 코드가 주석이 포함되어 좀 길어보일 수 있는데 찬찬히 보면 이해할 수 있다. printSuffixes는 변하지 않았고 makeSuffixArray 메소드에서만 좀 변화가 많이 있다.
package com.test;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class SuffixArrayAdvanced {
public static void main(String[] args){
String text = "banana";
ArrayList<Integer> suffixes = makeSuffixArray(text); // 접미사 배열을 생성함
printSuffixes(text, suffixes); // 콘솔에 출력
}
// 접미사 배열을 만드는 메소드
public static ArrayList<Integer> makeSuffixArray(String text){
// 이 값은 문자열의 0, 1, 3, 7번째를 비교하기 위해 사용함.
// 처음에는 0번째에서 시작한 뒤, t를 더해 1번째로 넘어갈 것임. 아래에서 t*2를 수행하여 이동하는 코드를 추가함
int t = 1;
int n = text.length();
// 접미사 내역을 저장하는 배열을 생성, 길이는 현재 text의 길이만큼만 하면 모두 저장이 가능함함
// index값만 저장함으로써 메모리 낭비를 막을 수 있음
// String 값을 모두 저장 시, 글자가 크면 클수록 메모리 낭비가 심함(N^2 수준)
ArrayList<Integer> suffixes = new ArrayList<>();
// group은 각 문자열을 잘라낸 후 해당 문자열이 속할 group을 지정하기 위해 사용
// 결국 1개씩 각각 모든 그룹에 속할 것이므로 group도 len 만큼 생성함
int[] group = new int[n];
for(int i=0; i < n; i++){
// 각 index 값을 array list에 넣는다.
suffixes.add(i);
// 각 index에 해당하는 문자열의 그룹을 초기에는 각 접미사의 첫 글자를 기준으로 설정
// 모두 소문자만 제공된다고 가정함
group[i] = text.charAt(i) - 'a';
}
// 비교할 위치를 지정하는 t의 값이 전체 문자열의 길이를 넘지 못해야 한다.
while(t < n){
// Comparator inner class에서 참조하기 위해서 finalGroup, finalT으로 복제
int[] finalGroup = group;
int finalT = t;
// Index만 String 값 기반으로 정렬하여 사용할 것임.
// Comparator를 구현하여 index값에 해당하는 substring된 문자열을 비교함.
Comparator<Integer> comp = new Comparator<Integer>() {
@Override
public int compare(Integer index1, Integer index2) {
// index1의 접미사와 index2의 접미사의 그룹이 다르다면
// 그룹 번호가 더 큰 것이 더 뒤의 문자임. 따라서 그 크기를 비교하여 반환
if(finalGroup[index1] != finalGroup[index2]){
return finalGroup[index1] - finalGroup[index2];
}
// 만약 두 index의 접미사가 그룹이 같다면
// 현재 위치의 문자로는 비교가 불가하므로 다음 비교할 문자의 group을 기준으로 비교함
// t를 더함으로써 전체 길이와 같거나 넘어가면 -1로 설정하여, 문자가 완료되었음을 표시한다.
int left = index1 + finalT >= n ? -1 : index1 + finalT;
int right = index2 + finalT >= n ? -1 : index2 + finalT;
return left - right;
}
};
// Collections.sort를 사용하여 O(nlogn)의 시간복잡도를 갖는 정렬 방식 사용
Collections.sort(suffixes, comp);
// 정렬을 진행한 뒤에는 현재 정렬된 상태의 내역들을 각 그룹으로 묶어줄 값을 저장해야함
int[] newGroup = new int[n];
// ArrayList의 제일 첫 번째에 있다는 것은 현재 비교된 문자를 기준으로 가장 앞에 있다는 의미이므로
// 0번 그룹으로 매칭
newGroup[suffixes.get(0)] = 0;
for(int i=1; i < n; i++){
// i-1번째의 접미사가 i번째의 접미사보다 더 그룹 번호가 크다면, i-1번째 그룹의 +1의 그룹으로 속하도록 함
if(group[suffixes.get(i-1)] < group[suffixes.get(i)]){
newGroup[suffixes.get(i)] = newGroup[suffixes.get(i-1)] + 1;
// 아니라면 같은 그룹으로 속하도록 함
} else {
newGroup[suffixes.get(i)] = newGroup[suffixes.get(i-1)];
}
}
group = newGroup; // 새로 지정된 그룹을 최신 그룹으로 지정함
t *= 2; // t값에 2를 곱함
}
return suffixes;
}
// 접미사 내역을 printing
public static void printSuffixes(String text, ArrayList<Integer> suffixes){
// 정렬된 Index 출력
for(int i : suffixes){
System.out.print(i + ", ");
}
System.out.println();
// 정렬된 Index를 가진 ArrayList를 기반으로 String을 SubString하여 출력
for(int i : suffixes){
System.out.print(text.substring(i) + ", ");
}
System.out.println();
}
}
4. 참고
참고 1) 왜 0, 1, 3, 7번째만 비교하나?
t의 값을 이용하여 0, 1, 3, 7.. 번째의 글자를 갖고 비교를 한다. 이 부분에서 왜 그게 확실히 정렬이 된다고 볼 수 있는가 하고 의심이 갈 수 있다.
이는 기본적으로 접미사를 활용하기 때문이다. 접미사의 성질 상, 위의 로직에서 최초에 각 첫 글자를 기준으로 모든 그룹을 나누기 때문에 모든 글자를 연속으로 모두 비교할 필요가 없어진다.
또한 현재 그룹에서 비교 시, Comparator 부분의 로직을 보면 현재 그룹이 같으면 바로 다음 문자의 그룹을 비교하는 작업을 한다. 이러한 작업이 반복되기 때문에 그 사이사이의 내역이 이미 검증되어 버린다.
참고 2) 더 효율적인 방법은 없을까?
위의 경우에는 시간복잡도를 O(n * logn * logn) 까지 줄일 수 있었다. 하지만 더 줄이는 건 불가능할까?
정렬 시 Radix 정렬을 사용하면 정렬에 들어가는 시간복잡도를 O(n)까지 줄일 수 있어서 전체 시간복잡도를 O(nlogn) 까지 줄일 수 있다.
추가로, 전체 복잡도를 O(n)에서 만들어낼 수 있는 알고리즘 또한 개발되었으나.. 너무나 복잡하며 실제로 그렇게 많이 통용되지는 않는다고 한다.
관련 내용은 여기서 참조할 수 있다. (아이오와 주립 대학교 리포트)
참고 3) Suffix Tree라는 것도 있던데?
접미사를 저장하는 방식은 위와 같은 접미사 배열만이 아닌, Tree 형식으로 구성하는 것 또한 가능하다.
이는 Trie(트라이)를 변형해서 사용하는 방식으로, 공간 효율성은 접미사 배열 방식에 비해 떨어지지만 속도 측면에서는 더욱 우수하다고 알려져 있다.
관련 내용은 추후 포스팅 후 링크를 달아놓겠습니다.
접미사 배열 부분은 내용이 많이 어려워서 이해하는데 시간이 많이 걸렸습니다. 자바로 정리된 것도 없어서 제가 C++ 코드를 자바로 옮겨서 한 번 구현해보았습니다.
오류가 있을 수 있으므로 참고하시고, 있는 경우 댓글 달아주시면 수정하겠습니다.
긴 글 읽어주셔서 감사합니다.
'자바 프로그래밍 > 자료구조(Data Structure)' 카테고리의 다른 글
| 자료구조 - 이분 그래프(Bipartite Graph) (2) | 2021.02.25 |
|---|---|
| 자료구조 - 접미사 트리(Suffix Tree) (0) | 2021.01.02 |
| 자료구조 - 정렬 8 (Topological) (0) | 2020.11.16 |
| 자료구조 - 정렬 7 (Bucket) (0) | 2020.11.14 |
| 자료구조 - 정렬 6 (Radix) (0) | 2020.11.14 |
