▲

GN⁺: 간결한(Succinct) 데이터 구조

 (blog.startifact.com)
20P by neo 14일전 | ★ favorite | 댓글 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에서도 적극적으로 구현되고 있음
  • 연구자 및 오픈 소스 개발자들과 협업하면서 많은 가능성을 발견
  • 향후 다양한 컴퓨터 과학 분야에서 더 널리 사용될 가능성 큼
▲
qwqwhs 12일전  [-]

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

답변달기
▲
neo 14일전  [-]
Hacker News 의견

  • Gonzalo Navarro에게 이메일을 보내 질문을 했고, 그 결과로 함께 논문을 작성하게 되었음

    • 그의 또 다른 논문은 몇 가지 우아한 아이디어를 결합하여 비트벡터 랭크/셀렉트의 간단한 구현을 다루고 있음
    • 이 시기에 간결한 데이터 구조에 대해 매우 흥미를 느껴 여러 비트벡터 타입과 웨이브렛 매트릭스를 구현하는 Rust 라이브러리를 작성했음
    • 데이터 시각화 관점에서 공간 효율적인 데이터 구조가 클라이언트 측에서 대규모 데이터셋의 상호작용 탐색을 근본적으로 개선할 수 있는지 궁금했음

  • 이 분야에 30년 넘게 있었지만 "간결한 데이터 구조"라는 것을 처음 들어봤음

    • 이 게시물을 보지 않았다면 아마도 알지 못했을 것임
    • 이 데이터 구조가 그래프 처리에 실질적인 응용을 가지고 있다면 중요한 발견일 수 있음
    • 이 주제가 매력적으로 느껴짐

  • 간결한 데이터 구조는 데이터셋이 메모리에 맞는 경우 기존 구조보다 빠르지 않을 수 있음

    • 하지만 대규모 데이터셋에서는 저장소 접근 시간이 지배적이므로 간결한 데이터 구조가 유리함
    • 간결한 트리는 예술 작품과 같음

  • Edward Kmett로부터 간결한 데이터 구조의 개념을 처음 들었음

    • 그는 유명한 Haskell 라이브러리 개발자이며, 오래전에 간결한 데이터 구조에 대한 강연을 했음

  • 간결한 데이터 구조는 매우 재미있음

    • Zig로 이를 구현했으며, 주요 구현은 4비트 미만의 요소를 사용하는 최소 완벽 해시 함수임
    • 이러한 알고리즘을 구현하는 것은 마법과 같음

  • Navarro의 책은 훌륭한 조사서임

    • Erik Demaine의 간결한 데이터 구조에 대한 강의도 훌륭함

  • 간결한 데이터 구조에 대해 아침을 보냈으며, 메모리 효율성이 놀라움

    • 대규모 XML 파일을 분석하는 프로젝트에서 RAM을 많이 소모하고 있음
    • 웨이브렛 매트릭스 개념이 텍스트 중심의 작업에 유망해 보임

  • 대형 구조체의 메모리 내 노드 표현을 효율적으로 만드는 방법이 있음

    • 드물게 사용되는 필드의 오프셋을 할당하고 비트마스크를 사용하여 필드의 존재를 나타냄
    • 마스킹과 popcount는 빠른 접근을 가능하게 함

  • Marisa trie는 매우 멋지고 유용한 간결한 데이터 구조임

    • High Performance Python 책에서도 언급됨

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

답변달기