From WinZips to GIFs, Jacob Ziv’s Algorithms Have Powered Decades of Compression | Hacker News Reader

From WinZips to GIFs, Jacob Ziv’s Algorithms Have Powered Decades of Compression

spectrum.ieee.org

98 pointschha21 comments

I know it was meant as a bit of a goof, but i always thought that the "look up the file in pi!" idea was a clever way of doing compression[1], exploiting the fact that pi is normal and thus any given sequence of numbers will happen eventually, meaning that any given file that could possibly exist will show up eventually. Using this, you could theoretically just store two numbers to compress anything, a beginning point and an end point for its position in pi.

I'm aware this would be unbearably slow and the numbers to store really big files might end up taking more memory than LZMA, so I don't need a lecture about it, I just thought it was an interesting idea.

[1] https://github.com/philipl/pifs

It's not just slow but it wouldn't be compression either.

On average, the length of the number required to point to the starting digit will be the same length as the data you're trying to compress.

It would be 0% compression in the long run.

> On average, the length of the number required to point to the digit will be the same length as the data you're trying to compress. It would be 0% compression in the long run

Worse than 0%. The average position of numbers 0000-9999 in pi is 9940, for example.

I believe ideally you'd want a De Bruijn sequence (https://en.wikipedia.org/wiki/De_Bruijn_sequence - "optimally short with respect to the property of containing every string of length n at least once") but even that won't get 1:1 compression.

It's a commonly held misconception that Pi is proven to be normal - it is NOT (it is a conjecture as of now) [1] [2]. Proving normality of number is a very hard problem, and hardly any numbers outside of purposefully constructed ones (such as Champernowne's constant [3]) are proven normal.

In fact it's not even proven that every digit occurs infinitely many times in the decimal expansion of Pi. [4]

So https://github.com/philipl/pifs is wrong in claiming that all byte stream will exist somewhere in Pi (it's not proven). Also it's worth calling out that even if Pi was Normal it will likely take more space to store the indices of two location as it will for original data itself (for at least majority of the integers), so it's not much of a "compression" strictly speaking. It's easy to see how this will work out for a known normal number - Champernowne's constant [3] -> Unlike Pi, Champernowne's constant is guaranteed to contain all the possible natural number sequences, but storing just the starting index of them in this constant is going to take much longer than the entire number itself (e.g., number "11" start at index 12 (1-indexing), number "12" starts at index 14, and so on - the size of index increases much faster than integer being looked up itself).

[1] https://mathworld.wolfram.com/NormalNumber.html

[2] https://math.stackexchange.com/a/216578

[3] Champernowne's constant (in base 10) is the concatenation of all positive integers and treating them as the decimal expansion (following "0."): 0.12345678910111213... It can be trivially seen that it contains all natural number strings. It is also proven to be Normal in base 10 (which is a stronger property). See https://en.wikipedia.org/wiki/Champernowne_constant for details.

[4] https://en.wikipedia.org/wiki/Normal_number#Properties_and_e...

I know it's just a conjecture, it's actually mentioned in that Github page that it's a conjecture.

That said, if we assume it's true, it's an interesting thing to think about.

I was referring to the claim made in the README's section: "Every file that could possibly exist?", which is written as if it's a proven statement:

> That's right! Every file you've ever created, or anyone else has created or will create! Copyright infringement? It's just a few digits of π! They were always there!

But yes, after you mentioned it, I see that the conjecture disclaimer is mentioned in a section at top ("What does π have to do with my data?") and afterwards the fact is assumed as true in rest of the README.

How would that be any better than "point to a spot on the number line"?

I suppose it's not functionally different, since any binary can be expressed in terms of an integer. My tail has been thoroughly planted between my legs.

Did the word "compression" get cut off due to title length? Or is it intentionally being compressed in the original title as a meta-joke? Turns out it's the former

It's lossless too (with the context)!

Well quite to opposite it’s a pretty good example of lossy compression.

Lossless compression has to be lossless outside of any context or interpretation, it’s mathematically reversible.

This is rather a good analogy of a compression akin to say MP3.

> The following year, the two researchers issued a refinement, LZ78. That algorithm became the basis for the Unix compress program used in the early ’80s; WinZip and Gzip, born in the early ’90s; and the GIF and TIFF image formats.

I don't understand the inclusion of WinZip and gzip here. Those are based on DEFLATE, which I thought was deliberately derived from LZ77 and LZSS rather than anything particular to the LZ78/LZW lineage (for patent reasons). Am I confused about something?

I'm finding conflicting web docs about what algorithms pkzip prior to 2.0 (deflate == gzip) used. There were "shrink" and "implode", they had some run-length encoding, and some entropy coding (shannon fano trees, later replaced by huffman coding in deflate). My vague memory says there was an LZW among them, with PKZIP 0.8 or something, but I'm not sure.

What I am sure about, is that the predecessor to PKZIP, "PKARC", most certainly did use LZW; It was compatible with SEA ARC, but much, much faster (like 5x or so). SEA sued Phil Katz, and his response was to drop ARC compatibility and release PKZIP which was faster and better -- though the incumbent "deflate" method did not appear until version 2 a few years later.

Shrink is LZW, Implode is LZ77 + Shannon-Fano/Huffman. See https://www.hanshq.net/zip2.html

I think it's the article that's confused, or being a bit careless with the details.

Like you say, Deflate is based on LZ77, and I think it's not just for patent reasons but because it's a nice algorithm. More modern algorithms like LZMA is also LZ77 based.

> Without these algorithms, we’d likely be mailing large data files on discs instead of sending them across the Internet with a click, buying our music on CDs instead of streaming it, and looking at Facebook feeds that don’t have bouncing animated images.

I really hate these hyperbolic statements. It makes it seem like if it wasn't for Ziv and Lempel no one would have figured out how to do lossless compression, which is just utterly ridiculous.

“We would pick a book and then study together, like religious Jews studying the Hebrew Bible.“ Damn, I miss the days when I had the opportunity to actually do that. As a researcher, nowadays I’m forced to skim over many papers a day without having the time to actually study them and learn something deep about what the authors proposed. Anyone else thinks that the joy of creating/learning has been replaced by the need of constant output and technical literature feels really shallow nowadays?

In what way are you “forced”? I assume you aren’t tenured - but I do know several tenured academics who got off the treadmill and are doing just that.

There is a multitude of different papers coming out on each subject every day, most with small shallow contributions, and I need to keep up. When I do my own writing, I need to compare and state how I’m improving on them. Paper publishing is an extremely lucrative business, so technical papers are flowing like an endless river, regardless of quality or depth. Edit: I have a permanent position (outside the US system) but from my experience a tenure simply means more work. You need to keep up with the output if you want to do high-impact research, and it’s simply too much (in my opinion).

Perhaps try to find a less crowded niche. When Ziv approached information theory it was nearly empty by the standards of the time (.. and everything was much less crowded than today, also publish or perish wasn’t yet a thing)

accessible link for nojs clients:

https://archive.is/Bb1Aw

Reply on news.ycombinator.com