간결한(Succinct) 데이터 구조
(blog.startifact.com)- 성능 최적화를 위해 논문을 읽던 중 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 라이브러리
Wavelet Matrix (웨이블릿 행렬)
- Rank/Select 개념을 더 큰 알파벳을 포함하는 데이터에 확장
- 예: DNA 서열 분석(A, C, G, T) 또는 텍스트 검색(UTF-8 문자, 256개 기호)
- Rank/Select 비트 벡터를 기반으로 동작
-
Rust 라이브러리
-
vers
에 웨이블릿 행렬 구현 포함
-
FM-Index (압축된 문자열 색인)
- 대량의 텍스트 데이터를 압축하여 저장하면서도 검색 기능을 지원
- 핵심 기능:
-
count(pattern)
: 특정 패턴(문자열)이 몇 번 등장하는지 계산 -
locate(pattern)
: 해당 패턴이 등장하는 모든 인덱스 반환
-
- DNA 서열 검색 및 대규모 텍스트 검색에서 유용
- Rust 라이브러리
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에서도 적극적으로 구현되고 있음
- 연구자 및 오픈 소스 개발자들과 협업하면서 많은 가능성을 발견
- 향후 다양한 컴퓨터 과학 분야에서 더 널리 사용될 가능성 큼
Hacker News 의견
-
Gonzalo Navarro에게 이메일을 보내 질문을 했고, 그 결과로 함께 논문을 작성하게 되었음
- 그의 또 다른 논문은 몇 가지 우아한 아이디어를 결합하여 비트벡터 랭크/셀렉트의 간단한 구현을 다루고 있음
- 이 시기에 간결한 데이터 구조에 대해 매우 흥미를 느껴 여러 비트벡터 타입과 웨이브렛 매트릭스를 구현하는 Rust 라이브러리를 작성했음
- 데이터 시각화 관점에서 공간 효율적인 데이터 구조가 클라이언트 측에서 대규모 데이터셋의 상호작용 탐색을 근본적으로 개선할 수 있는지 궁금했음
-
이 분야에 30년 넘게 있었지만 "간결한 데이터 구조"라는 것을 처음 들어봤음
- 이 게시물을 보지 않았다면 아마도 알지 못했을 것임
- 이 데이터 구조가 그래프 처리에 실질적인 응용을 가지고 있다면 중요한 발견일 수 있음
- 이 주제가 매력적으로 느껴짐
-
간결한 데이터 구조는 데이터셋이 메모리에 맞는 경우 기존 구조보다 빠르지 않을 수 있음
- 하지만 대규모 데이터셋에서는 저장소 접근 시간이 지배적이므로 간결한 데이터 구조가 유리함
- 간결한 트리는 예술 작품과 같음
-
Edward Kmett로부터 간결한 데이터 구조의 개념을 처음 들었음
- 그는 유명한 Haskell 라이브러리 개발자이며, 오래전에 간결한 데이터 구조에 대한 강연을 했음
-
간결한 데이터 구조는 매우 재미있음
- Zig로 이를 구현했으며, 주요 구현은 4비트 미만의 요소를 사용하는 최소 완벽 해시 함수임
- 이러한 알고리즘을 구현하는 것은 마법과 같음
-
Navarro의 책은 훌륭한 조사서임
- Erik Demaine의 간결한 데이터 구조에 대한 강의도 훌륭함
-
간결한 데이터 구조에 대해 아침을 보냈으며, 메모리 효율성이 놀라움
- 대규모 XML 파일을 분석하는 프로젝트에서 RAM을 많이 소모하고 있음
- 웨이브렛 매트릭스 개념이 텍스트 중심의 작업에 유망해 보임
-
대형 구조체의 메모리 내 노드 표현을 효율적으로 만드는 방법이 있음
- 드물게 사용되는 필드의 오프셋을 할당하고 비트마스크를 사용하여 필드의 존재를 나타냄
- 마스킹과 popcount는 빠른 접근을 가능하게 함
-
Marisa trie는 매우 멋지고 유용한 간결한 데이터 구조임
- High Performance Python 책에서도 언급됨
-
간결한 데이터 구조를 위한 나의 기본 라이브러리는 SDSL-Lite임