Suffix Array vs Suffix Tree vs Trie
Suffix Array vs. Suffix Tree vs. Trie Suffix Array, Suffix Tree, 그리고 Trie는 모두 문자열 처리와 패턴 매칭을 위한 데이터 구조로, 각각 고유한 특성과 용도를 가지고 있다. 특성 Suffix Array Suffix Tree Trie 기본 구조 모든 접미사를 정렬하여 저장하는 1차원 배열 모든 접미사를 트리 형태로 저장하는 압축된 트리 구조 문자열을 문자 단위로 저장하는 트리 구조 메모리 효율성 O(n), 매우 효율적 O(n), 하지만 실제로는 4n 정도로 큼 O(ALPHABET_SIZE key_length n), 매우 큼 구축 시간 O(n log n) O(n) (Ukkonen’s Algorithm 사용 시) O(n * key_length) 검색 시간 O(m log n + occ), m은 패턴 길이 O(m + occ), m은 패턴 길이 O(m), m은 검색할 문자열 길이 구현 난이도 비교적 간단 매우 복잡 비교적 간단 LCP 계산 추가 배열 필요 트리 구조에서 직접 계산 가능 해당 없음 패턴 매칭 이진 검색 이용 트리 순회로 직접 검색 트리 순회로 직접 검색 공간 지역성 매우 좋음 (연속된 메모리) 보통 (포인터로 인한 흩어짐) 나쁨 (노드가 메모리에 흩어짐) 주요 응용 텍스트 검색, DNA 분석 문자열 처리, 바이오인포매틱스 사전 구현, 자동 완성 동적 업데이트 어려움 가능하나 복잡 쉬움 접두사 검색 어려움 가능하나 비효율적 매우 효율적 최장 공통 접두사 추가 작업 필요 직접 계산 가능 직접 계산 가능 최장 공통 부분 문자열 LCP 배열 필요 직접 계산 가능 부적합 압축 가능성 제한적 매우 좋음 있음 (압축 트라이) 캐시 성능 매우 좋음 보통 나쁨 실제 사용 사례 대용량 문자열 검색 시스템 생물정보학, 문자열 처리 자동 완성, 사전 검색 추가적인 중요 고려사항: ...