SACA-K: 상수 알파벳에 대한 실용적 선형 시간 접미사 정렬
Source
Evernote/IFTTT Feedly/Practical linear-time O(1)-workspace suffix sorting for constant alphabets.md
Summary
이 문서는 상수 알파벳 집합에 대해 접미사 배열(Suffix Array)을 구성하는 선형 시간 알고리즘인 SACA-K를 소개합니다. SACA-K는 이론적으로 O(n log K + n log n + K log n) 비트의 메모리를 사용하며, 실제 구현에서는 n 바이트 + (n+256) 워드를 사용하여 최대 ASCII 알파벳까지 지원합니다. 실험 결과, 기존에 가장 효율적이었던 SA-IS 알고리즘보다 시간과 공간 효율성에서 우수함을 보였습니다.
Key Points
- SACA-K 알고리즘은 입력 문자열의 접미사를 정렬하여 접미사 배열을 구성하는 O(n) 시간 알고리즘입니다.
- 상수 알파벳 크기(K)를 가정하며, 이론적 메모리 사용량은 n log K + n log n + K log n 비트입니다.
- 실용적 구현은 n 바이트와 (n+256) 워드(워드는 log n 비트)를 사용하여 ASCII 알파벳까지 처리 가능합니다.
- 이전 최선 알고리즘이었던 SA-IS 대비 시간 및 공간 효율성에서 성능 우위를 입증했습니다.