Compactar arquivos semelhantes com eficiência

11

Freqüentemente, tenho a necessidade de compactar arquivos muito parecidos entre si.

Atualmente, uso o 7Zip, que comprime um arquivo de 16 GB para 1,2 GB em cerca de 35 minutos, usando 8 núcleos com configurações Ultra.

Parece-me que grande parte desse tempo é gasto computando o dicionário para usar na compactação. Como os arquivos são altamente semelhantes, o dicionário realmente usado provavelmente também é semelhante.

Existe uma ferramenta de compactação baseada no Windows (7Zip com uma opção que eu não conheço ou uma ferramenta diferente) que pode salvar o dicionário e reutilizá-lo nos arquivos subseqüentes?

Existe uma maneira melhor de abordar o problema de manter uma taxa de compressão semelhante à que eu tenho, enquanto comprime significativamente mais rápido?

Eric J.
fonte

Respostas:

5

O algoritmo de compressão Lempel-Ziv-Welch (LZW) é inerentemente intensivo em termos computacionais, com a maior parte do trabalho sendo computando o dicionário. É literalmente assim que o LZW funciona.

O próprio algoritmo adiciona uma nova entrada de dicionário para cada próximo "símbolo" que varre e, portanto, durante cada iteração, uma nova entrada é adicionada ao dicionário. De fato, o dicionário se torna a cópia compactada do arquivo e, portanto, é realmente a única coisa que a compactação LZW gasta um tempo significativo de computação em primeiro lugar.


Se você usasse algo como a codificação Huffman , a reutilização do dicionário seria realmente possível (às custas de uma taxa / tamanho de compressão possivelmente não ideais). Entretanto, a maioria dos algoritmos e ferramentas de compressão modernos usa o algoritmo LZW para eficiência e velocidade (a compressão Huffman exigiria duas passagens sobre os dados [uma para gerar a árvore / tabela Huffman, outra para realmente comprimir os dados], enquanto a LZW pode ser concluída em um único passe).

Avanço
fonte
11
Com Huffman e um dicionário predefinido, seria necessária apenas uma passagem? Existem ferramentas baseadas em Huffman disponíveis no mercado que suportam dicionários salvos?
Eric J.
@EricJ. Sim, com um dicionário predefinido, seria a codificação de passagem única. Não conheço nenhum software disponível que possa fazer isso, embora tenha escrito pessoalmente programas que o fazem. Enquanto eu não tentei, esta ferramenta parece que pode fazer exatamente isso. No entanto, observe que (novamente, ao contrário do LZW) para decodificar um fluxo de bits codificado por Huffman, você ainda precisa do dicionário original para descomprimir os dados.
Breakthrough
Com base na idade dessa ferramenta, acho que ela é de thread único. Eu acho que usar 1 núcleo em vez de 8 compensaria qualquer benefício para um dicionário fixo :-( Ter o dicionário disponível do outro lado é viável no meu cenário (transferir arquivos grandes entre data centers).
Eric J.
2

Diferentemente do algoritmo DEFLATE, o LZMA do 7-Zip usa compactação sólida por padrão, o que tira proveito da redundância entre arquivos. Isso funcionará com as configurações padrão, desde que os arquivos sejam pequenos o suficiente.

Com as configurações padrão de 2 GB para o tamanho do Solid Block , um arquivo de 16 GB é realmente compactado como 8 blocos separados.

Como o @Breakthorugh já disse, o dicionário é gerado em tempo real. Você pode verificar isso empiricamente definindo o tamanho do bloco sólido como Sólido (compactar todos os arquivos de uma vez) e Não sólido (compactar cada arquivo separadamente).

Aumentar o tamanho do Solid Block resultará em uma desaceleração, mas poderá resultar em uma taxa de compactação muito melhor. Por exemplo, compactar dois arquivos idênticos resultará em um arquivo morto quase o dobro da compactação não sólida.

Dennis
fonte
11
No meu caso, comprimo os arquivos semelhantes, um de cada vez, em diferentes ocasiões. Há apenas todos os arquivos de 16GB-ish em um determinado arquivo morto.
Eric J.
Ah ok. Eu interpretei isso errado. Os arquivos antigos são excluídos quando o novo é criado? Se não, seria admissível armazenar vários arquivos em um único arquivo? Isso não ajudará na velocidade da compactação, mas, dependendo de quão semelhantes sejam os arquivos, poderá ajudar na proporção.
Dennis
11
Deixa pra lá, não. A atualização de um arquivo sólido leva muito mais tempo, mas não resulta em melhor compactação.
Dennis