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

建议你去。

具有足够大小的缓冲区的推测性展望,表明优越的压缩是值得更改的。

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

在一般情况下,可以通过在可能启动新块的每个点分支,使两个分支在必要时递归,直到所有路由都被占用,从而确保生成最佳输出。有窝行为的道路是成功的。这不太可能是可行的非琐碎的输入大小,因为选择何时开始一个新的块是如此开放。

简单地将其限制为至少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.

开销是一个常数,用来说明切换块的成本。

这很粗糙,可能会得到改善,但如果没有其他的话,这是分析的开始。在代码中插入导致切换的信息,使用该代码确定好的启发式方法,即更改可能有益(可能压缩比已显著降低)。

这可能导致只有在启发式方法认为规范变更是合理的情况下才进行规范变更的构建。如果启发式的结果是一个强有力的指标,那么你可以去掉投机性质,然后简单地决定在点上交换,无论什么。

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

同时,我想到,为了在这个问题上做出一个完全知情的选择,我需要更好地了解块大小决策的优缺点。很快我就明白了,更小的块可以让你有一个潜在的更好的目标符号字母表——代价是更多地定义树会增加开销。较大的块与它们更通用的符号字母表相对应,具有一定的比例效率(对于大量编码数据,只需存储和解码一棵树)。

从我的头顶上看,不清楚小代码与长度、距离代码的相对分布是否会对最佳块大小产生特定的影响。不过,这是值得深思的好东西。