簡潔な（Succinct）データ構造

• パフォーマンス最適化のために論文を読んでいる中で、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ビット 程度まで圧縮して保存できる
• 例の木構造:

   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]

Wavelet を活用した圧縮構造は Djvu で標準として広く使われています。画像圧縮は本当に素晴らしいですね。

[GN⁺]

Hacker Newsの意見

• Gonzalo Navarro にメールを送って質問したところ、その結果として一緒に論文を書くことになった

  • 彼の別の論文では、いくつかのエレガントなアイデアを組み合わせて、ビットベクタの rank/select のシンプルな実装を扱っている
  • この時期に簡潔データ構造に非常に興味を持ち、複数のビットベクタ型と wavelet matrix を実装する Rust ライブラリを書いた
  • データ可視化の観点から、省メモリなデータ構造がクライアント側で大規模データセットのインタラクティブな探索を根本的に改善できるのか気になっていた

• この分野に30年以上いるが、「簡潔データ構造」というものを初めて聞いた

  • この投稿を見ていなければ、おそらく知ることはなかっただろう
  • もしこのデータ構造がグラフ処理に実用的な応用を持つなら、重要な発見になり得る
  • この話題は魅力的に感じる

• 簡潔データ構造は、データセットがメモリに収まる場合には従来の構造より速くないかもしれない

  • しかし大規模データセットではストレージアクセス時間が支配的になるため、簡潔データ構造の方が有利になる
  • 簡潔木は芸術作品のようだ

• Edward Kmett から簡潔データ構造という概念を初めて聞いた

  • 彼は有名な Haskell ライブラリ開発者で、かなり前に簡潔データ構造について講演していた

• 簡潔データ構造はとても面白い

  • Zig でこれを実装しており、主な実装は 4 ビット未満の要素を使う最小完全ハッシュ関数だ
  • こうしたアルゴリズムを実装するのは魔法のようだ

• Navarro の本は素晴らしい概説書だ

  • Erik Demaine の簡潔データ構造に関する講義も素晴らしい

• 簡潔データ構造について朝の時間を費やしたが、そのメモリ効率には驚かされた

  • 大規模な XML ファイルを解析するプロジェクトで RAM を大量に消費している
  • wavelet matrix の概念は、テキスト中心の作業に有望そうに見える

• 大きな構造体のメモリ内ノード表現を効率化する方法がある

  • めったに使われないフィールドにオフセットを割り当て、ビットマスクを使ってフィールドの存在を示す
  • マスキングと popcount により高速なアクセスが可能になる

• Marisa trie はとてもクールで便利な簡潔データ構造だ

  • High Performance Python という本でも触れられている

• 簡潔データ構造のための私の基本ライブラリは SDSL-Lite だ