アーカイブ内のランダムアクセスを適切にサポートする圧縮形式?

https://stackoverflow.com/questions/429987

07-07-2019
|

質問

これは次のようなものです前の質問, 、しかし、そこにある答えは私のニーズを満たしておらず、私の質問は少し異なります。

現在、ソートされたデータを含むいくつかの非常に大きなファイルに対して gzip 圧縮を使用しています。ファイルが圧縮されていない場合、バイナリ検索は、並べ替えられたデータ内の場所の検索をサポートする便利で効率的な方法です。

ただし、ファイルが圧縮されている場合は問題が発生します。最近知ったのですが、ズリブさんの Z_FULL_FLUSH このオプションは、圧縮中に使用して、圧縮出力に「同期ポイント」を挿入できます (inflateSync() その後、ファイル内のさまざまなポイントから読み取りを開始できます)。これは問題ありませんが、この機能を追加するには、すでに所有しているファイルを再圧縮する必要があります (そして奇妙なことに gzip これを行うオプションはありませんが、必要に応じて独自の圧縮プログラムを作成するつもりです)。

からのようです一つの情報源それさえ Z_FULL_FLUSH これは完璧な解決策ではありません...すべての gzip アーカイブでサポートされているわけではないだけでなく、アーカイブ内の同期ポイントを検出するという考え方自体が誤検知を引き起こす可能性があります (同期ポイントのマジックナンバーとの一致、または事実により)それ Z_SYNC_FLUSH 同期ポイントも生成されますが、ランダムアクセスには使用できません)。

もっと良い解決策はありますか?可能であれば、インデックス作成用の補助ファイルの使用は避けたいと思っています。また、準ランダムアクセスに対する明示的なデフォルトサポートが役立つと思います (10 MB 間隔ごとに読み取りを開始できるなど、粒度が大きい場合でも)。gzip よりもランダム読み取りをサポートする別の圧縮形式はありますか?

編集:先ほども述べたように、圧縮データに対して二分探索をしたいと考えています。特定の (非圧縮) 位置をシークする必要はありません。圧縮ファイル内である程度の粗い粒度でシークするだけです。「この圧縮ファイルの途中のおよそ 50% (25%、12.5% など) からデータを解凍する」ようなことのサポートが欲しいだけです。

解決

非圧縮データの特定の場所へのランダムアクセスをサポートする圧縮ファイル形式はわかりませんが（マルチメディア形式を除く）、独自の形式を作成できます。

たとえば、bzip2圧縮ファイルは、サイズが<！> lt; 1MBの独立した圧縮ブロックで構成されており、マジックバイトのシーケンスで区切られているため、bzip2ファイルを解析し、ブロック境界を取得してから解凍するだけです右のブロック。これには、ブロックの開始位置を記憶するためのインデックスが必要になります。

それでも、最良の解決策は、ファイルを選択したチャンクに分割し、アーカイブ内の個々のファイルへのランダムアクセスをサポートするzipやrarなどのアーカイバで圧縮することだと思います。

他のヒント

dictzip をご覧ください。 gzipと互換性があり、粗いランダムアクセスが可能です。

マニュアルページからの抜粋：

dictzip は、 gzip （1）アルゴリズム（LZ77）を使用してファイルを圧縮します。 gzipファイル形式と完全に互換性があります。 gzipの拡張ファイル形式（Extra Field、RFC 1952の2.3.1.1で説明）は、追加のデータを許可します圧縮ファイルのヘッダーに保存されます。 gzipやzcatなどのプログラムこの余分なデータは無視されます。ただし、[dictzcat --start]は使用しますこのデータを使用して、ファイルに対して擬似ランダムアクセスを実行します。

Ubuntuにはdictzipパッケージがあります。または、そのソースコードは dictd-*。tar.gz にあります。そのライセンスはGPLです。自由に勉強できます。

更新：

dictzipを改善して、ファイルサイズの制限がないようにしました。私の実装はMITライセンスの下です。

.xzファイル形式（LZMA圧縮を使用）はこれをサポートしているようです：

ランダムアクセス読み取り：データは、独立して圧縮されたブロックに分割できます。すべての.xzファイルにはブロックのインデックスが含まれているため、ブロックサイズが十分に小さい場合にランダムアクセスの読み取りが制限されます。

これで目的に十分です。欠点は、liblzmaのAPI（これらのコンテナーと対話するための）が十分に文書化されていないようであるため、ブロックにランダムにアクセスする方法を見つけるのに多少の努力が必要な場合があることです。

gzipおよびbzip2アーカイブへのランダムアクセスを提供するソリューションがあります：

gzip zran。 c ghostscriptソースコードから
bzip2 Same-bzip by James Taylor

（ 7zip用のものを探しています）

bgzipは、インデックス可能なgzipバリアントでファイルを圧縮できます（tabixで解凍できます）。これは、<=>インデクサーとともに、一部のバイオインフォマティクスアプリケーションで使用されます。

こちらの説明をご覧ください： http：// blastedbio .blogspot.fr / 2011/11 / bgzf-blocked-bigger-better-gzip.html 、およびここ： http://www.htslib.org/doc/tabix.html 。

他のアプリケーションにどの程度適応できるかわかりません。

これがあなたの正確な状況で実用的かどうかわかりませんが、大きなファイルをそれぞれ小さなファイル、たとえばそれぞれ10 MBにgzipすることはできませんか？最終的には、file0.gz、file1.gz、file2.gzなどの一連のファイルになります。元のラージ内の特定のオフセットに基づいて、"file" + (offset / 10485760) + ".gz"という名前のファイルを検索できます。非圧縮アーカイブ内のオフセットはoffset % 10485760です。

ロスレス圧縮は、一部の領域で他の領域よりもうまく機能するため、圧縮データを適切な長さのBLOCKSIZEのブロックに保存すると、各ブロックの圧縮バイト数はまったく同じですが、一部の圧縮ブロックは他のブロックよりもはるかに長いプレーンテキストに拡張されます。

あなたは <！> quot; Compression：A Generation Key for Next-Generation Text Retrieval Systems <！> quot; Nivio Ziviani、Edleno Silva de Moura、Gonzalo Navarro、Ricardo Baeza-Yates に コンピュータマガジン2000年11月 http://doi.ieeecomputersociety.org/10.1109/2.881693

それらのデコンプレッサは、圧縮されたデータの1、2、または3バイト全体を取得し、（語彙リストを使用して）単語全体に解凍します。圧縮されたテキストで単語やフレーズを直接検索できますが、非圧縮テキストを検索するよりもさらに高速であることがわかりました。

これらの解凍プログラムを使用すると、テキスト内の任意の単語を通常の（バイト）ポインターでポイントし、そのポイントからすぐに解凍を開始できます。

テキストにはおそらく65,000未満の一意の単語があるため、すべての単語に一意の2バイトコードを付けることができます。（KJV聖書にはほぼ13,000のユニークな単語があります）。 65,000を超える単語がある場合でも、最初の256個の2バイトコード<！> quot; words <！> quot;を割り当てるのは非常に簡単です。すべての可能なバイトまで、65,000程度の<！> quot;最も頻繁に使用される単語とフレーズ<！> quot;の辞書にない単語を綴ることができます。（頻繁な単語やフレーズを2バイトにパックすることで得られる圧縮通常は<！> quot; expansion <！> quot;の価値があります。 1文字につき2バイトを使用して単語を時々綴る）。 <！> quot;頻出する単語やフレーズ<！> quot;の辞書を選択するには、さまざまな方法があります。それは適切な圧縮を提供します。たとえば、LZWコンプレッサーを調整して<！> quot; phrases <！> quot;をダンプできます。フレーズごとに1行のレキシコンファイルを複数回使用し、すべてのデータに対して実行します。または、非圧縮データをレキシコンファイルの5バイトフレーズに、フレーズごとに1行ずつ任意に切り分けることもできます。または、非圧縮データを実際の英語の単語に切り刻み、単語の先頭のスペースを含む各単語をレキシコンファイルに入れることもできます。次に<！> quot; sort --unique <！> quot;を使用します。そのレキシコンファイル内の重複する単語を削除します。（完全な<！> quot; optimum <！> quot;語彙の単語リストを選択しても、NP困難と見なされますか？）

巨大な圧縮ファイルの先頭にレキシコンを保存し、便利なBLOCKSIZEになるまでパディングしてから、圧縮テキスト（一連の2バイトの<！> quot; words <！> quot; -そこからファイルの終わりまで。おそらく、検索者はこのレキシコンを一度読み取って、解凍中にRAM内のデコード可能なクイック形式で保持し、<！> quot; 2バイトコード<！> quot;の解凍を高速化します。 <！> quot;可変長フレーズ<！> quot; 最初のドラフトはフレーズリストごとに1行のシンプルなものから始まりますが、後でインクリメンタルコーディングまたはzlibを使用して、より圧縮された形式でレキシコンを保存するように切り替えることができます。

圧縮テキストへのランダムな偶数バイトオフセットを選択し、そこから圧縮解除を開始できます。粒度の細かいランダムアクセス圧縮ファイル形式を作成することは不可能だと思います。

2つの可能な解決策：

すべてのテキストファイルを含む圧縮ファイルシステム（SquashFS、clicfs、cloop、cramfs、e2comprなど）をOSが圧縮に対処してマウントし、アプリケーションプログラムでの圧縮については何もしない。
ファイルシステムイメージを圧縮する代わりに、各テキストファイルで直接clicfsを使用します（テキストファイルごとに1つのclicfs）。 <！> quot; mkclicfs mytextfile mycompressedfile <！> quot;を考えてください。 <！> quot; gzip <！> lt; mytextfile <！> gt; mycompressedfile <！> quot;および<！> quot; clicfs mycompressedfile directory <！> quot;ファイル<！> quot; directory / mytextfile <！> quot;を介してデータにランダムにアクセスする方法として。

まだ言及されたかどうかはわかりませんが、Kiwix プロジェクトはこの点で素晴らしい仕事をしました。彼らは、プログラム Kiwix を通じて、ZIM ファイルアーカイブへのランダムアクセスを提供しています。圧縮も良好です。このプロジェクトは、Wikipedia のオフラインコピーの需要があったときに始まりました (すべてのメディアを含めると、非圧縮形式で 100 GB 以上に達しました)。彼らは、25 GB のファイル (ほとんどのメディアを含まないウィキペディアの単一ファイルの具体化) を取得し、それをわずか 8 GB の zim ファイルアーカイブに圧縮することに成功しました。また、Kiwix プログラムを使用すると、ネットサーフィンよりも速く、Wikipedia の任意のページとすべての関連データを呼び出すことができます。

Kiwix プログラムはウィキペディアのデータベース構造をベースにしたテクノロジーですが、優れた圧縮率とランダムアクセスを同時に実現できることが証明されています。

これは非常に古い質問ですが、 zindex は良い解決策を提供できるようです（ただし、あまり経験がありません）

razipは、このサポートのために調整する必要があるgzip / bzip2よりも優れたパフォーマンスでランダムアクセスをサポートします-<！> quot; ok <！> quot;を犠牲にして圧縮を削減します。ランダムアクセス：

http://sourceforge.net/projects/razip/

私は、特定の種類の生物学的データを圧縮するためのオープンソースツールの著者です。 starchと呼ばれるこのツールは、染色体ごとにデータを分割し、それらの区分をインデックスとして使用して、より大きなアーカイブ内の圧縮データユニットに高速でアクセスします。

染色体ごとのデータは、ゲノム座標の冗長性を除去するために変換され、変換されたデータはbzip2またはgzipアルゴリズムで圧縮されます。オフセット、メタデータ、および圧縮されたゲノムデータは1つのファイルに連結されます。

ソースコードは、 GitHub サイトから入手できます。 LinuxおよびMac OS Xでコンパイルしました。

あなたの場合、ヘッダーにカスタムアーカイブ形式のオフセット（10 MBなど）を保存できます。ヘッダーを解析し、オフセットを取得し、fseek + current_offset_sumによってファイルをインクリメンタルにheader_sizeします。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow