2-12. 자료구조: Suffix Array (접미사 배열)

1. 접미사 배열(Suffix Array)의 개념과 배경

접미사 배열(Suffix Array)은 문자열 처리 분야에서 매우 강력하게 사용되는 자료구조 중 하나입니다. 문자열 내에서 특정 패턴을 빠르게 검색하고, 문자열 간의 유사성을 효율적으로 분석하는 데 필수적인 도구로 활용됩니다. 특히, 생물 정보학, 데이터 압축, 정보 검색 등 다양한 분야에서 널리 사용됩니다.

접미사 배열을 이해하기 위해서는 먼저 접미사(suffix)의 개념을 알아야 합니다. 문자열의 접미사란, 문자열의 특정 위치에서 시작하여 끝까지 이어지는 부분 문자열을 의미합니다. 예를 들어, 문자열 "banana"의 접미사들은 다음과 같습니다:

• "banana"
• "anana"
• "nana"
• "ana"
• "na"
• "a"

접미사 배열은 이러한 모든 접미사들을 사전식(lexicographical) 순서로 정렬하여 그 시작 위치를 저장하는 정수 배열입니다. 즉, 문자열의 모든 접미사들을 정렬한 다음, 각 접미사의 원래 위치를 배열에 기록하는 것입니다.

이러한 구조를 통해 접미사 배열은 문자열 내의 특정 패턴을 찾는 문제를 빠르게 해결할 수 있게 해줍니다. 일반적으로 문자열을 탐색하는 데 걸리는 시간 복잡도가 $O(n^2)$인 반면, 접미사 배열을 사용하면 $O(m \log n)$으로 줄일 수 있습니다. (여기서 n은 문자열의 길이, m은 패턴의 길이)

2. 접미사 배열의 구성

접미사 배열은 두 개의 주요 배열로 구성됩니다. 하나는 접미사들의 시작 위치를 저장하는 배열(SA 또는 suffix_array), 다른 하나는 각 접미사들의 공통 접두사의 길이를 저장하는 배열(LCP 또는 longest common prefix)입니다.

1) 접미사 배열 (Suffix Array, SA)

접미사 배열 SA는 입력 문자열의 모든 접미사들을 사전 순으로 정렬한 후, 각 접미사의 시작 위치(index)를 저장하는 배열입니다. SA[i]는 사전 순으로 i번째 접미사의 시작 위치를 나타냅니다.

예를 들어, 문자열 "banana"에 대한 접미사 배열을 구성하는 과정을 살펴보겠습니다.

1. 모든 접미사 생성:

   • banana
   • anana
   • nana
   • ana
   • na
   • a

2. 사전 순 정렬:

   • a
   • ana
   • anana
   • banana
   • na
   • nana

3. 시작 위치 저장 (Suffix Array):

   • a (위치: 5)
   • ana (위치: 3)
   • anana (위치: 1)
   • banana (위치: 0)
   • na (위치: 4)
   • nana (위치: 2)

   따라서, 접미사 배열 SA는 [5, 3, 1, 0, 4, 2]가 됩니다.

2) LCP 배열 (Longest Common Prefix, LCP)

LCP 배열은 인접한 두 접미사 간의 가장 긴 공통 접두사(longest common prefix)의 길이를 저장하는 배열입니다. LCP[i]는 SA[i]와 SA[i-1]에 해당하는 접미사들의 가장 긴 공통 접두사의 길이를 나타냅니다. LCP 배열은 접미사 배열과 함께 사용되어 문자열의 반복 패턴을 효율적으로 파악하고 다양한 문자열 관련 문제를 해결하는 데 도움을 줍니다.

예를 들어, 위에서 구한 접미사 배열 SA = [5, 3, 1, 0, 4, 2]와 "banana" 문자열을 사용하여 LCP 배열을 계산해 보겠습니다.

1. 인접한 접미사 쌍:

   • SA[0] = 5: "a", SA[1] = 3: "ana"
   • SA[1] = 3: "ana", SA[2] = 1: "anana"
   • SA[2] = 1: "anana", SA[3] = 0: "banana"
   • SA[3] = 0: "banana", SA[4] = 4: "na"
   • SA[4] = 4: "na", SA[5] = 2: "nana"

2. LCP 계산:

   • "a"와 "ana"의 LCP: "a", 길이 = 1
   • "ana"와 "anana"의 LCP: "ana", 길이 = 3
   • "anana"와 "banana"의 LCP: "" (공백), 길이 = 0
   • "banana"와 "na"의 LCP: "", 길이 = 0
   • "na"와 "nana"의 LCP: "na", 길이 = 2

3. LCP 배열: [0, 1, 3, 0, 0, 2] (LCP 배열은 일반적으로 첫 번째 값은 정의되지 않으므로, 0으로 초기화합니다.)

LCP 배열은 접미사 배열과 함께 사용되어 다양한 문자열 관련 문제, 특히 부분 문자열의 중복, 유사성, 반복 패턴 등을 파악하는 데 효과적입니다.

3. 접미사 배열의 활용

접미사 배열은 다양한 문자열 관련 문제들을 효율적으로 해결하는 데 사용됩니다. 몇 가지 주요 활용 사례는 다음과 같습니다.

1) 패턴 검색

접미사 배열은 문자열 내에서 특정 패턴을 검색하는 데 매우 효율적입니다. 이진 검색(Binary Search)을 사용하여 $O(m \log n)$ 시간 복잡도로 패턴을 찾을 수 있습니다. 여기서 m은 패턴의 길이, n은 문자열의 길이입니다.

• 과정:
  1. 접미사 배열을 생성합니다.
  2. 이진 검색을 사용하여 패턴이 시작되는 접미사의 인덱스를 찾습니다. 각 접미사의 시작 위치에서 패턴을 비교합니다.
  3. 패턴이 발견되면 해당 위치를 반환합니다.

2) 중복 문자열 찾기

접미사 배열과 LCP 배열을 사용하여 문자열 내에서 반복되는 부분 문자열(중복 문자열)을 찾을 수 있습니다.

• 과정:
  1. 접미사 배열과 LCP 배열을 생성합니다.
  2. LCP 배열에서 가장 큰 값을 찾습니다. 이 값은 가장 긴 중복 부분 문자열의 길이를 나타냅니다.
  3. 해당 길이의 부분 문자열을 접미사 배열에서 찾아 반환합니다.

3) 최장 공통 부분 문자열 (LCS)

접미사 배열은 두 개 이상의 문자열 간의 최장 공통 부분 문자열(Longest Common Substring, LCS)을 찾는 데 사용될 수 있습니다.

• 과정:
  1. 두 문자열을 연결하고, 연결된 문자열의 끝을 나타내는 고유한 구분자(예: '$')를 추가합니다. 예: "string1$string2"
  2. 결합된 문자열에 대한 접미사 배열과 LCP 배열을 생성합니다.
  3. LCP 배열을 순회하면서, 서로 다른 두 문자열에서 시작하는 접미사들의 LCP 값을 찾습니다.
  4. 가장 큰 LCP 값을 가진 접미사 쌍이 LCS에 해당합니다.

4) 기타 활용

• 생물 정보학: DNA 서열 분석, 유전자 검색
• 데이터 압축: LZ77 알고리즘 등
• 정보 검색: 문서 내의 키워드 검색, 유사 문서 찾기

4. 접미사 배열 구성 알고리즘

접미사 배열을 구성하는 데는 여러 알고리즘이 사용될 수 있으며, 알고리즘의 효율성은 시간 복잡도에 따라 달라집니다.

1) 단순 정렬 (Naive Approach)

가장 간단한 방법은 모든 접미사를 생성하고, 사전식 순서로 정렬하는 것입니다. 이 방법은 $O(n^2 \log n)$의 시간 복잡도를 가집니다. (n은 문자열의 길이)

• 과정:
  1. 모든 접미사를 생성합니다.
  2. 표준 정렬 알고리즘(예: 퀵 정렬, 병합 정렬)을 사용하여 접미사를 정렬합니다.
  3. 정렬된 접미사의 시작 위치를 접미사 배열에 저장합니다.

이 방법은 구현이 간단하지만, 긴 문자열에 대해서는 비효율적입니다.

2) Kärkkäinen-Sanders 알고리즘 (선형 시간 알고리즘)

Kärkkäinen-Sanders 알고리즘은 접미사 배열을 $O(n)$ 시간에 구성하는 선형 시간 알고리즘입니다. 이 알고리즘은 분할 정복(Divide and Conquer) 방식과 재귀 호출을 사용하여 접미사 배열을 효율적으로 생성합니다. 이 알고리즘은 복잡하지만 이론적으로 매우 중요하며, 실용적인 구현에서도 좋은 성능을 보입니다.

• 과정:
  1. 입력 문자열을 세 개의 문자로 이루어진 그룹으로 나눕니다.
  2. 각 그룹을 정렬하고, 그룹 내의 상대적 순위를 기준으로 새로운 문자열을 생성합니다.
  3. 새로운 문자열에 대한 접미사 배열을 재귀적으로 계산합니다.
  4. 결과를 결합하여 최종 접미사 배열을 구성합니다.

3) Manber-Myers 알고리즘

Manber-Myers 알고리즘은 $O(n \log^2 n)$ 시간 복잡도를 가지는 비교적 간단한 알고리즘입니다. 이 알고리즘은 점진적으로 접미사들을 정렬해 나가는 방식을 사용합니다.

• 과정:
  1. 각 접미사의 첫 번째 문자를 기준으로 정렬합니다.
  2. 정렬된 순서를 기반으로, 각 접미사의 첫 두 문자를 기준으로 정렬합니다.
  3. 이 과정을 반복하며, 정렬 범위를 두 배씩 늘려나갑니다.
  4. 모든 접미사가 정렬될 때까지 반복합니다.

5. LCP 배열 구성 알고리즘

LCP 배열은 접미사 배열이 생성된 후, 접미사 배열을 사용하여 효율적으로 구성할 수 있습니다.

1) 기본적인 LCP 계산

가장 기본적인 방법은 각 인접한 접미사 쌍에 대해 직접 LCP를 계산하는 것입니다. 이 방법은 $O(n^2)$ 시간 복잡도를 가질 수 있습니다.

• 과정:
  1. 접미사 배열을 순회하며, 각 인접한 접미사 쌍을 가져옵니다.
  2. 각 쌍에 대해, 두 접미사의 문자를 앞에서부터 비교하여 일치하는 문자의 수를 계산합니다.
  3. 계산된 값을 LCP 배열에 저장합니다.

2) Kasai의 알고리즘 (선형 시간 알고리즘)

Kasai의 알고리즘은 LCP 배열을 $O(n)$ 시간에 계산하는 효율적인 알고리즘입니다. 이 알고리즘은 접미사 배열과 원본 문자열을 사용하여 LCP 배열을 구성합니다. 핵심 아이디어는 접미사 배열에서 인접한 두 접미사의 LCP 값을 사용하여 다른 접미사들의 LCP 값을 계산하는 것입니다.

• 과정:
  1. rank 배열을 생성합니다. rank[i]는 문자열에서 i번째 문자가 시작하는 접미사의 접미사 배열에서의 위치(index)를 나타냅니다.
  2. LCP 배열을 계산합니다. LCP[i] = 0으로 초기화합니다.
  3. 원본 문자열을 순회하며, 각 문자에 대해 다음 단계를 수행합니다.
     • k = 0으로 초기화합니다.
     • rank[i]에 해당하는 접미사와 rank[i] - 1에 해당하는 접미사의 LCP를 계산합니다. (단, i > 0)
     • LCP[rank[i]] = k로 설정합니다.
     • k = max(0, k - 1)로 업데이트합니다.

6. 주의사항과 트러블슈팅

1) 메모리 사용량

접미사 배열은 문자열의 길이에 비례하는 메모리를 사용합니다. 특히, LCP 배열까지 함께 사용하면 추가적인 메모리 공간이 필요합니다. 매우 긴 문자열을 처리할 때는 메모리 사용량을 고려해야 합니다.

2) 성능 최적화

접미사 배열 구성 알고리즘의 선택은 성능에 큰 영향을 미칩니다. 선형 시간 알고리즘 (예: Kärkkäinen-Sanders, Kasai)을 사용하면 더 효율적으로 접미사 배열과 LCP 배열을 구성할 수 있습니다.

3) 구현의 복잡성

접미사 배열 관련 알고리즘은 구현이 다소 복잡할 수 있습니다. 특히, Kärkkäinen-Sanders 알고리즘과 같은 선형 시간 알고리즘은 신중한 구현이 필요합니다. 하지만, 올바르게 구현하면 문자열 처리 문제를 해결하는 데 매우 강력한 도구가 될 수 있습니다.

4) 문자열 인덱스 오류

접미사 배열을 사용하는 동안, 문자열의 인덱스 범위를 벗어나는 오류가 발생하지 않도록 주의해야 합니다. 특히, 접미사 배열과 LCP 배열을 함께 사용할 때, 인덱스 계산에 오류가 없도록 꼼꼼하게 확인해야 합니다.

7. 결론

접미사 배열은 문자열 처리 분야에서 매우 유용한 자료구조입니다. 문자열 검색, 패턴 매칭, 중복 문자열 찾기 등 다양한 문제들을 효율적으로 해결할 수 있습니다. 접미사 배열의 개념, 구성, 그리고 다양한 활용 사례를 이해하는 것은 문자열 알고리즘 및 데이터 구조에 대한 깊이 있는 이해를 돕고, 실제 문제 해결 능력을 향상시키는 데 기여할 것입니다.