About: 簡潔データ構造

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