Compressed data structure とは

圧縮データ構造という用語は、アルゴリズム、データ構造、および理論的コンピュータ科学のコンピュータサイエンスのサブフィールドで発生します。これは、その操作が問題の従来のデータ構造とほぼ同じくらい高速であるが、そのサイズは実質的に小さくてもよいデータ構造を指す。圧縮データ構造のサイズは、典型的には、表現されているデータのエントロピーに大きく依存する。
圧縮データ構造の重要な例には、圧縮サフィックス配列とFMインデックスがあり、どちらもパターンマッチングのために文字Tの任意のテキストを表すことができます。任意の入力パターンPが与えられた場合、それらは、PがT内に現れるかどうかを見つける操作をサポートする。探索時間は、パターンPの長さ、テキストTの長さの非常に遅い関数、報告された一致の数それらが占めるスペースは、部分一致またはgzipによる予測などによって得られるエントロピー圧縮形式のテキストTのサイズにほぼ等しい。さらに、両方のデータ構造は、ランダムアクセス方式でテキストTを再構成することができる点で自己索引付けであり、したがって、基礎となるテキストTを破棄することができる。言い換えれば、それらは同時に、テキストTの圧縮された迅速に検索可能な表現を提供する。それらは、Tのサイズよりも何倍も多くのスペースを占める従来の接尾辞ツリーおよび接尾辞配列よりも大幅な空間改善を表す。逆索引とは対照的に、単語ベースの検索のみをサポートできる任意のパターン。また、逆索引には自己索引付け機能はありません。
関連する重要な概念は、データを表現するのに必要な空間の最悪の概念である情報理論最小値にほぼ​​等しい空間を使用する、簡潔なデータ構造の概念です。対照的に、圧縮されたデータ構造のサイズは、表現される特定のデータに依存する。実際の自然言語テキストの場合のように、データが圧縮可能である場合、圧縮データ構造は、情報理論上の最小値に非常に近く、ほとんどの圧縮方式よりもかなり少ない空間を占有することができる。