9

私は小さなサイド プロジェクトとして圧縮ライブラリを作成していますが、十分に進んでいます (私のライブラリは標準の gzip ファイルを抽出し、準拠した (ただし、まだ最適ではない) gzip 出力を生成できます)。意味のあるブロック終了戦略を打ち出します。現在、32k の入力 (LZ77 ウィンドウ サイズ) ごとにブロックを切り取っています。これは、実装が便利で迅速だったからです。今は、圧縮効率を実際に改善しようとしています。

Deflate 仕様には、これについて次のように書かれているだけです。それは役に立ちます。

SharpZipLib コードを並べ替えたところ (これが最も読みやすいオープン ソース実装であることがわかったので)、出力の 16k リテラルごとにブロックを終了し、入力を無視することがわかりました。これを実装するのは簡単ですが、特に仕様の言語が「新鮮なツリーで新しいブロックを開始することが有用であると判断する」ことを考えると、よりターゲットを絞ったアプローチが必要なようです。

新しい戦略のアイデアや、既存の戦略の例を持っている人はいますか?

前もって感謝します！

4

2 に答える 2

2

あなたを動かすための提案として。

優れた圧縮率を示すのに十分なサイズのバッファーを使用した投機的な先読みは、変更する価値があります。

これにより、ストリーミングの動作が変更され (出力が発生する前に、より多くのデータを入力する必要があります)、フラッシュなどの操作が大幅に複雑になります。また、圧縮ステークにかなりの余分な負荷がかかります。

一般的なケースでは、新しいブロックを開始できる各ポイントで分岐し、すべてのルートが使用されるまで必要に応じて両方の分岐を繰り返して、最適な出力が生成されるようにすることができます。入れ子の振る舞いをしたパスが勝ちます。これは、新しいブロックをいつ開始するかの選択が非常にオープンであるため、重要な入力サイズでは実行できない可能性があります。

最小 8K の出力リテラルに制限し、ブロック内の 32K を超えるリテラルを防ぐだけで、投機的アルゴリズムを試すための比較的扱いやすい基盤が得られます。8K をサブブロックと呼びます。

最も単純なものは（疑似コード）です。

create empty sub block called definite
create empty sub block called specChange
create empty sub block called specKeep
target = definite
While (incomingData)
{
  compress data into target(s)    
  if (definite.length % SUB_BLOCK_SIZ) == 0)
  {
    if (targets is definite)
    {
      targets becomes 
        specChange assuming new block 
        specKeep assuming same block as definite
    }        
    else
    {
      if (compression specChange - OVERHEAD better than specKeep)
      {
        flush definite as a block.
        definite = specChange
        specKeep,specChange = empty
        // target remains specKeep,specChange as before 
        but update the meta data associated with specChange to be fresh
      }
      else 
      {
        definite += specKeep
        specKeep,specChange = empty
        // again update the block meta data
        if (definite is MAX_BLOCK_SIZE)
        {
          flush definite
          target becomes definite 
        }
      }
    }
  }
}
take best of specChange/specKeep if non empty and append to definite
flush definite.

OVERHEAD は、ブロックを切り替えるコストを説明する定数です。

これは大まかなものであり、おそらく改善される可能性がありますが、分析の出発点です。切り替えの原因に関する情報を得るためにコードを計測し、それを使用して、変更が有益である可能性がある (おそらく圧縮率が大幅に低下した) というヒューリスティックを判断します。

これにより、ヒューリスティックが妥当と判断した場合にのみ、specChange の構築が行われる可能性があります。ヒューリスティックが強力な指標であることが判明した場合は、投機的な性質を排除し、何があってもその時点で交換することを決定できます。

于 2009-01-27T19:15:05.390 に答える
0

うーん、私はヒューリスティック分析のアイデアが好きで、いつブロックを終了するのが有益であるかについて、いくつかの「ルール」を考え出そうとします。今夜、提案されたアプローチを調べて、それで何ができるかを見ていきます。

それまでの間、この問題について十分な情報に基づいた選択を行うには、ブロック サイズの決定の長所と短所をよりよく理解する必要があることに気づきました。すぐに、ブロックを小さくすると、ターゲットを絞ったシンボル アルファベットを改善できる可能性があることがわかりますが、ツリーを頻繁に定義することでオーバーヘッドが増加します。より大きなブロックは、より一般的なシンボル アルファベットに対抗して、スケールの効率を高めます (大量のエンコードされたデータを格納およびデコードするツリーは 1 つだけです)。

私の頭の上から、リテラルコードと長さ、距離コードの相対的な分布が最適なブロックサイズに特定の影響を与えるかどうかは明らかではありません。しかし、考えるのには良い食べ物です。

于 2009-01-27T19:58:33.837 に答える