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

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 de seu conjunto de dados?

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

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

O 7z helpfile menciona:

LZMA é um algoritmo baseado em   Algoritmo Lempel-Ziv. Ele fornece muito   descompressão rápida (cerca de 10-20 vezes   mais rápido que a compressão). Memória   requisitos para compressão e   descompressão também são diferentes (ver   d = {Tamanho} [b | k | m] opção para detalhes).

(Observe que o artigo do algoritmo L-Z wikipedia faz não mencionar nada sobre o requisito de memória.)

d = {tamanho} [b | k | m] conjuntos Tamanho do dicionário   para LZMA . Você deve especificar o tamanho em   bytes, kilobytes ou megabytes. o   valor máximo para o tamanho do dicionário é 1   GB = 2 ^ 30 bytes. Valores padrão para   LZMA são 24 (16 MB) no modo normal, 25   (32 MB) no modo máximo (-mx = 7) e 26   (64 MB) no modo ultra (-mx = 9). Se vocês   não especifique nenhum símbolo do conjunto   [b | k | m], o tamanho do dicionário será   calculado como DictionarySize = 2 ^ Size   bytes. Para descompactar um arquivo   comprimido pelo método LZMA com   tamanho do dicionário N, você precisa sobre N   bytes de memória (RAM) disponíveis.

Seguindo a Wikipédia mais adiante no artigo sobre codificadores de dicionário Parece que o algoritmo trabalha comparando os dados a serem compactados com 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?

Se a outra resposta é muito difícil para alguém ler porque tem muito jargão técnico, ofereço minha resposta.

Um arquivo é armazenado no disco rígido ou na unidade sólida. O que é um arquivo que você pergunta? Eu respondo, um monte de 1s e 0s dispostos em uma ordem específica que parece um arquivo do lado de fora. O que é um programa executável? *.exe? É executável em código de máquina, também um monte de 1s e 0s. Também é armazenado na sua unidade de disco. Quando você clica no executável de compactação de arquivos, o algoritmo de instruções de código é carregado a partir do *.exe na unidade de disco na RAM. Só então é capaz de correr. A CPU do computador executa programas e lê / grava dados. Não é possível obter nada diretamente da unidade de disco. Ele tem que carregar tudo na memória RAM primeiro, que atua como intermediário entre a CPU e a unidade de disco onde todos os seus dados são armazenados.

Agora o programa de compactação de arquivos está sendo executado pela CPU na RAM. O que as instruções do código dizem à CPU para fazer? Eles dizem para carregar o próprio arquivo da unidade de disco para a memória RAM, para que o programa possa trabalhar com ele. Então agora temos duas coisas na memória RAM: o próprio programa e o arquivo.

Você diz a este programa de compactação de arquivos para compactar o arquivo. No entanto, não pode magicamente apenas fazer isso. Para ser comprimido, um arquivo deve ser organizado em uma certa ordem, o mais rigorosamente possível. Talvez antes da compactação, o arquivo estava um pouco desorganizado, como seu gabinete de arquivos. O programa de compactação de arquivos precisa organizar o arquivo da maneira mais clara e precisa possível. Para fazer isso, ele precisa temporariamente colocar o arquivo em um estado ainda mais desorganizado, a fim de encontrar todas as partes nas quais tudo pertence.

Pense em como você comprimiria seus papéis. Primeiro você os espalharia por toda a sua mesa até que pudesse vê-los todos, e eles os classificassem por categorias, e começassem a colocar os papéis em pastas.

Então agora temos três coisas na memória RAM: 1. As instruções do programa em si. 2. O arquivo original que foi carregado a partir da unidade de disco. 3. Uma cópia temporária do arquivo original, que está em estado de ser desmontado e colocado de volta. Talvez várias cópias temporárias de todo o arquivo ou partes dele sejam feitas na RAM para facilitar a organização e a compactação desse arquivo. Agora você vê como os programas de compactação de arquivos podem ocupar muito mais RAM quando estão trabalhando em comparação com o tamanho do arquivo original na unidade de disco?

A quantidade de RAM usada durante esse processo depende da habilidade do programador que projetou o aplicativo. Existem maneiras inteligentes e eficientes de escrever o código para minimizar o consumo de RAM. E há formas de força bruta para realizar a mesma tarefa, mas ela fica mais lenta e ocupa mais memória RAM. RAM pode até ser desperdiçado se o programa tiver um vazamento de memória. Pense em um vazamento de memória, como fazer várias cópias dos mesmos dados, mas depois deixá-lo na mesa e nem mesmo se preocupar em limpar a si mesmo.

Eventualmente, todas as cópias temporárias seriam condensadas na versão compactada do arquivo. Ele ainda está na memória RAM, então a versão compactada do arquivo deve ser enviada de volta para o disco rígido, onde é salvo permanentemente.

A idéia principal é que, para alcançar um estado de baixa entropia, você deve passar temporariamente por um estado de alta entropia. Isto é claro, escrito nos termos mais gerais.