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

嗯，我喜欢一些启发式分析的想法，以尝试提出一些“规则”，以便在结束块时可能是有益的。今晚我会研究你建议的方法，看看我能用它做什么。

与此同时，我突然想到，为了在这个问题上做出充分知情的选择，我需要更好地了解块大小决策的利弊。很快我就知道更小的块可以让你有一个潜在的更好的目标符号字母表——代价是更频繁地定义树的开销增加。较大的块以规模效率对抗其更通用的符号字母表（只有一棵树来存储和解码大量编码数据）。

在我的脑海中，文字代码与长度，距离代码的相对分布是否会对最佳块大小产生特定影响尚不清楚。不过值得深思。

于 2009-01-27T19:58:33.837 回答