在deflate算法中，确定块大小的一些好策略是什么？

Question

我正在编写一个压缩库作为一个小的副业项目，目前已经完成了一定进展（我的库可以提取任何标准gzip文件，并生成符合规范（但肯定不是最优）的gzip输出），现在是时候想出一个有意义的块终止策略了。目前，我只是在每32k输入（LZ77窗口大小）后截断块，因为这样做方便且实现迅速 - 现在我正在回头尝试实际提高压缩效率。

关于此，Deflate规范只有这么说：“当压缩器确定使用新的树开始新块或者块大小填满压缩器的块缓冲区时，它会终止一个块”，这并没有什么帮助。

我研究了SharpZipLib代码（因为我认为它是最易于阅读的开源实现），发现它忽略输入，每16k输出文字时终止一个块。这很容易实现，但似乎必须有一些更针对性的方法，特别是考虑到规范中的语言“确定使用新的树开始新块是否有用”。

那么，有人有新策略的想法或现有策略的例子吗？

提前感谢！

- David Hay

Answer 1

作为一个启示，以下是一些内容。

为了表明更优压缩的改变值得实施，需要预留足够大的缓冲区进行猜测性展望。

这会改变流媒体行为（在输出之前需要输入更多数据），并且会显著增加压缩负担，从而使操作如flush变得更加复杂。

在一般情况下，可以通过在每个可能开始新块的点处分支来确保产生最佳输出，递归地采取两个分支，直到所有路线都被采取。具有最佳行为的路径获胜。由于选择何时开始新块非常开放，因此这不太可行。

简单地将其限制为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的构建。如果启发式证明是一个强有力的指标，那么你可以放弃投机性质，决定无论如何在某个点交换。

- ShuggyCoUk

Answer 2

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

同时，我意识到为了在这个问题上做出全面的决策，我需要更好地了解块大小决策的利弊。很快我就明白了，较小的块允许您拥有潜在的更好的目标符号字母表 - 但代价是更频繁地定义树所带来的开销增加。较大的块通过规模效率（只需存储和解码大量编码数据的一个树）抵消了它们更一般的符号字母表。

从我的经验来看，不清楚文字代码与长度、距离代码的相对分布是否会对最佳块大小产生特定影响。这是一个值得深思的问题。

- David Hay

---

使用机器学习来制定规则。为了生成训练数据，探索下一个数据的所有候选压缩决策，并记录哪个决策与数据的特征在决策点附近（或者如果使用深度学习等自己进行表示学习的机器学习方法，则记录原始数据）一起效果最好，并将其提供给学习器。在生产中，提取特征并询问模型应该做出哪些压缩决策。 - undefined