algorithm - 在放气算法中确定 block 大小的一些好的策略是什么？

Question

我正在编写一个压缩库作为一个小的辅助项目，而且我已经足够了(我的库可以提取任何标准的 gzip 文件，以及产生兼容的(但肯定还不是最佳的)gzip 输出)它是是时候找出一个有意义的区 block 终止策略了。目前，我只是在每 32k 输入(LZ77 窗口大小)后切断 block ，因为它实现起来方便且快速——现在我回过头来尝试真正提高压缩效率。

Deflate spec只有这样说:“当压缩器确定用新鲜树开始一个新 block 是有用的，或者当 block 大小填满压缩器的 block 缓冲区时，压缩器终止一个 block ”，这并不是那么有用。

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

那么有人对新策略或现有策略有任何想法吗？

提前致谢!

Answer 1

作为让您前进的建议。

推测性展望，缓冲区大小足以表明卓越的压缩值得改变。

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

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

简单地将其限制为最少 8K 的输出文字但防止 block 中超过 32K 的文字将导致尝试推测算法的相对容易处理的基础。称 8K 为子 block 。

其中最简单的是(伪代码):

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 是一些常量，用于说明切换 block 的成本

这是粗略的，可能会有所改进，但如果没有别的，这只是分析的开始。检测有关导致切换的原因的信息的代码，使用它来确定更改可能有益的良好启发式方法(也许压缩率已显着下降)。

这可能导致仅当启发式认为合理时才构建 specChange。如果启发式结果是一个强有力的指标，那么您就可以消除投机性质，并且无论如何都可以简单地决定在该点进行交换。