Como é que um programa de compactação de arquivos pode usar mais RAM do que o arquivo não compactado que está sendo compactado?

3

Eu estava compactando um conjunto de 120 MB de arquivos na melhor compactação que o 7z oferece e notei que ele estava consumindo quase 600MB de RAM no pico.

Por que esses programas de compactação usam tanta RAM, mesmo quando trabalham com conjuntos de dados realmente pequenos, chegando ao ponto de consumir várias vezes mais memória do que o tamanho descompactado do conjunto de dados?

Apenas curioso, estou mais interessado no lado técnico dele.

    
por Faken 13.10.2010 / 16:22

1 resposta

6

Nunca estive em compressão tecnicamente, mas vamos começar a pesquisar ...

O arquivo de ajuda 7z menciona:

LZMA is an algorithm based on Lempel-Ziv algorithm. It provides very fast decompression (about 10-20 times faster than compression). Memory requirements for compression and decompression also are different (see d={Size}[b|k|m] switch for details).

(Observe que o artigo do algoritmo LZ em wikipedia faz < em> não menciona nada sobre o requisito de memória.

d={Size}[b|k|m] Sets Dictionary size for LZMA. You must specify the size in bytes, kilobytes, or megabytes. The maximum value for dictionary size is 1 GB = 2^30 bytes. Default values for LZMA are 24 (16 MB) in normal mode, 25 (32 MB) in maximum mode (-mx=7) and 26 (64 MB) in ultra mode (-mx=9). If you do not specify any symbol from the set [b|k|m], the dictionary size will be calculated as DictionarySize = 2^Size bytes. For decompressing a file compressed by LZMA method with dictionary size N, you need about N bytes of memory (RAM) available.

Após a wikipedia no artigo sobre os codificadores de dicionário , parece que o algoritmo trabalha comparando os dados a serem compactados para um conjunto de dados em um "dicionário" que deve ser baseado nos dados brutos que devem ser compactados.

Independentemente de como este dicionário é construído, uma vez que ele deve ser mantido na memória, o requisito de RAM é uma função deste dicionário. E como esse dicionário não é dados brutos, mas sim alguma estrutura de dados não compactada, ele (pode) ser maior que os dados brutos processados. Faz sentido?

    
por 13.10.2010 / 16:46