簡潔データ構造

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