undefined | Better HN

0 pointsadrianmonk3y ago0 comments

> I don't think PKWARE feels bad because ZSTD is a homage to ZIP.

Is zstd actually an homage to zip?

I'm not saying that it definitely isn't, but the only connection I know of myself is that they both begin with the letter Z, and the letter Z has a long association with data compression that goes back before the zip format / pkzip program.

The LZ77, LZ78[1], and LZW[2] algorithms all predate the zip format. As do two very old, obsolete Unix compression programs: "pack"[3], which is uses a ".z" suffix for compressed files, and "compress"[4], which uses a ".Z" suffix for compressed files.

In those algorithm names, the L and Z stand for Lempel and Ziv, respectively. But interestingly, the Unix "pack" program uses a ".z" suffix even though its algorithm is just Huffman (not one of the Lempel-Ziv family of algorithms), so the letter Z somehow came to signify data compression more generally.

Rough timeline of letter Z in data compression:

1977: LZ77

1978: LZ78

1982 or earlier: Unix "pack" (.z)

1984: LZW

1985: Unix "compress" (.Z)

1989: PKZIP

---

[1] https://en.wikipedia.org/wiki/LZ77_and_LZ78

[2] https://en.wikipedia.org/wiki/Lempel-Ziv-Welch

[3] https://en.wikipedia.org/wiki/Pack_(compression)

[4] https://en.wikipedia.org/wiki/Compress

0 comments

bayindirh3y ago

> Is zstd actually an homage to zip?

I think so. Or more generally, DEFLATE family of algorithms used by zlib and ZIP.

> I'm not saying that it definitely isn't, but the only connection I know of myself is that they both begin with the letter Z, and the letter Z has a long association with data compression that goes back before the zip format / pkzip program.

> The LZ77, LZ78[1], and LZW[2] algorithms all predate the zip format.

I'm well aware of the Ziv, Lempel & Welch's work, since I've developed a compression algorithm [*] and did extensive research on the family before, however the usage of extension is a rather new information for me.

On the other side, official repository of zstd [0] lists zlib and other libraries which use DEFLATE in one way other, pointing back to Ziv's ZIP at the same time.

At the end of the day, it might be tipping its hat directly to "ZIP" per se, but to general direction of DEFLATE which is used by ZIP format too.

[*]: The algorithm I developed was working on syllables rather than bytes. It had a deterministic and fast hyphenation engine for the language, and used embedded dictionary to minimize bit-flip damage during transit. I have paper published from it, and still planning to re-implement and open it, since the PoC was beyond bad from a code quality perspective.

adrianmonkOP3y ago

Right, there's definitely a connection in the algorithms. They're all derivatives of the same family of stuff.

I could've been clearer, but when I said the only connection I saw between them was the Z, I meant the only connection between their names. In other words, while zstd surely has zip among its main influences, I'm not sure that the Z in "zstd" is there to convey "zip-like". It could be, or maybe it's just there because Z is generally associated with data compression.

j / k navigate · click thread line to collapse