圧縮データ構造

圧縮データ構造という用語は、アルゴリズム、データ構造、および理論計算機科学のコンピュータ サイエンスのサブフィールドで使用されます。これは、問題に対する従来のデータ構造とほぼ同じ速度で操作でき、サイズを大幅に小さくできるデータ構造を指します。圧縮データ構造のサイズは、通常、表現されるデータの情報エントロピーに大きく依存します。

圧縮データ構造の重要な例としては、圧縮サフィックス配列^{[1] [2]}とFM インデックス^[3]があり、どちらもパターンマッチングのために任意の文字のテキストTを表すことができます。任意の入力パターンP が与えられると、これらはPがTに現れるかどうか、またどこに現れるかを検索する操作をサポートします。検索時間は、パターンPの長さ、テキストTの長さの非常に緩やかな増加関数、および報告された一致の数の合計に比例します。これらが占めるスペースは、部分一致による予測やgzipによって得られるものなど、エントロピー圧縮された形式のテキストTのサイズとほぼ等しくなります。さらに、両方のデータ構造は自己インデックスであり、ランダムアクセス方式でテキストT を再構築できるため、基になるテキストT を破棄できます。言い換えると、これらは同時に、テキストTの圧縮され、すばやく検索可能な表現を提供します。これらは、 Tのサイズよりも何倍も多くのスペースを占める従来の接尾辞ツリーと接尾辞配列に比べて、大幅なスペースの改善を表しています。また、単語ベースの検索しかサポートできない転置インデックスとは対照的に、任意のパターンの検索もサポートしています。さらに、転置インデックスには自己インデックス機能がありません。

関連する重要な概念として、簡潔なデータ構造があります。これは、情報理論の最小値とほぼ等しいスペースを使用します。これは、データを表すために必要なスペースの最悪のケースの概念です。対照的に、圧縮されたデータ構造のサイズは、表現される特定のデータによって異なります。データが圧縮可能である場合 (自然言語テキストの場合に実際によくあることですが)、圧縮されたデータ構造は、情報理論の最小値に非常に近いスペースを占めることができ、ほとんどの圧縮方式よりも大幅に少ないスペースを占めることができます。^{[例が必要] [引用が必要]}