ds · 18

접미사 배열

검색접미사배열문자열

긴 문자열에서 "이 패턴이 어디에 나오는가?"를 여러 번 물어야 할 때, 질문마다 문자열 전체를 훑으면 비효율적입니다. 문자열을 미리 정리해 두면 질문마다 훨씬 빠르게 답할 수 있습니다. 접미사 배열(suffix array)은 문자열의 모든 접미사를 사전순으로 정렬했을 때 각 접미사가 시작하는 인덱스를 차례로 적어 둔 배열로, 이 정렬 덕분에 패턴 검색을 이진 탐색으로 할 수 있습니다.

예를 들어 "banana"의 접미사는 banana, anana, nana, ana, na, a이고, 이를 사전순으로 정렬하면 a, ana, anana, banana, na, nana입니다. 각각의 시작 인덱스를 모은 [5, 3, 1, 0, 4, 2]가 접미사 배열입니다. 접미사 문자열을 모두 저장하지 않고 인덱스 n개만 저장하므로 공간이 O(n)입니다. 이웃한 접미사의 공통 접두사 길이를 담은 LCP 배열을 함께 쓰면 가장 긴 반복 부분 문자열 같은 문제도 풀 수 있습니다.

핵심 개념

접미사

문자열의 i번째 글자부터 끝까지입니다. 길이 n인 문자열에는 접미사가 n개 있고, 인덱스 i가 접미사 하나를 대표합니다.

핵심 개념

접미사 배열

접미사를 사전순으로 정렬했을 때 시작 인덱스를 순서대로 적은 배열입니다. SA[r]은 순위(0부터) r인 접미사가 시작하는 위치입니다.

핵심 개념

패턴 검색

패턴으로 시작하는 접미사들은 정렬된 배열에서 연속된 구간을 이룹니다. 이진 탐색으로 구간의 시작과 끝을 찾으면 구간의 SA 값이 모두 출현 위치입니다.

핵심 개념

LCP 배열

사전순으로 이웃한 두 접미사가 앞에서부터 몇 글자까지 같은지(최장 공통 접두사)를 적은 배열입니다. 정렬하면 같은 접두사를 가진 접미사끼리 이웃하므로, 임의의 두 접미사의 공통 접두사 길이는 그 사이 구간 LCP의 최솟값으로 구할 수 있습니다.

핵심 개념

구성 알고리즘

접미사를 비교 정렬하면 단순하지만 느리고, 접두사를 두 배씩 늘려 가며 기수(계수) 정렬로 순위를 매기는 방식은 O(n log n), 선형 시간 알고리즘은 O(n)에 접미사 배열을 만듭니다.

핵심 개념

접미사 트리와의 관계

접미사 트리가 하는 일의 상당 부분을 접미사 배열과 LCP 배열이 더 적은 메모리로 해냅니다. 구조가 정렬된 배열과 이진 탐색이라 단순하지만, 선형 시간 구성 알고리즘은 복잡합니다.

검색은 이진 탐색으로 합니다 — 패턴 길이를 m이라 하면 비교 한 번에 최대 m글자를 보므로 구간의 시작과 끝을 찾는 데 대략 O(m log n)이 듭니다. 패턴이 텍스트보다 훨씬 짧으면, 같은 문자열을 여러 번 검색할 때 매번 O(n)씩 훑는 것보다 빠릅니다.

공간이 O(n)입니다 — 접미사를 문자열로 저장하지 않고 정수 인덱스만 저장합니다. 접미사를 모두 저장하면 O(n^2)가 됩니다.

전처리 비용을 한 번 치릅니다 — 구성에 시간이 들지만, 한 번 만들면 같은 문자열에 대한 많은 질문에 재사용합니다. 문자열이 바뀌면 보통 다시 만듭니다.

LCP로 통계를 얻습니다 — LCP의 최댓값이 가장 긴 반복 부분 문자열의 길이이고, n(n + 1) / 2에서 LCP의 합을 빼면 서로 다른 부분 문자열의 개수입니다.

이 시각화에서 확인할 것 — "구성" 탭에서 접미사가 사전순으로 놓이는 과정을, "패턴 검색" 탭에서 이진 탐색이 구간의 시작과 끝을 좁혀 가는 모습을, "LCP 배열" 탭에서 이웃한 접미사의 공통 접두사를 STEP으로 확인하세요.

접미사 배열의 배경

접미사 배열은 우디 매버(Udi Manber)와 진 마이어스(Gene Myers)가 1990년 소개했고, 이후 1993년 학술지에 "Suffix arrays: a new method for on-line string searches"로 실렸습니다. 접미사 트리보다 메모리를 적게 쓰면서 온라인 문자열 검색을 효율적으로 하자는 것이 목표였습니다. 이후 선형 시간에 구성하는 알고리즘(Kärkkäinen과 Sanders, Ko와 Aluru 등)과 LCP 배열을 선형 시간에 구하는 Kasai 등의 알고리즘이 나와, 접미사 배열과 LCP 배열을 모두 선형 시간에 만들 수 있게 되었습니다.

숫자로 확인하기

구성 — "banana"의 접미사 6개를 사전순으로 정렬하면 a(5), ana(3), anana(1), banana(0), na(4), nana(2)이고, 접미사 배열은 [5, 3, 1, 0, 4, 2]입니다.

검색 — 패턴 "ana"는 이진 탐색으로 구간 [1, 3)을 찾고, 그 구간의 SA 값 3과 1이 출현 위치입니다. 실제로 "banana"의 1번과 3번 위치에서 "ana"가 시작합니다.

LCP 배열 — 이웃한 접미사의 공통 접두사 길이는 [0, 1, 3, 0, 0, 2]입니다. 최댓값 3이 가리키는 문자열이 "ana"입니다.

서로 다른 부분 문자열 — "banana"는 21 - 6 = 15개입니다. "mississippi"는 가장 긴 반복 부분 문자열이 "issi", 서로 다른 부분 문자열이 53개로, 모든 부분 문자열을 직접 모아 센 값과 같았습니다.

자주 하는 오해

접미사 배열이 접미사 문자열을 저장한다 — 인덱스만 저장하고 문자열은 원본을 그대로 씁니다. 그래서 공간이 O(n)입니다.

단순 정렬이면 충분하다 — 접미사를 비교하는 데 최대 O(n)이 걸려서 정렬 전체가 O(n^2 log n)까지 갈 수 있습니다. 긴 문자열에는 전용 구성 알고리즘을 씁니다.

접미사 트리의 완전한 대체이다 — 많은 문제를 접미사 배열과 LCP 배열로 풀 수 있지만, 일부 연산은 접미사 트리가 더 직접적입니다. 메모리가 중요하면 접미사 배열을 고릅니다.

문자열이 바뀌어도 쉽게 갱신된다 — 문자열을 수정하면 접미사의 순서가 바뀌므로 다시 만드는 것이 보통입니다. 한 번 만들고 여러 번 질의하는 상황에 알맞습니다.

면접에서 이렇게 물어요

면접 질문

접미사 배열이란 무엇인가요?

문자열의 모든 접미사를 사전순으로 정렬했을 때 각 접미사가 시작하는 인덱스를 저장한 배열입니다. 접미사 문자열이 아니라 인덱스만 저장해 공간이 O(n)입니다.

면접 질문

패턴 검색은 어떻게 하나요?

정렬되어 있으므로 패턴으로 시작하는 접미사들이 연속된 구간을 이룹니다. 이진 탐색으로 구간의 시작과 끝을 찾고, 그 구간의 SA 값이 출현 위치입니다.

면접 질문

LCP 배열은 어디에 쓰나요?

이웃한 접미사의 최장 공통 접두사 길이로, 가장 긴 반복 부분 문자열과 서로 다른 부분 문자열의 개수 계산에 씁니다. 후자는 n(n + 1) / 2에서 LCP의 합을 뺍니다.

면접 질문

접미사 트리와 비교하면?

접미사 배열은 보통 메모리를 적게 쓰고(원 논문은 실제 구현에서 3~5배 적다고 보고) 구조가 단순합니다. 접미사 트리는 일부 연산이 더 직접적이지만 메모리와 구현 부담이 큽니다.

실제 시스템에서는

생물정보학 — 긴 유전체 서열에서 짧은 서열이 어디에 나오는지 찾는 문제에서 BWA, Bowtie 같은 도구가 BWT 기반 FM 인덱스를 씁니다. FM 인덱스는 접미사 배열처럼 패턴의 출현 구간을 찾되 압축된 공간에 담은 구조입니다.

데이터 압축 — 버로스-휠러 변환(BWT)은 문자열의 회전을 정렬한 결과를 이용하는데, 문자열 끝에 종료 기호를 붙이면 회전 정렬과 접미사 정렬의 순서가 같아서 접미사 배열 SA에서 BWT[i] = T[SA[i] - 1]로 얻을 수 있습니다. bzip2 압축에 BWT가 쓰입니다.

알고리즘 대회 — 가장 긴 반복 부분 문자열, 서로 다른 부분 문자열 수, 두 문자열의 가장 긴 공통 부분 문자열 같은 문제에 자주 쓰는 도구입니다.

함께 보면 좋은 토픽

이진 탐색 — 접미사 배열 검색이 쓰는 이진 탐색의 원리를 봅니다.

트라이 — 문자열을 접두사 트리로 저장하는 구조와 비교합니다.

정렬 비교 — 접미사를 정렬하는 비용을 이해하는 데 도움이 됩니다.

시간 복잡도 — O(n log n)과 O(n^2 log n)의 차이를 봅니다.

참고 자료

논문 — Manber, U. and Myers, G., "Suffix arrays: a new method for on-line string searches", SIAM Journal on Computing 22(5), 1993

논문 — Kasai, T. 외, "Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications", CPM 2001

학습 자료 — cp-algorithms Suffix Array

Python — 접미사 배열 구성과 이진 탐색

def build_sa(s):
    return sorted(range(len(s)), key=lambda i: s[i:])   # 접미사를 사전순으로 정렬

s = 'banana'
sa = build_sa(s)
print(sa)                          # [5, 3, 1, 0, 4, 2]
print([s[i:] for i in sa])             # ['a', 'ana', 'anana', 'banana', 'na', 'nana']

def search(s, sa, p):
    lo, hi = 0, len(sa)
    while lo < hi:                      # p 이상인 첫 접미사
        mid = (lo + hi) // 2
        if s[sa[mid]:sa[mid] + len(p)] < p: lo = mid + 1
        else: hi = mid
    start = lo
    hi = len(sa)
    while lo < hi:                      # 앞 len(p)글자가 p보다 큰 첫 접미사
        mid = (lo + hi) // 2
        if s[sa[mid]:sa[mid] + len(p)] <= p: lo = mid + 1
        else: hi = mid
    return sorted(sa[start:lo])             # 출현 위치

print(search(s, sa, 'ana'), search(s, sa, 'nan'), search(s, sa, 'xyz'))   # [1, 3] [2] []

접미사 배열은 접미사 문자열 자체가 아니라 각 접미사가 시작하는 인덱스만 저장합니다(결과 배열은 인덱스 n개). 위 코드는 접미사를 키로 삼아 인덱스를 정렬하는 가장 단순한 구성법으로, "banana"에서 [5, 3, 1, 0, 4, 2]가 나옵니다. 시각화의 구성 탭이 보여 주는 순서와 같습니다. 검색은 정렬된 접미사에 대한 이진 탐색을 두 번 합니다. 첫 번째는 앞 len(p)글자가 패턴 이상인 첫 접미사를, 두 번째는 패턴보다 큰 첫 접미사를 찾아, 그 사이가 패턴으로 시작하는 접미사의 구간입니다. "ana"는 구간 [1, 3)에 접미사 두 개(인덱스 3과 1)가 있어 위치 [1, 3]이 나옵니다. 이 단순한 구성은 접미사 비교에 최대 O(n)이 걸려 전체가 O(n^2 log n)에 이를 수 있고, 정렬 키로 접미사 문자열을 임시로 만들어 메모리도 O(n^2) 쓰므로 학습용입니다. 실제로는 O(n log n)이나 O(n)에 구성하는 알고리즘을 씁니다.

Python — Kasai 알고리즘으로 LCP 배열 구하기

def kasai(s, sa):
    n = len(s)
    rank = [0] * n
    for i, p in enumerate(sa): rank[p] = i      # 접미사 p의 사전순 순위
    lcp = [0] * n                         # lcp[i] = sa[i-1]과 sa[i]의 공통 접두사 길이
    h = 0
    for i in range(n):
        if rank[i] > 0:
            j = sa[rank[i] - 1]                # 사전순으로 바로 앞 접미사
            while i + h < n and j + h < n and s[i + h] == s[j + h]:
                h += 1
            lcp[rank[i]] = h
            if h > 0: h -= 1                # 다음 접미사는 최소 h-1은 같다
        else:
            h = 0
    return lcp

lcp = kasai(s, sa)
print(lcp)                             # [0, 1, 3, 0, 0, 2]

LCP 배열의 lcp[i]는 사전순으로 이웃한 접미사 sa[i - 1]과 sa[i]가 앞에서부터 몇 글자까지 같은지를 나타냅니다. "banana"에서는 [0, 1, 3, 0, 0, 2]로, 시각화의 LCP 탭에서 이웃한 쌍을 위에서부터 비교한 값과 같습니다. Kasai 알고리즘은 문자열 순서대로(i = 0, 1, 2, ...) 접미사를 보면서, 접미사 i와 사전순으로 바로 앞 접미사의 공통 접두사가 h(> 0)글자였다면 접미사 i + 1과 그 사전순 앞 접미사는 최소 h - 1글자를 공유한다는 성질로 h를 거의 줄이지 않고 이어 갑니다. h는 한 번에 최대 1씩 줄고 n을 넘지 못하므로 전체 증가 횟수가 2n 이하여서 O(n)입니다. 순위 배열 rank(접미사 p가 사전순 몇 번째인지)가 필요해서 접미사 배열을 먼저 만든 뒤에 호출합니다.

Python — 가장 긴 반복 부분 문자열과 서로 다른 부분 문자열 수

def analyze(s):
    sa = build_sa(s)
    lcp = kasai(s, sa)
    k = max(range(len(s)), key=lambda i: lcp[i])
    longest = s[sa[k]:sa[k] + lcp[k]]                  # LCP의 최댓값이 가리키는 접두사
    distinct = len(s) * (len(s) + 1) // 2 - sum(lcp)    # 전체 접두사 수 - LCP 합
    return longest, distinct

for w in ['banana', 'mississippi', 'abracadabra']:
    print(w, analyze(w))
# banana ('ana', 15)
# mississippi ('issi', 53)
# abracadabra ('abra', 54)

LCP의 최댓값은 두 번 이상 나타나는 가장 긴 부분 문자열의 길이입니다. 그 값을 가진 이웃 쌍이 공통으로 가진 접두사가 바로 그 문자열입니다. "banana"에서 LCP의 최댓값은 3이고 문자열은 "ana"입니다. 서로 다른 부분 문자열의 개수는 모든 접미사의 접두사 수 n(n + 1) / 2에서 이웃 접미사끼리 겹치는 접두사 수 LCP의 합을 뺀 값입니다. "banana"는 21 - 6 = 15개입니다. 모든 부분 문자열을 직접 모아 세어도 mississippi는 53개입니다. 접미사 배열과 LCP 배열이 주어지면 이 두 값은 한 번 훑어 선형 시간에 계산되어서, 접미사 배열이 단순한 검색 자료구조를 넘어 문자열 통계에도 쓰이는 이유가 됩니다.

접미사 배열(Suffix Array)이란?

"banana"의 접미사: banana, anana, nana, ana, na, a

접미사 배열은 문자열의 모든 접미사를 사전순으로 정렬한 뒤, 각 접미사가 시작하는 인덱스를 순서대로 저장한 배열입니다.

접미사 배열로 패턴 검색을 하는 기본 방법은?

접미사가 사전순으로 정렬되어 있다는 점을 이용합니다.

접미사들이 정렬되어 있으므로 패턴으로 시작하는 접미사들은 배열에서 연속된 구간을 이룹니다. 이진 탐색으로 그 구간을 찾아 패턴의 출현 위치를 구할 수 있습니다.

LCP 배열이 나타내는 것은?

LCP는 Longest Common Prefix의 약자입니다.

LCP 배열은 접미사 배열에서 이웃한 두 접미사가 앞에서부터 몇 글자까지 같은지를 저장합니다. 가장 긴 반복 부분 문자열, 서로 다른 부분 문자열 개수 등을 구하는 데 활용됩니다.