# 간결한(Succinct) 데이터 구조

> Clean Markdown view of GeekNews topic #19618. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=19618](https://news.hada.io/topic?id=19618)
- GeekNews Markdown: [https://news.hada.io/topic/19618.md](https://news.hada.io/topic/19618.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2025-03-07T18:33:35+09:00
- Updated: 2025-03-07T18:33:35+09:00
- Original source: [blog.startifact.com](https://blog.startifact.com/posts/succinct/)
- Points: 20
- Comments: 2

## Summary

간결한 데이터 구조는 데이터를 압축하여 저장하면서도 압축 해제 없이 접근 및 조작이 가능하여 메모리 사용을 줄이면서 빠른 연산을 제공하는 기술입니다. Rust에서도 이러한 구조를 활용하기 위한 다양한 라이브러리가 개발되고 있으며, 특히 Rank/Select 비트 벡터와 FM-Index는 대량의 텍스트 데이터 검색 및 처리에 유용합니다. 이러한 데이터 구조는 시스템 프로그래밍에서 성능 최적화에 기여할 수 있으며, 앞으로 다양한 컴퓨터 과학 분야에서 더 널리 사용될 가능성이 큽니다.

## Topic Body

- 성능 최적화를 위해 논문을 읽던 중 **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`](https://crates.io/crates/vers-vecs): 높은 성능과 최소한의 오버헤드 제공  
  - [`sucds`](https://crates.io/crates/sucds): `SArray` 같은 희소(Sparse) 구현 지원  
  - `vers`는 **효율적인 데이터 구조 생성**에 강점이 있어 향후 희소 구현도 지원 예정  
  
### Wavelet Matrix (웨이블릿 행렬)  
  
- Rank/Select 개념을 **더 큰 알파벳을 포함하는 데이터**에 확장  
- 예: **DNA 서열 분석**(A, C, G, T) 또는 **텍스트 검색**(UTF-8 문자, 256개 기호)  
- Rank/Select 비트 벡터를 기반으로 동작  
- **Rust 라이브러리**  
  - [`vers`](https://crates.io/crates/vers-vecs)에 웨이블릿 행렬 구현 포함  
  
### FM-Index (압축된 문자열 색인)  
  
- 대량의 텍스트 데이터를 압축하여 저장하면서도 **검색 기능**을 지원  
- 핵심 기능:  
  - `count(pattern)`: 특정 패턴(문자열)이 몇 번 등장하는지 계산  
  - `locate(pattern)`: 해당 패턴이 등장하는 **모든 인덱스 반환**  
- **DNA 서열 검색** 및 **대규모 텍스트 검색**에서 유용  
- **Rust 라이브러리**  
  - [`fm-index`](https://crates.io/crates/fm-index) 라이브러리 사용 가능  
  - 기존에는 [`fid`](https://docs.rs/fid/latest/fid/)을 사용했으나 `vers`로 마이그레이션 후 성능 향상됨  
  
### Balanced Parentheses (균형 잡힌 괄호 표현)  
  
- 트리 구조를 **2비트 per 노드** 수준으로 압축하여 저장  
- 예제 트리:  
```  
   a  
 /   \  
b     c  
```  
- `(()())` 형태로 표현 가능  
- `1`(열린 괄호)와 `0`(닫힌 괄호)로 변환 가능: `110100`  
- Rank/Select 연산을 활용하여 **트리 내 탐색 연산 최적화**  
- **Rust 라이브러리**  
  - [`vers`](https://crates.io/crates/vers-vecs)의 `dev-bp` 브랜치에서 구현 중  
  
### 응용: XML 저장 및 처리  
  
- XML을 **균형 잡힌 괄호 표현**을 이용해 저장 가능  
- XML 태그(`p`, `div` 등)를 효율적으로 처리하기 위해 **Rank/Select 비트 벡터 활용**  
- `FM-Index`를 사용하여 **텍스트 검색 성능 향상**  
  
### 결론  
  
- succinct 데이터 구조는 **적은 메모리 사용**과 **빠른 연산**을 동시에 제공  
- **C++에서 연구가 많았지만 Rust에서도 적극적으로 구현되고 있음**  
- 연구자 및 오픈 소스 개발자들과 협업하면서 많은 가능성을 발견  
- **향후 다양한 컴퓨터 과학 분야에서 더 널리 사용될 가능성 큼**

## Comments



### Comment 35608

- Author: qwqwhs
- Created: 2025-03-09T19:35:25+09:00
- Points: 1

Wavelet 을 활용한 압축 구조는 Djvu에서 표준으로 잘 사용되고 있습니다. 이미지 압축이 정말 훌륭하죠.

### Comment 35566

- Author: neo
- Created: 2025-03-07T18:33:35+09:00
- Points: 1

###### [Hacker News 의견](https://news.ycombinator.com/item?id=43282995) 
* Gonzalo Navarro에게 이메일을 보내 질문을 했고, 그 결과로 함께 논문을 작성하게 되었음
  - 그의 또 다른 논문은 몇 가지 우아한 아이디어를 결합하여 비트벡터 랭크/셀렉트의 간단한 구현을 다루고 있음
  - 이 시기에 간결한 데이터 구조에 대해 매우 흥미를 느껴 여러 비트벡터 타입과 웨이브렛 매트릭스를 구현하는 Rust 라이브러리를 작성했음
  - 데이터 시각화 관점에서 공간 효율적인 데이터 구조가 클라이언트 측에서 대규모 데이터셋의 상호작용 탐색을 근본적으로 개선할 수 있는지 궁금했음

* 이 분야에 30년 넘게 있었지만 "간결한 데이터 구조"라는 것을 처음 들어봤음
  - 이 게시물을 보지 않았다면 아마도 알지 못했을 것임
  - 이 데이터 구조가 그래프 처리에 실질적인 응용을 가지고 있다면 중요한 발견일 수 있음
  - 이 주제가 매력적으로 느껴짐

* 간결한 데이터 구조는 데이터셋이 메모리에 맞는 경우 기존 구조보다 빠르지 않을 수 있음
  - 하지만 대규모 데이터셋에서는 저장소 접근 시간이 지배적이므로 간결한 데이터 구조가 유리함
  - 간결한 트리는 예술 작품과 같음

* Edward Kmett로부터 간결한 데이터 구조의 개념을 처음 들었음
  - 그는 유명한 Haskell 라이브러리 개발자이며, 오래전에 간결한 데이터 구조에 대한 강연을 했음

* 간결한 데이터 구조는 매우 재미있음
  - Zig로 이를 구현했으며, 주요 구현은 4비트 미만의 요소를 사용하는 최소 완벽 해시 함수임
  - 이러한 알고리즘을 구현하는 것은 마법과 같음

* Navarro의 책은 훌륭한 조사서임
  - Erik Demaine의 간결한 데이터 구조에 대한 강의도 훌륭함

* 간결한 데이터 구조에 대해 아침을 보냈으며, 메모리 효율성이 놀라움
  - 대규모 XML 파일을 분석하는 프로젝트에서 RAM을 많이 소모하고 있음
  - 웨이브렛 매트릭스 개념이 텍스트 중심의 작업에 유망해 보임

* 대형 구조체의 메모리 내 노드 표현을 효율적으로 만드는 방법이 있음
  - 드물게 사용되는 필드의 오프셋을 할당하고 비트마스크를 사용하여 필드의 존재를 나타냄
  - 마스킹과 popcount는 빠른 접근을 가능하게 함

* Marisa trie는 매우 멋지고 유용한 간결한 데이터 구조임
  - High Performance Python 책에서도 언급됨

* 간결한 데이터 구조를 위한 나의 기본 라이브러리는 SDSL-Lite임