Wavelet Tree

개요

Wavelet Tree는 **문자열이나 시퀀스에서 순위(rank), 선택(select), 구간 빈도(range frequency)**와 같은 질의를 빠르게 처리할 수 있도록 설계된 이진 트리 기반의 압축 인덱스 자료구조입니다. 본래 압축 텍스트 인덱싱을 위해 개발되었으나, 현재는 생물정보학, 정보 검색, 문자열 알고리즘 등 다양한 분야에서 활용되고 있습니다.

---

1. 개념 및 정의

Wavelet Tree는 입력 시퀀스를 여러 레벨의 이진 트리로 분해하고, 각 노드에 비트 벡터를 저장하여 특정 질의를 O(log σ) 시간에 처리할 수 있도록 구성됩니다.

• 입력: 길이 n의 시퀀스 S over alphabet Σ
• 트리 구조: 알파벳 구간을 기준으로 분할된 이진 트리
• 노드 데이터: 현재 구간 내 요소의 분할 여부를 나타내는 비트 벡터

---

2. 구조 예시

예: 문자열 S = "ggcaccaa"

1. 알파벳 정렬: a < c < g
2. 루트 노드: [a,c] vs [g] 기준 → "00101110"
3. 왼쪽 자식: a/c 구간 → "100100"
4. 오른쪽 자식: g만 존재 → 종료

각 노드는 Rank/Select를 위한 비트 벡터와, 자식 노드를 포함합니다.

---

3. 주요 연산 및 시간 복잡도

연산	설명	시간 복잡도
Rank(i, c)	인덱스 i까지 문자 c의 등장 횟수	O(log σ)
Select(k, c)	문자 c가 k번째 등장하는 위치	O(log σ)
Access(i)	i번째 문자의 실제 값	O(log σ)
Range Count(l, r, c)	[l, r] 내 문자 c의 개수	O(log σ)

σ: 알파벳 크기 (예: 영문 알파벳은 26)

---

4. 장점과 특징

항목	장점
빠른 질의 응답	대부분 O(log σ) 시간 내 처리 가능
압축 가능성	Huffman-shaped Wavelet Tree로 공간 최적화 가능
범용성	문자열, 정수열, 로그 데이터 등 적용 가능
메모리 효율	Suffix Array보다 적은 공간 사용 가능

Wavelet Matrix로 변형하여 넓은 알파벳 공간도 효율적으로 처리할 수 있습니다.

---

5. 활용 사례

분야	활용 사례
정보 검색	압축 텍스트 인덱스 구현 (FM-index 기반)
생물정보학	DNA 서열의 빠른 매칭과 빈도 분석
통계 분석	범위 내 값 분포 및 히스토그램 생성
시계열 데이터	로그나 트래픽의 효율적 저장 및 질의 처리
공간 인덱스	Wavelet Tree + Quadtree를 통한 2D 질의 지원

Wavelet Tree는 특히 공간-시간 복잡도 균형이 중요한 문제에 적합합니다.

---

6. 구현 및 최적화 기술

전략	설명
Bit Vector Rank/Select	succinct data structure 사용 (e.g., sdsl-lite)
Huffman-Shaped Tree	출현 빈도 기반 비대칭 분할로 압축률 향상
Wavelet Matrix	순차적 비트 분해로 트리 없이도 유사한 기능 구현
SIMD 기반 연산	빠른 질의 처리를 위한 벡터 연산 가속

---

7. 결론

Wavelet Tree는 압축성과 질의 효율을 동시에 제공하는 고급 문자열 자료구조로, Suffix Array와 비교해 더 나은 공간 효율성과 다양한 질의 지원 능력을 갖춘 대안입니다. 문자열 처리, 텍스트 검색, 생물정보학 등 다양한 응용 분야에서 빠르고 메모리 친화적인 텍스트 인덱스가 필요한 경우 핵심 솔루션으로 자리잡고 있으며, Wavelet Matrix 등 변형 구조를 통해 점점 더 넓은 분야로 확장되고 있습니다.