ファイルのランダムな読み取り/書き込みを可能にする最適な圧縮アルゴリズムは何ですか?
適応圧縮アルゴリズムが問題外であることはわかっています。
そして、ハフマンエンコーディングが問題外であることは知っています。
ランダムな読み取り/書き込みを可能にする、より優れた圧縮アルゴリズムを持っている人はいますか?
ブロックで記述すれば、任意の圧縮アルゴリズムを使用できると思いますが、理想的には、一度にブロック全体を解凍する必要はありません。しかし、これを行う簡単な方法とブロック境界を知る方法について提案がある場合は、お知らせください。これが解決策の一部である場合は、読み取りたいデータがブロック境界をまたいでいる場合の対処方法も教えてください。
あなたの回答の文脈では、問題のファイルが100GBであると仮定してください。最初の10バイトを読みたい場合もあれば、最後の19バイトを読みたい場合もあり、17バイトを読みたい場合もあります真ん中のバイト。.
そんなことはありえないとほのめかす回答の多さに唖然とします。
これらの人々は、1993 年に Microsoft が圧縮ファイル システム技術をめぐって Stac Electronics によって訴えられる前から存在していた「圧縮ファイル システム」について聞いたことがありませんか?
LZSとLZJBは、ランダムアクセス読み取りとランダムアクセス書き込みの両方を必然的に必要とする圧縮ファイルシステムを実装する人々に人気のあるアルゴリズムであると聞いています。
おそらく、最も簡単で最善の方法は、そのファイルのファイル システム圧縮をオンにして、OS に詳細を処理させることです。ただし、どうしても手動で処理したい場合は、NTFS の透過的なファイル圧縮に関する記事を読んでヒントを得ることができます。
また、 「StackOverflow: アーカイブ内のランダム アクセスを適切にサポートする圧縮形式はありますか?」も参照してください。
razip 形式は、このサポートのために微調整する必要がある gzip/bzip2 よりも優れたパフォーマンスでランダム アクセス読み取りをサポートします。
スティーブン・デンネはここで何かをしているのではないかと思います。想像：
プラスの効果の1つは、辞書がファイル全体に適用されることです。CPUサイクルを節約できる場合は、「ファイル」境界と重複するシーケンスを定期的にチェックしてから、それらを再グループ化することができます。
このアイデアは、真にランダムな読み取り用です。固定サイズのレコードのみを読み取る場合は、このアイデアの一部が簡単になる可能性があります。
各ディクショナリ エントリのコードが同じサイズでエンコードされているディクショナリ ベースの圧縮方式では、コード サイズの任意の倍数で読み取りを開始できるようになり、コードがコンテキストを使用しない場合は、書き込みと更新が容易になります。 /隣人。
エンコーディングにコードの開始または終了を区別する方法が含まれている場合、コードが同じ長さである必要はなく、ファイルの途中のどこからでも読み取りを開始できます。この手法は、ストリーム内の不明な位置から読み取る場合により便利です。
圧縮とは、データから冗長性を取り除くことです。残念ながら、冗長性がファイル全体に単調に均等に分散される可能性は低く、それが圧縮ときめの細かいランダム アクセス を期待できる唯一のシナリオです。
ただし、圧縮中に作成された外部リストを維持することで、ランダムアクセスに近づけることができます。これは、圧縮されていないデータストリーム内の選択されたポイントと圧縮されたデータストリーム内のそれらの位置との対応を示しています。明らかに、ソース ストリームとその圧縮バージョンの間の変換スキームがストリーム内の場所によって変化しない方法を選択する必要があります (つまり、LZ77 または LZ78 ではありません。代わりに、おそらく Huffman または byte-明らかに、これは多くのオーバーヘッドを招きます。また、「ブックマーク ポイント」に必要なストレージ スペースと、ストリームを圧縮解除するために必要なプロセッサ時間との間でどのようにトレードオフするかを決定する必要があります。データを取得するためのブックマーク ポイント
ランダムアクセス書き込みに関しては... それはほとんど不可能です。すでに述べたように、圧縮とはデータから冗長性を取り除くことです。冗長であったために圧縮された可能性のあるデータを、同じ冗長性を持たないデータで置き換えようとすると、単純に収まりません。
ただし、実行するランダムアクセス書き込みの量によっては、圧縮後にファイルに書き込まれたすべてのデータを表す疎行列を維持することで、それをシミュレートできる場合があります。すべての読み取りで、マトリックスをチェックして、圧縮後に書き込んだ領域を読み取っていたかどうかを確認します。そうでない場合は、データの圧縮ファイルに移動します。
ランダムな読み取りを許可する圧縮アルゴリズムは知りません。ランダムな書き込みは気にしません。そのような機能が必要な場合は、ファイルを全体ではなくチャンクで圧縮することをお勧めします。
例:
最初に読み取り専用のケースを見ていきます。ファイルを 8K のチャンクに分割するとします。各チャンクを圧縮し、圧縮された各チャンクを順番に保存します。圧縮された各チャンクが保存されている場所とその大きさを記録する必要があります。次に、オフセット O から始まる N バイトを読み取る必要があるとします。それがどのチャンク (O / 8K) にあるかを把握し、そのチャンクを解凍してそれらのバイトを取得する必要があります。必要なデータは複数のチャンクにまたがる可能性があるため、そのシナリオに対処する必要があります。
圧縮ファイルに書き込めるようにしたい場合、事態は複雑になります。圧縮されたチャンクが大きくなったり小さくなったりすることに対処する必要があります。拡張する場合に備えて、各チャンクに追加のパディングを追加する必要がある場合があります (圧縮されていない場合でも同じサイズですが、異なるデータは異なるサイズに圧縮されます)。圧縮されたデータが大きすぎて元のスペースに収まらない場合は、チャンクを移動する必要さえあるかもしれません。
これは基本的に、圧縮ファイル システムがどのように機能するかです。ファイルのファイルシステム圧縮をオンにして、通常どおり読み書きする方がよい場合があります。