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

Question

我正在编写一个压缩库作为一个小的项目,我已经足够了(我的库可以提取任何标准的gzip文件,以及生成兼容的(但肯定不是最佳的)gzip输出)是时候计算了一个有意义的块终止策略.目前,我只是在每32k输入(LZ77窗口大小)之后关闭块,因为它是通用的并且快速实现 - 现在我回过头来尝试实际提高压缩效率.

该放气的规格只有这样说的:"压缩机终止块时,它确定开始用新鲜的树一个新的模块将是有益的,或者当块大小填补了压缩机的缓冲块",这是不是所有的这很有帮助.

我通过SharpZipLib代码进行了排序(因为我认为这将是一个可读的开源实现),并发现它每16k字节的输出终止一个块,忽略输入.这很容易实现,但似乎必须有一些更具针对性的方法,特别是考虑到规范中的语言"确定用新鲜树开始新块将是有用的".

那么,是否有人对新战略或现有战略的例子有任何想法？

提前致谢!

Answer 1

作为让你继续前进的建议。

推测性的展望具有足够大小的缓冲区，以表明卓越的压缩值得进行更改。

这会改变流行为（在输出发生之前需要输入更多数据）并使刷新等操作显着复杂化。这也是压桩中相当大的额外负载。

在一般情况下，只需在可以开始新块的每个点进行分支，根据需要递归两个分支，直到采用所有路径，就可以确保产生最佳输出。有嵌套行为的路径获胜。这对于重要的输入大小不太可能是可行的，因为何时开始新块的选择是如此开放。

简单地将其限制为最少 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 的构建。如果启发法被证明是一个强有力的指标，那么您就可以消除投机性质，并简单地决定无论如何都在该点进行交换。