접미사 배열 (Suffix Array)
쉽게 풀면
"banana"라는 단어가 있다면, 이 단어의 접미사는 "banana", "anana", "nana", "ana", "na", "a" 여섯 가지입니다. 접미사 배열은 이 접미사들을 알파벳 순서로 정렬해서 그 시작 위치만 배열로 저장해 둔 것입니다. 이렇게 미리 정렬해두면, "특정 부분 문자열이 이 텍스트 안에 있는가?"라는 질문에 사전에서 단어 찾듯 이진 탐색으로 빠르게 답할 수 있습니다. 즉, 텍스트 전체를 처음부터 끝까지 훑지 않고도 원하는 패턴이 어디에 있는지 빠르게 찾아낼 수 있는 것입니다.
왜 중요한가
접미사 배열은 문자열 안에서 패턴 검색, 반복 구간 탐지, 최장 공통 부분 문자열 계산처럼 다양한 문자열 문제를 빠르게 처리할 수 있게 해주는 범용 색인 구조이기 때문에, 문자열 알고리즘 연구뿐 아니라 생물정보학, 검색 엔진, 데이터 압축 등 실용적인 응용 분야에서도 핵심 도구로 다뤄집니다. 특히 유전체처럼 매우 긴 문자열을 다뤄야 하는 분야에서는, 매번 전체 텍스트를 훑는 대신 미리 만들어둔 색인을 활용해 반복적인 검색 비용을 크게 줄일 수 있다는 점이 중요하게 여겨집니다.
논문에서는 이렇게 쓰입니다
이 문장은 DNA 염기서열처럼 매우 긴 문자열 데이터에서 특정 패턴이나 반복 구간을 빠르게 찾아내기 위해 접미사 배열을 활용했다는 뜻입니다. 생물정보학(bioinformatics), 전문(full-text) 검색 엔진, 데이터 압축 알고리즘 연구에서 핵심 자료구조로 자주 쓰입니다.
이 문장은 전문 검색 시스템이 방대한 문서 컬렉션에서 사용자가 입력한 임의의 검색어를 빠르게 찾아낼 수 있도록, 접미사 배열 기반 색인을 구축했다는 뜻입니다.
이 문장은 데이터 압축 알고리즘에서 접미사 배열을 이용해 문자열을 압축에 유리한 형태로 재배열하는 변환을 계산했다는 뜻으로, 접미사 배열이 압축 분야에서도 기반 자료구조로 쓰인다는 것을 보여줍니다.
조금 더 깊게 보면
접미사 배열은 흔히 LCP(최장 공통 접두사) 배열과 함께 쓰이는데, 이는 정렬된 순서상 인접한 두 접미사가 앞부분을 얼마나 공유하는지를 나타내는 보조 배열로, 두 접미사 사이의 공통 부분을 매번 처음부터 비교하지 않고도 빠르게 알 수 있게 해줍니다. 접미사 배열을 만드는 방법도 단순 비교 기반 정렬부터 시작해, 접미사들을 여러 단계에 걸쳐 그룹으로 묶어가며 선형 시간에 가깝게 구성하는 접근까지 다양하게 연구되어 왔으며, 유전체 정렬 도구 등 실제 소프트웨어에서는 이러한 효율적인 구성 방법이 필수적으로 쓰입니다.
주의할 점
접미사 배열은 접미사 트리(suffix tree)와 목적이 비슷하지만, 트리 구조 대신 정렬된 배열만 저장하기 때문에 메모리를 훨씬 적게 사용합니다. 다만 접미사 배열 단독으로는 일부 연산(예: 두 접미사의 공통 부분 길이 구하기)이 느릴 수 있어, 실무에서는 LCP 배열 등 보조 자료구조와 함께 쓰는 경우가 많다는 점에 유의해야 합니다.