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

https://spectrum.ieee.org/geek-life/profiles/from-winzips-to-cat-gifs-jacob-zivs-algorithms-have-powered-decades-of-compression

by chha • 5 years ago

98 21 5 years ago

spectrum.ieee.org

bobbyi_settv• 5 years ago

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

mygoodaccount• 5 years ago

It's lossless too (with the context)!

dogma1138• 5 years ago

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.

0xcde4c3db• 5 years ago

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?

beagle33• 5 years ago

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.

zmodem2• 5 years ago

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

zmodem2• 5 years ago

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.

tombert3• 5 years ago

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

crazygringo• 5 years ago

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.

treesprite82• 5 years ago

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.

anuragbiyani2• 5 years ago

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

tombert3• 5 years ago

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.

jonny_eh• 5 years ago

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

tombert3• 5 years ago

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.

forgotmypw17• 5 years ago

accessible link for nojs clients:

https://archive.is/Bb1Aw

Twirrim• 5 years ago

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.

low_tech_love2• 5 years ago

“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?

beagle33• 5 years ago

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.

low_tech_love2• 5 years ago

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

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

Related Stories