간결한(Succinct) 데이터 구조

1 week ago 2

성능 최적화를 위해 논문을 읽던 중 Succinct Data Structures(간결한 데이터 구조) 개념을 처음 접하게 됨
관련 논문을 찾다가 저명한 연구자인 Gonzalo Navarro 교수와 직접 연락을 주고받음
기존의 배열, 해시맵, 트리 등과 달리 왜 이러한 데이터 구조가 잘 사용되지 않는지 의문이 생김
이에 대해 간략히 설명하고자 함

Succinct Data Structures 개요

일반적인 데이터 압축과 유사하게 데이터를 압축하여 저장하지만, 압축된 상태에서도 직접 활용 가능
기존 압축 방식과 차이점: 데이터를 압축 해제하지 않고도 접근 및 조작 가능
최근 25년 동안 연구가 활발하게 진행된 분야

Rust에서의 활용

시스템 프로그래밍에서는 성능과 메모리 사용이 중요한데, 이러한 데이터 구조가 유용할 가능성이 높음
기존 연구는 주로 **C++**에서 이루어졌으나, Rust에서도 구현을 찾기 시작함
Rust 개발자들에게 도움이 될 만한 라이브러리를 소개

Bit Vectors (비트 벡터)

비트 배열 예시: [0, 1, 0, 1, 1, 0, 1, 0]
64비트 시스템에서 64개의 비트를 단일 정수로 저장 가능하여 공간 절약 효과 있음
비트 벡터 자체는 succinct 구조가 아니지만, 이를 효율적으로 활용하는 방법이 존재

Rank/Select Bit Vector

Rank 연산: 특정 인덱스 이전에 1이 몇 번 등장했는지 계산
- 예시: rank(3) → 2
Select 연산: 특정 번째 1이 등장하는 위치 반환
- 예시: select(2) → 3
O(1) 시간 복잡도로 실행 가능
메모리 오버헤드가 적으며, 큰 문자열을 다룰 때 유용함
활용 사례
- 큰 문자열을 작은 문자열 단위로 나누어 저장할 때 유용
- 특정 인덱스가 어느 부분 문자열에 속하는지 효율적으로 찾을 수 있음
- 압축 저장 방식을 통해 메모리 사용량을 줄이면서도 빠른 검색 가능
Rust 라이브러리
- vers: 높은 성능과 최소한의 오버헤드 제공
- sucds: SArray 같은 희소(Sparse) 구현 지원
- vers는 효율적인 데이터 구조 생성에 강점이 있어 향후 희소 구현도 지원 예정

Wavelet Matrix (웨이블릿 행렬)

Rank/Select 개념을 더 큰 알파벳을 포함하는 데이터에 확장
예: DNA 서열 분석(A, C, G, T) 또는 텍스트 검색(UTF-8 문자, 256개 기호)
Rank/Select 비트 벡터를 기반으로 동작
Rust 라이브러리
- vers에 웨이블릿 행렬 구현 포함

FM-Index (압축된 문자열 색인)

대량의 텍스트 데이터를 압축하여 저장하면서도 검색 기능을 지원
핵심 기능:
- count(pattern): 특정 패턴(문자열)이 몇 번 등장하는지 계산
- locate(pattern): 해당 패턴이 등장하는 모든 인덱스 반환
DNA 서열 검색 및 대규모 텍스트 검색에서 유용
Rust 라이브러리
- fm-index 라이브러리 사용 가능
- 기존에는 fid을 사용했으나 vers로 마이그레이션 후 성능 향상됨

Balanced Parentheses (균형 잡힌 괄호 표현)

트리 구조를 2비트 per 노드 수준으로 압축하여 저장
예제 트리:

a / \ b c

(()()) 형태로 표현 가능
1(열린 괄호)와 0(닫힌 괄호)로 변환 가능: 110100
Rank/Select 연산을 활용하여 트리 내 탐색 연산 최적화
Rust 라이브러리
- vers의 dev-bp 브랜치에서 구현 중

응용: XML 저장 및 처리

XML을 균형 잡힌 괄호 표현을 이용해 저장 가능
XML 태그(p, div 등)를 효율적으로 처리하기 위해 Rank/Select 비트 벡터 활용
FM-Index를 사용하여 텍스트 검색 성능 향상

결론

succinct 데이터 구조는 적은 메모리 사용과 빠른 연산을 동시에 제공
C++에서 연구가 많았지만 Rust에서도 적극적으로 구현되고 있음
연구자 및 오픈 소스 개발자들과 협업하면서 많은 가능성을 발견
향후 다양한 컴퓨터 과학 분야에서 더 널리 사용될 가능성 큼

Read Entire Article