How is it that a file compression program can use up more RAM than the uncompressed file it is compressing?

Question

I was compressing a 120 MB set of files on the best compression that 7z offers and noticed that it was consuming nearly 600MB of RAM at peak.

Why do these compression programs use so much RAM even when working with realitivly small data sets, even to the point of consuming multiple times more memory than the uncompressed size of its data set?

Just curious, I'm more interested in the technical side of it.

Answer 1

Never been into compression technically, but lets start searching ...

The 7z helpfile mentions:

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).

(Note that the L-Z algorithm article on wikipedia does not mention anything about memory requirement.)

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.

Following wikipedia further to the article about dictionary coders it would appear that the algorithm works by comparing the data to be compressed to a set of data in a "dictionary" that has to be based on the raw data that is to be compressed.

Regardless of how this dictionary is built, since it must be kept in memory, the RAM requirement is a function of this dictionary. And since this dictionary isn't raw data, but some uncompressed data structure, it will (can) be bigger than the raw data that is processed. Makes sense?