問題タブ [bzip2]

解凍速度が最も速いbzip2の実装はどれですか？

http://bitbucket.org/james_taylor/seek-bzip2/src/tip/micro-bunzip.cが主張しています

Manuel Novoa III（mjn3@codepoet.org）によるサイズと速度の最適化。ハフマンコードのより効率的な読み取り、合理化されたread_bunzip（）関数、およびその他のさまざまな調整。（制限付き）テストでは、x86のbzcatよりも約20％速く、armの場合は約10％速くなります。時間の約2/3がread_unzip（）でBurrows-Wheeler変換を逆にするのに費やされていることに注意してください。その時間の多くは、キャッシュミスに起因する遅延です。

多くのキャッシュミスは、いくつかの手法によって最適化される可能性があるため、さらに高速な実装が可能です。

これ（seek-bzip2）には、入力ファイルで簡単に検索できるという興味深い機能もあります。

私のプログラムはbzip2の出力を消費し、（理論的には）ファイルのさまざまな部分でこれを並行して実行できます。したがって、並列bzip2実装も考慮されます。

ありがとう。

高速な MTF ( http://en.wikipedia.org/wiki/Move-to-front_transform ) の場合、文字を配列内から配列の前に移動する高速バージョンが必要です。

cachegrind が示しているように、memmove では多くの分岐予測ミスが発生しています。

他のバージョンのコード (最初の例の memmove ではなく、これ)

多くのバイト読み取り/書き込み、条件付き分岐、分岐予測ミスがあります

i は、「適切な」入力に使用される MTF であるため、それほど大きくはありません。BWT (Burrows–Wheeler 変換) 後のテキスト ファイルです。

コンパイラはGCCです。

.tarファイルにはディレクトリやその他のファイルが含まれており、.bz2はbzip2圧縮で圧縮されたファイルであると理解しています。

したがって、bzip2圧縮を使用するほとんどのtarballは次のように終わります。

これは、tarballに適用されるbzip2圧縮です。

ただし、Mercurial Webサーバーからソースコードをダウンロードするときはいつでも、次のいずれかから取得した内部コードをダウンロードします。

またはBitBucketから、で終わるものを取得します

複数のファイルにbzip2圧縮を適用することはできないため、これは私には意味がありません。そのため、最初にそれらを「tar」する必要があります。

これはMercurialのバグですか？それとも、これは私のWebブラウザのバグですか（WindowsではGoogle Chromeを、UbuntuではFirefoxを試しました）？それとも、これは奇妙なことですが、違いはありませんか？

私がダウンロードした最新のソースは、Mercurialブックのリポジトリであるhttp://bitbucket.org/bos/hgbookからのものでした。

データベースにクエリを実行し、Python を使用して結果をアーカイブしています。ログ ファイルに書き込むときにデータを圧縮しようとしています。しかし、私はそれでいくつかの問題を抱えています。

私のコードは次のようになります。

ただし、出力ファイルのサイズは 1,409,780 です。このファイルで実行bunzip2すると、ファイルのサイズは 943,634 になり、そのファイルで実行すると、サイズは 217,275 になりbzip2ます。つまり、圧縮されていないファイルは、Python の bzip コーデックを使用して圧縮されたファイルよりも大幅に小さくなります。 コマンドラインで実行する以外に、これを修正する方法はありますか?bzip2

問題が解決するかどうかを確認するために、Python の gzip コーデック (行を に変更codecs.open(archive_file, 'a+', 'zip')) を試しました。まだ大きなファイルを取得できますがgzip: archive_file: not in gzip format、ファイルを解凍しようとするとエラーも発生します。 何が起こっているのですか？

EDIT：私は元々、ファイルを書き込みモードではなく追加モードで開いていました。これは問題になる場合とそうでない場合がありますが、ファイルが 'w' モードで開かれている場合でも問題は残ります。

いくつかのbzip2アーカイブで構成された連結ファイルがあります。bzip2また、そのファイル内の個々のチャンクのサイズも知っています。

bzip2個々の bzip2 データ チャンクからストリームを解凍し、出力を標準出力に書き込みたいと考えています。

まずfseek、ファイル カーソルを目的のアーカイブ バイトに移動してから、ファイルの「サイズ」チャンクをBZ2_bzRead呼び出しに読み込みます。

fprintf問題は、ステートメントの出力とコマンド ラインで実行した出力を比較すると、bzip22 つの異なる答えが得られることです。

bzip2具体的には、このコードから得られる出力は、コマンド ラインで実行した場合よりも少なくなります。

より具体的には、このコードからの出力は、コマンド ライン プロセスからの出力の小さなサブセットであり、対象の bzip2 チャンクの末尾にあるものを見逃しています。

コマンドラインbzip2が正しい答えを提供していることを別の手法で確認しました。そのため、C コードの問題により、チャンクの最後の出力が失われています。その問題が何であるかはわかりません。

bzip2またはに精通している場合はlibbzip2、上記のコード サンプルで間違っている点について何かアドバイスをいただけますか? アドバイスありがとうございます。

bzip2Cアプリケーション内のストリームからデータをプルしています。データのチャンクがデコンプレッサから出てくるので、それらは以下に書き込むことができますstdout：

これはうまくいきます。に送信されると、すべてのデータを取得しstdoutます。

に書き込む代わりにstdout、このステートメントからの出力を1行のチャンクで内部的に処理したいと思います。改行文字で終了する文字列です\n。

デコンプレッサストリームの出力を、改行に達するまで一度に1文字ずつ別のバッファに書き込んでから、行ごとの処理関数を呼び出しますか？これは遅いですか、よりスマートなアプローチがありますか？アドバイスありがとうございます。

編集

あなたの提案をありがとう。最終的に、出力バッファーに相当するデータを通過するたびに、短い行バッファーの先頭に残り（出力バッファーの最後にある「スタブ」）を格納するバッファーのペアを作成しました。

出力バッファを1文字ずつループし、改行に相当するデータを一度に処理します。改行のない余りが割り当てられて割り当てられ、次のストリームのラインバッファにコピーされます。繰り返されるステートメントreallocよりも安価なようです。malloc-free

これが私が思いついたコードです：

皆様のご協力に心より感謝申し上げます。これはうまく機能しています。

私は共有ホスティングを利用していますが、PHPにbzip2が含まれていないことに気付きました。これを使用するには、PHPを再コンパイルする必要があるようです。共有ホスティングでこれが可能になるとは思わないので、私の状況やbzip2に代わるものはありますか？

Bzip2 アーカイブを作成する必要があります。「Apache ant」からダウンロードした bzip2 ライブラリ。

（使い方の例が見つからなかったので、このように使うことにしました）

ただし、ディスク上に破損したアーカイブが作成されます。

James Taylor の優れた小さな「seek-bzip2」を Windows でコンパイルできませんか? bzip2 アーカイブのインデックスを作成し、そのインデックスを使用して、アーカイブの個々のブロックへのランダム アクセスを提供できます。

これは C で書かれており、64 ビット長の long が必要で、http: //bitbucket.org/james_taylor/seek-bzip2から入手できます。

無料の Windows C コンパイラでコンパイルすることができません。

• Borland には、必要なヘッダー ファイルがいくつかありません。
• lcc はそれをコンパイルしますが、どの bzip2 ファイルでも「予期しない EOF」で失敗します。
• 「-m64」フラグを削除すると、mingw はコンパイルしますが、上記の lcc と同じように失敗します。

無料のコンパイラはデバッグをあまりサポートしていないようで、MS Visual Studio はリムーバブル ハード ドライブへのインストールを拒否し、ネットブックの C および D ドライブには十分な容量がありません。

編集誰かに移植を依頼していたので、この質問を言い換えましたが、喜んで自分で移植してみます。どこから始めたらいいのかわからない。64 ビット型が一般的になる前から、C には触れていません。

圧縮されたbzip2アーカイブのCRC32チェックサムを計算/検証しようとしています。

http://en.wikipedia.org/wiki/Bzip2

したがって、CRCチェックサムがbz2ファイルのどこにあるかはわかっていますが、それらを検証するにはどうすればよいでしょうか。binascii.crc32()両方のCRCを取得するには、どのチャンクが必要ですか？さまざまなチャンクのCRCをバイトごとに計算しようとしましたが、一致するものを取得できませんでした。

ありがとうございました。特にメソッドで何かを見つけるために、bzip2ソースとbz2Pythonライブラリコードを調べます。decompress()

アップデート1：

私が見る限り、ブロックヘッダーは次のタグで識別されます。ただし、小さなbz2ファイルにはENDMARKファイルが含まれていません。（adwのおかげで、圧縮データはバイトに埋め込まれていないため、ENDMARKのビットシフト値を探す必要があることがわかりました。）

これはbzlib2recover.cソースからのものであり、ブロックは常にCRCチェックサムの直前のビット80で開始するようです。これは、CRC計算から除外する必要があります。これは、自身のCRCを同じCRCにすることはできないためです（私のポイントを取得します） 。

これを計算するコードを調べます。

アップデート2：

bzlib2recover.cCRC計算機能はなく、破損したファイルからCRCをコピーするだけです。ただし、Pythonでブロック計算機能を複製して、bz2圧縮ファイル内の各ブロックの開始ビットと終了ビットをマークアウトすることができました。compress.c軌道に戻ると、それはの定義のいくつかを参照していることがわかりましたbzlib_private.h。

これらの定義はによってもアクセスさbzlib.cれ、s->blockCRCで初期化および更新されbzlib.c、でファイナライズされcompress.cます。2000行を超えるCコードがあり、何が入っているのか、何が入っていないのかを調べて理解するのに時間がかかります。C質問にもタグを追加しています。

ちなみに、bzip2のCソースは次のとおりですhttp://www.bzip.org/1.0.6/bzip2-1.0.6.tar.gz

アップデート3：

ブロックCRC32bzlib2は、次のアルゴリズムを使用して計算されていることがわかります。

dataInエンコードするデータです。

BZ2_crc32Tableが定義されている場所crctable.c

dataIn = "justatest"返されるCRCは、その7948C8CBデータでテキストファイルを圧縮しているため、bz2ファイル内のcrc：32チェックサム79 48 c8 cbは一致します。

結論：

bzlib2 CRC32は（引用符crctable.c）

comp.compression FAQのセクション51にある、RobWarnockによるコードから漠然と派生しています...

...したがって、私が理解している限り、標準のCRC32チェックサム計算機を使用して事前計算/検証することはできませんが、bz2lib実装が必要です（の155〜172行目bzlib_private.h）。