一連のバイトに使用する最適な圧縮アルゴリズムの決定

Question

私の個人的なプロジェクトのために、かなり曖昧な形式に圧縮したり解凍したりするための小さなクラスを作成しています。仕様はすべて揃っていますが、問題はここではありません。

まず、この「フォーマット」では、6つの異なる圧縮タイプのセットと、バイトデータの非圧縮ブロックを使用します。形式は、RLE、RLEの派生物であり、番号は各バイトをインクリメントします（3、4、5など）、16ビットRLE、LZコピー、逆LZコピー、およびLZコピーXor ' d with255。これは最もクリーンな仕様ではありませんが、私もデザインしませんでした。

私の圧縮ルーチンは、1〜65535バイトの配列を受け取り、（できれば）可能な限り圧縮することを想定しています。これでの私の以前の試みは、非圧縮ストリームのインデックスから始まり、上記の圧縮技術のどれが最良の圧縮を提供するかを計算し、そのメソッドが圧縮バイトの配列に圧縮するが、新しい「非圧縮」インデックス、例：

{0,0,0,1,2,3,4}

アルゴリズムは最初に3つのゼロがあることを読み取り、仕様が使用するRLEエンコーディングを出力し、4番目の要素から開始して、RLEの増分が '1,2をカバーすることを読み取ります、3、4 'で十分であり、それを圧縮してから戻ります。

要約した問題は、使用するのに最適な仕様を見つけようとしている間、小さな（20-30）バイト配列でもルーチンが非常に遅いということです。誰も私がこれを最適化する方法についてのヒントを手伝ってくれますか、または私が助けるために提供できる情報がありますか？

Answer 1

あなたがやろうとしているのは、ファイルのすべての可能なセグメント（可変長の1-64Kブロックセグメントと呼びましょう）に対して多数の圧縮の可能性を考え出すことです。私が間違っている場合は修正しますが、次の選択肢から最初のセグメントに最適な圧縮を行っていますか（方法0は非圧縮です）：

• 圧縮方法0、長さ1バイト。
• 圧縮方法1、長さ1バイト。
• ：：：：：
• 圧縮方法6、長さ1バイト。
• 圧縮方法0、長さ2バイト。
• 圧縮方法1、長さ2バイト。
• ：：：：：
• 圧縮方法6、長さ65534バイト。
• 圧縮方法0、長さ65535バイト。
• 圧縮方法1、長さ65535バイト。
• 圧縮方法2、長さ65535バイト。
• 圧縮方法3、長さ65535バイト。
• 圧縮方法4、長さ65535バイト。
• 圧縮方法5、長さ65535バイト。
• 圧縮方法6、長さ65535バイト。

これには膨大な時間がかかります（セグメントあたり約420,000の圧縮試行）。それがあなたがしていることであれば、単一のセグメントサイズ（64Kなど）を選択し、7つの圧縮方法のそれぞれを適用して最適なものを選択する方が良いでしょう。次に、各セグメントについて、「メソッド」を出力します。バイトの後に圧縮データが続きます。