Why are tar.xz files 15x smaller when using Python's tar compared to macOS tar?

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

LZ78 isn't adaptive; entries are forced out of the dictionary as soon as the window moves beyond where the dictionary-entry was originally defined, and if those entries are still relevant, they'll get a redundant definition in the next block.

Also, LZ78 is not recursively compressed (i.e. it doesn't compress the dictionary itself—it won't recognize when the subsequences it's working with are themselves internally redundant and would be better represented as a function with an input.)

Huffman/arithmetic/range/ANS are all "the same" insofar as they're all local-context streaming coders, i.e. things that only have the power of an FSM rather than the power you can get from requiring a pushdown automata/Turing machine.

The kind of coder I was talking about above, definitely would require a Turing machine. You couldn't implement it as a DSP — you need that unbounded-length state tape, the ability to write unbounded amounts of code to it, and the ability to jump to that code. That doesn't guarantee that it would be more powerful/better compressing; just that it could be. It wouldn't have the same inherent limits to its power that FSM-equivalent codes do.

-----

Let me go on a tangent for a bit, about what such a code probably would achieve if it could work (which should convince you, like me, that this is probably impossible somehow):

One thing I'd expect the code above to accomplish, would be to take a set of files representing images produced by capturing the sequential output frames generated by running an input movie on a NES emulator; and to emit something that looks very analogous to a cut-down version of the original ROM + input movie. (That is, the compressed data would contain 1. a set of partial spritesheets — the nodes of the prefix trie; 2. a set of partial tilemaps, referencing those spritesheets — the dictionary patch definition blocks; and 3. a sequence of bytecode instructions that use arbitrary geometric "draw" operations, jumps, loop registers, etc., to generate the screen-capture images by referencing the tilemaps that in turn reference the spritesheets — i.e. by calling ops to load/unload dictionary patches by reference. That's a "demo", in demoscene terms.)

This kind of result, if achieved, would (AFAIK) beat all currently-known compression methods. The best ANS code can't compress a sequence-of-images of SMB1 as well as just storing the ROM of SMB1 together with the input movie does. This wouldn't get quite to that degree of compression, but it would get close, and it would do it without the "implicit" Kolmogorov complexity of a NES emulator†.

† Though you could think of the output as something like the Futamura projection of a NES emulator with a specific ROM + input movie loaded into it. (It'd be a very weird NES emulator; one that runs as a batch process and emits image files of video frames. But if you had such an emulator, the output of Futamura-ing it would be very close to — or possibly better than — the output of this kind of approach. But, unlike this approach, incredibly non-portable — it would likely only run on the host architecture + OS version it was Futamura-ed on.)

In the (1D) audio domain, what I'm describing would basically involve turning PCM audio that encodes a rendering of a MIDI sequence through a set of patches, back into the inputs (a MIDI sequence and a set of patches), plus any noise/mastering effects as a residue. We can already do that in domain-specific systems, of course — that's how Melodyne's Direct Note Access works.

I'm just talking about doing it instead in a general compressor, lifting data with opaque redundancies out into graphical data-structures heuristically in order to then compress those graphical data-structures into programs that build-and-then-walk those graphs to produce the original output. A code that synthesizes something like MIDI to represent music; something like NES nametables to represent collaged images; etc. Not as well as those domain-tuned codes do, but better than local-context non-structural codes do. Basically the promise of Hierarchical Temporal Memory, but without the ML part. Purely-algorithmic HTM.

And another fun consequence of such a graphical-structuring code existing, would be that you could feed it non-trivial program binaries, and its output would be an equivalent program retargeted into an hypothetical ISA optimized for just that program. Feed it a corpus of enough such programs, all distinct, and you'll get a generally-space-optimized version of the ISA. An automatic derivation of THUMB from ARM, sorta thing.

------

And again, as I said in my sibling comment: this seems so obvious a win to me that it must be broken or impossible somehow. Tries / DAFSAs are easy. Longest-common-substring iterated to a satisfaction threshold is easy (using temporary post-constructed suffix automata.) Hypothetical iterated restructuring is easy — see OptiPNG, HypoPG, etc. So, where's the impossible part where the wheels fall off? I'm pretty sure it's there.)

In terms of standard Linux tools, that's hardly ancient.

The article calls xz out for its inadequacy as a (long-term) container format, which is nothing to do with its compression method (shared by both xz and lzip). I guess in this thread we are specifically talking about the efficiency of compression algorithms...

Most of the points that article makes are utterly irrelevant for most uses of xz, including this one.

So, I wanted to check so I downloaded linux source tree and ran gzip and zstd.

    Uncompressed .tar:    1064376320
    .xz (downloaded file): 117637692 (88.9%)
    .gz:                   189299444 (82.2%)
    .gz (level 9):         186533230 (82.5%)
    .zst:                  178012638 (83.3%)
    .zst --ultra -22:      119676867 (88.8%)

So, even at maximum level, zstd is only about 6% better, or about 37% if you consider .gz as baseline, while being about 10x slower than gzip level 9. There are places where having a smaller compressed file is worth the cost of 10x execution time (and much higher memory usage), but serving web pages is almost certainly not one of them.

In other words, the reason gzip is still being widely used is simply because it's good enough for its use cases. It's less like the original T1, and more like complaining that people are still driving Toyota Camry 2011 when Toyota Camry 2021 is a so much better car.

I'll start calling my grandpa junk too.

I recall reading something in the 90s where in the 70s, Huffman coding was considered mathematically optimal compression and the whole field stagnated for a while because they thought they'd reached a fundamental limit.

> If I called an original Atari junk, some would take it as "this is useless" but most would take it as "this is useless now".

I think you have that backwards. "junk" is an insulting word. If you called an Atari junk, most would understand you to be disparaging it in a roundabout way, not making a temporal point. To be fair to OP he did at least call it "ancient junk." But there's no need to add "junk." "old" or "ancient" more than ably would have made the point.

> And how do you read those archives (or, for that matter, create them) using a ZIP library that doesn't know how to deal with compressed data?

You don’t because you just want to archive them not read them.

> That's because using non-binary mode is bad

Text mode is perfectly good, it’s what users want in a good 90% of cases. Possibly more.

Nothing prevents calling the AWS CLI inside a Lambda.