元のデータのオフセットからデータを即座に解凍しますか？

Question

私は、可変サイズのC構造体を圧縮したいというデータブロックを持っています。私はデータを圧縮したいが、データ全体を圧縮解除することなく、アプリケーションコード内でその場で構造体の特定のフィールドにアクセスしたい。

オフセット（元のデータの場合）を取り、データを解凍して返すアルゴリズムがありますか？

Answer 1

圧縮方法は、一般に、上記のデータを使用して圧縮を行います。圧縮データのどの時点でも、後に続くものを圧縮解除するには、少なくとも前回の圧縮されていないデータの量を知る必要があります。

圧縮データ内の選択ポイントで意図的に履歴を忘れて、それらのポイントでランダムアクセスすることができます。これにより、いくらかの圧縮が削減されますが、十分に離れたランダムアクセスポイントでは、圧縮が小さくなる可能性があります。単純なアプローチは、gzipでピースを圧縮し、gzipストリームを連結し、各ストリームのオフセットの記録を保持することです。オーバーヘッドが少ない場合は、zlibのZ_FULL_FLUSHを使用して同じことを行うことができます。

また、各ランダムアクセスポイントの履歴を別々のファイルに保存することもできます。このようなランダムアクセスインデックスをzlibまたはgzipストリームに作成する例は、zran.cにあります。

単純なハフマンコーディングのように、解凍のための以前の履歴に依存しない圧縮方法を構築できます。ただし、圧縮率は、以前の履歴に依存する方法と比較して劣ります。

Answer 2

圧縮ファイルシステムの例：ディスクに書き込む前に発生する圧縮について知る必要のないファイルシステムAPIがあります。そこにはいくつかのアルゴリズムがあります。 詳細はhereをご確認ください。

しかし、使用したデータ構造を最適化しようとすると、圧縮する必要はありません。 効率的なアクセスのためにはインデックスが必要です。したがって、配列とマルチマップとスパース配列の間には、データを効率よく表現するために、さらなる圧縮の必要がないというデータをモデル化する方法があるはずです。 もちろん、これはかなり曖昧なユースケースに大きく依存します。

データにアクセスするために圧縮レイヤーが必要なユースケースは想像することができますが、問題を解決するためのより良い方法がある可能性があります。