Quais são algumas boas estratégias para determinar o tamanho do bloco em um algoritmo deflate?

Question

Eu estou escrevendo uma biblioteca de compressão como um pequeno projeto paralelo, e eu estou longe o suficiente (minha biblioteca pode extrair qualquer arquivo padrão gzip, bem como compatível com produtos (mas certamente ainda não ideal) gzip saída) que é tempo para descobrir uma estratégia de terminação bloco significativa. Atualmente, eu só cortar os blocos off após cada 32k de entrada (tamanho da janela LZ77) porque foi conveinent e rápida de implementar -. Agora eu vou voltar e tentar realmente melhorar a eficiência de compressão

O Deflate especificação só tem a dizer sobre isso: "O compressor termina um bloco quando se determina que começar um novo bloco com árvores frescas seria útil, ou quando o tamanho do bloco enche buffer do bloco do compressor", que não é tudo o que útil.

Eu classificadas através do código SharpZipLib (como eu imaginei que seria a implementação open source mosteasily legível), e descobriu que ele termina um bloco a cada 16k literais de saída, ignorando a entrada. Isso é fácil de implementar, mas parece que deve haver alguma abordagem mais direcionados, especialmente tendo em conta o idioma no spec "determina que começar um novo bloco com árvores frescas seria útil".

Então, alguém tem alguma idéia para novas estratégias, ou exemplos das já existentes?

Agradecemos antecipadamente!

Answer 1

Como sugestão para você ir.

A frente olhar especulativo com um buffer de tamanho suficiente para a indicação de compressão superior para valer a pena a mudança.

Isto muda o comportamento de streaming (mais dados são necessários para ser de entrada antes de ocorrer a saída) e complica significativamente as operações como flush. É também uma carga adicional considerável nas estacas de compressão.

No caso geral, seria possível assegurar que esta produziu a saída ideal simplesmente por ramificação em cada ponto onde é possível começar um novo bloco, tendo ambos os ramos recursing conforme necessário até que todas as rotas são tomadas. O caminho que tinha as vitórias de comportamento ninho. Isso não é provável que seja viável em tamanhos de entrada não triviais desde a escolha do momento para começar um novo bloco é tão aberto.

Simplesmente restringi-lo a um mínimo de 8K literais de saída, mas evitar que mais de 32K literais em um bloco resultaria em uma base relativamente tratável por tentar algoritmos especulativos. chamar 8K um bloco sub.

O mais simples de que seria (código pseudo):

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.

sobrecarga é uma constante para a conta para o custo de comutação blocos

Este é áspero, e provavelmente poderia ser melhorado, mas é um começo para análise, se nada mais. Instrumento o código para obter informações sobre o que provoca um interruptor, o uso que para determinar boas heurísticas que uma mudança pode ser benéfica (talvez que a taxa de compressão caiu significativamente).

Isto pode levar à construção de specChange sendo feito somente quando a heurística considerou razoável. Se as voltas heurísticos a ser ser um forte indicador de que você poderia, então, acabar com a natureza especulativa e simplesmente decidir troca no ponto, não importa o quê.

Answer 2

Hmm, eu gosto da idéia de alguns análise heurística para tentar chegar a algumas "regras" para quando terminar o bloco pode ser benéfico. Vou olhar para a sua abordagem esta noite sugerido, e ver o que eu poderia fazer com ele.

Entretanto, ocorre-me que, a fim de fazer uma escolha plenamente informada sobre a questão, eu preciso de uma melhor imagem mental dos prós e contras de decisões tamanho do bloco. Muito rapidamente Recebo que blocos menores permitem que você tenha um símbolo do alfabeto potencialmente melhor orientados - à custa do aumento da sobrecarga de definir árvores com mais freqüência. blocos maiores contrariar seu símbolo alfabeto mais geral com efficiences de escala (apenas uma árvore para armazenar e decodificar para os lotes de dados codificados).

Em cima da minha cabeça, não é claro se a distribuição relativa de códigos Litteral vs. comprimento, códigos distância teria um impacto específico sobre o tamanho ideal bloco. Boa comida para o pensamento embora.