簡潔データ構造

ウィキペディア

簡潔データ構造

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/11/26 18:38 UTC 版)

簡潔データ構造 (かんけつデータこうぞう、英: succinct data structure) とは計算機科学の用語で、情報理論的下界に「近い」領域量だけを使いつつ、（他の圧縮形式とは異なり）効率的に質問を受け付けることができるデータ構造を指す。その概念は最初 Jacobson ^[1] によってビット配列（英語版）、木、平面的グラフを符号化するために導入された。通常のロスなしデータ圧縮アルゴリズムとは異なり、簡潔データ構造は事前の展開操作をせずに使用することができる。圧縮データ構造（英語版）は関連する考え方に基づいているが、圧縮データ構造ではデータ構造のサイズは表現しようとする特定のデータに依存する。

あるデータを保持するために必要な情報理論的に最小のビット数が${\displaystyle Z}$