6 ms·

The 'window size' dictates how far back the algorithm can look for redundant data. If you set it too high, people without enough core memory might not be able t

by jtvjan 6y ago

The 'window size' dictates how far back the algorithm can look for redundant data. If you set it too high, people without enough core memory might not be able to decompress your archive.

duskwuff 6y ago
And the window size for gzip is only 32 kB -- it "forgets" context pretty quickly. gzip was written in 1992, so it had to run under much tighter memory constraints than necessarily make sense today. Modern compressors like xz (LZMA) use much more memory for context. Under extreme settings and when working with large files, they can use gigabytes of memory.
dmurray 6y ago
Is this really true? Surely they should be able to decompress it with virtual memory - you tell them exactly where to look for each operation. On the other hand, it will take you much longer to compress the file if your lookback window is larger than your available memory.
- jtvjan 6y ago
  They're stream compressors, so they don't want to rely on being able to seek in the file. Even with swap, you'll have to cut it off somewhere; swap space isn't infinite.
derefr 6y ago
If you know your compressor has enough memory to hold the whole plaintext at once, but your decompressor doesn't, why not do extra work on the compression end with the whole plaintext in memory to emit an optimal "dynamic" Huffman alphabet, i.e. a code that gets patched by each new compressed block, rather than resetting to a completely new dictionary for each new block? I presume the tightest packing possible would be achieved by converting the entire document into a Huffman-encoded sequence of references into a single unified strings table; breaking that strings table down recursively using largest-common-substring until satisfied; and then packing the resulting strings tree into something more like an intrusive prefix trie where offsets are implicit IDs. The problem would, of course, be the size of the resulting trie. But you could always make the document into bytecode for a compressor VM (RAR-alike) where one opcode is "insert nodes {KV1, KV2, ...} into the prefix trie", and another opcode is "drop nodes {K1, K2, ...} from the prefix trie", such that the trie "window" used over the document would grow and shrink over time. Then you could optimize for redundant re-definitions of identical trie nodes in the compressed data, vs. total in-memory trie "window" size at any given time. If the decompression wasn't required to be streaming, but rather could advance-allocate an mmap(2)ed file to write to, then you could also have a jump opcode, so that you could organize the Huffman-code trie-prefix definitions in an optimal order to minimize definition redundancy, trading off for making the compressed representation out-of-order relative to the plaintext it decompresses to. The compressor would put the "spine" of the document all together at the beginning, together with the frontloaded rootmost trie-node definitions; then gradually undefine them, replacing them with less-frequently-used nodes needed to decode context-free "islands" of content.
- tedunangst 6y ago
  Sure. Why not code it up?
  - derefr 6y ago
    I'm not an information theorist / cryptographer / etc., and so I have a strong feeling that there must be something wrong with my assumptions, given that "compressing big files using lots of memory for people to later decompress back to files using average amounts of memory" is an extremely-common need (for e.g. packaged software/OS updates.) When a physicist sees a proof for a perpetual-motion machine, they don't ask "can this work"; they ask "where is this going wrong, that it came to this absurd conclusion?" My post wasn't suggesting a real technique — it was me sharing my own perpetual-motion machine proof, so that someone can hopefully point out the step that's impossible, and I can then learn something from that :)
    - dmurray 6y ago
      It sounds plausible to me. Real-world constraints aren't usually "you can use any amount of resources on the compressor, and any amount of compute on the decompressor for free, but the decompressor is hardcapped at exactly X MB of memory". So you might only have a theoretical improvement on existing methods, but that would still be very cool. You can't beat existing methods by much - we're pretty close to the Shannon limit - but it's not a closed subject.
- craftinator 6y ago
  Relevant xkcd: https://xkcd.com/1831/ https://xkcd.com/1831/
- pezezin 6y ago
  What you described is pretty much LZ78. It has been proven that if you can have an infinite dictionary, then you can achieve optimal efficiency. But infinite dictionaries are impossible. Much better algorithms exist nowadays. Also, no modern algorithm uses Huffman coding anymore, it was overtaken by arithmetic and range coders long ago, and more recently by ANS coders.

by jtvjan 6y ago

The 'window size' dictates how far back the algorithm can look for redundant data. If you set it too high, people without enough core memory might not be able to decompress your archive.

duskwuff 6y ago

And the window size for gzip is only 32 kB -- it "forgets" context pretty quickly. gzip was written in 1992, so it had to run under much tighter memory constraints than necessarily make sense today. Modern compressors like xz (LZMA) use much more memory for context. Under extreme settings and when working with large files, they can use gigabytes of memory.

dmurray 6y ago

Is this really true? Surely they should be able to decompress it with virtual memory - you tell them exactly where to look for each operation. On the other hand, it will take you much longer to compress the file if your lookback window is larger than your available memory.

jtvjan 6y ago
They're stream compressors, so they don't want to rely on being able to seek in the file. Even with swap, you'll have to cut it off somewhere; swap space isn't infinite.

derefr 6y ago

If you know your compressor has enough memory to hold the whole plaintext at once, but your decompressor doesn't, why not do extra work on the compression end with the whole plaintext in memory to emit an optimal "dynamic" Huffman alphabet, i.e. a code that gets patched by each new compressed block, rather than resetting to a completely new dictionary for each new block? I presume the tightest packing possible would be achieved by converting the entire document into a Huffman-encoded sequence of references into a single unified strings table; breaking that strings table down recursively using largest-common-substring until satisfied; and then packing the resulting strings tree into something more like an intrusive prefix trie where offsets are implicit IDs. The problem would, of course, be the size of the resulting trie. But you could always make the document into bytecode for a compressor VM (RAR-alike) where one opcode is "insert nodes {KV1, KV2, ...} into the prefix trie", and another opcode is "drop nodes {K1, K2, ...} from the prefix trie", such that the trie "window" used over the document would grow and shrink over time. Then you could optimize for redundant re-definitions of identical trie nodes in the compressed data, vs. total in-memory trie "window" size at any given time. If the decompression wasn't required to be streaming, but rather could advance-allocate an mmap(2)ed file to write to, then you could also have a jump opcode, so that you could organize the Huffman-code trie-prefix definitions in an optimal order to minimize definition redundancy, trading off for making the compressed representation out-of-order relative to the plaintext it decompresses to. The compressor would put the "spine" of the document all together at the beginning, together with the frontloaded rootmost trie-node definitions; then gradually undefine them, replacing them with less-frequently-used nodes needed to decode context-free "islands" of content.

tedunangst 6y ago
Sure. Why not code it up?
- derefr 6y ago
  I'm not an information theorist / cryptographer / etc., and so I have a strong feeling that there must be something wrong with my assumptions, given that "compressing big files using lots of memory for people to later decompress back to files using average amounts of memory" is an extremely-common need (for e.g. packaged software/OS updates.) When a physicist sees a proof for a perpetual-motion machine, they don't ask "can this work"; they ask "where is this going wrong, that it came to this absurd conclusion?" My post wasn't suggesting a real technique — it was me sharing my own perpetual-motion machine proof, so that someone can hopefully point out the step that's impossible, and I can then learn something from that :)
  - dmurray 6y ago
    It sounds plausible to me. Real-world constraints aren't usually "you can use any amount of resources on the compressor, and any amount of compute on the decompressor for free, but the decompressor is hardcapped at exactly X MB of memory". So you might only have a theoretical improvement on existing methods, but that would still be very cool. You can't beat existing methods by much - we're pretty close to the Shannon limit - but it's not a closed subject.
craftinator 6y ago
Relevant xkcd: https://xkcd.com/1831/ https://xkcd.com/1831/
pezezin 6y ago
What you described is pretty much LZ78. It has been proven that if you can have an infinite dictionary, then you can achieve optimal efficiency. But infinite dictionaries are impossible. Much better algorithms exist nowadays. Also, no modern algorithm uses Huffman coding anymore, it was overtaken by arithmetic and range coders long ago, and more recently by ANS coders.