簡潔データ構造
簡潔データ構造 (かんけつデータこうぞう、英: succinct data structure) とは計算機科学の用語で、情報理論的下界に「近い」領域量だけを使いつつ、(他の圧縮形式とは異なり)効率的に質問を受け付けることができるデータ構造を指す。その概念は最初 Jacobson によってビット配列(英語版)、木、平面的グラフを符号化するために導入された。通常のロスなしデータ圧縮アルゴリズムとは異なり、簡潔データ構造は事前の展開操作をせずに使用することができる。圧縮データ構造(英語版)は関連する考え方に基づいているが、圧縮データ構造ではデータ構造のサイズは表現しようとする特定のデータに依存する。
あるデータを保持するために必要な情報理論的に最小のビット数が Z {\displaystyle Z} だとする。このデータの表現形式は、
Z + O ( 1 ) {\displaystyle Z+O(1)} ビットの領域を必要とする場合、implicit(英語版)、
Z + o ( Z ) {\displaystyle Z+o(Z)} ビットの領域を必要とする場合、簡潔 (succinct)、
O ( Z ) {\displaystyle O(Z)} ビットの領域を必要とする場合、コンパクト (compact)
であると呼ばれる。
implicit データ構造は通常、なんらかの順列を用いて情報を保持することに帰着される。よく知られる事例としてはヒープが挙げられる。