Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How are zlib, gzip and Zip related? (2013)

stackoverflow.com

Post reply on HN
Print view View original

131–140 of 145 posts

Re: How are zlib, gzip and Zip related? (2013)

#131

Post by niftich »

ralfd wrote: post #130
lpage wrote: post #55

In other compression news, Apple open sourced their implementation of lzfse yesterday: https://github.com/lzfse/lzfse . It's based on a relatively new type of coding - asymmetric numeral systems. Huffman coding is only optimal if you consider one bit as the smallest unit of information. ANS (and more broadly, arithmetic coding) allows for fractional bits and gets closer to the Shannon limit. It's also simpler to impl…

Interesting, but it is all spanish to me ... What are "fractional bits"?

This blog post [1] and its predecessor explaining Huffman Codes [2] was a very helpful guide for me.

[1] https://hbfs.wordpress.com/2011/11/01/fractional-bits-part-i... [2] https://hbfs.wordpress.com/2011/05/17/huffman-codes/

Re: How are zlib, gzip and Zip related? (2013)

#132

Post by derefr »

pixelglow wrote: post #98
TimMeade wrote: post #83

Earlier quoted context omitted.

This cannot be a 'true' zip file. The central directory is at the end of the zip file. It's made up of information that is needed for the decompression. So if you are streaming it, you cannot decompress until the entire file is reassembled.

You can definitely compose a zip file "on the fly" and stream it out. The central directory at the end of the zip file can be determined from all the content already streamed. The only wrinkle is that each entry has a header which typically states the compressed size and checksum. Either you have to compress each entry content in some temp buffer or file to figure out the compressed size and checksum, then write out…

What the parent is saying is that the client has to buffer the entire zip file before they receive the index and can begin decompressing it. "Streaming compression" usually implies streaming decompression as well—importantly because a non-negligible use case for streaming compression is sending streams of compressed data that won't fit on the destination together with the decompressed copy; or sending continuous streams of compressed data that could never reach the end to be decompressed. What the parent is saying is that zip cannot work for these use-cases.

Re: How are zlib, gzip and Zip related? (2013)

#133

Post by eln1 »

ralfd wrote: post #130
lpage wrote: post #55

In other compression news, Apple open sourced their implementation of lzfse yesterday: https://github.com/lzfse/lzfse . It's based on a relatively new type of coding - asymmetric numeral systems. Huffman coding is only optimal if you consider one bit as the smallest unit of information. ANS (and more broadly, arithmetic coding) allows for fractional bits and gets closer to the Shannon limit. It's also simpler to impl…

Interesting, but it is all spanish to me ... What are "fractional bits"?

Generally, a symbol of probability p contains lg(1/p) bits of information: 1 bit if p=1/2, 2 bits if p=1/4 etc. In Huffman you directly assign a concrete bit sequence to every symbol - it is perfect if their probabilities are powers of 1/2, but generally is not true: requires approximations, leading to a suboptimal compression ratio.

Accurate entropy coders like arithmetic/range coding or ANS family can directly work on symbols of general probabilities: containing a non-integer number of bits. It has to finally produce complete bits - their fractional number is handled by the state of the coder - kind of a buffer containing a fractional number of bits. Complete bits are produced as soon as they accumulate.

Re: How are zlib, gzip and Zip related? (2013)

#134

Post by kbenson »

ww520 wrote: post #120
kbenson wrote: post #118

Earlier quoted context omitted.

> The 32K back distance just limits how far back to use the duplicate data from the current cursor. It doesn't really limit the block size. Yes, which is a problem because the huffman encoding tree is at the begiing of the block (I believe). except for that, for LZ77 I believe it doesn't really matter when the block begins, because the deduplication is based on prior occurrences (within 32k), so as long as you have t…

In the risk of dragging this too far, tar is just a command line front end to gzip. It just forks gzip in a child process to pipe data to it. No zlib is involved. The archive.tar.gz means tar the files into archive.tar, then gzip it into archive.tar.gz. You can run gzip -d to get back archive.tar. Tar -czf is just a shortcut command. Tar cannot change the file format of .tar.gz. Otherwise, gzip -d won't work.

> Tar cannot change the file format of .tar.gz. Otherwise, gzip -d won't work

I wasn't suggesting that tar changes the file format, but tar, if it was doing the compression through an API call utilizing the zlib library and not piping it through the gzip program would allow tar some extra control over how it chose to compress the archive. The point is moot, it's not calling an API, at least not in GNU tar.

> In the risk of dragging this too far, tar is just a command line front end to gzip. It just forks gzip in a child process to pipe data to it. No zlib is involved.

Yes, I've confirmed this for myself as well now, but that's not the only way it could have been done, which is why I was saying I wanted to take a look.

I often call zlib functions for in memory compression, It's not uncommon, so I thought it was worth looking into.

> The archive.tar.gz means tar the files into archive.tar, then gzip it into archive.tar.gz. You can run gzip -d to get back archive.tar. Tar -czf is just a shortcut command.

I'm well aware, but that doesn't mean there isn't some leeway in how a deflate stream is created. There are many eventual compressed outputs that can result from the same uncompressed input. For example, if you limited your deflate stream blocks to 65k (or whatever size), you would sacrifice a small amount of compression efficiency for the ability to (mostly) reliably discover the entire last block, and using that you could do what we've been talking about. Unfortunately, since it's not enforced by the protocol, you can't rely on it.

Re: How are zlib, gzip and Zip related? (2013)

#135

Post by andrepd »

bch wrote: post #66
mayoff wrote: post #64

Earlier quoted context omitted.

Strange that Apple didn't publish it on https://github.com/apple (which holds all of their open Swift repos). Also, to clarify, ANS is relatively new (2009) but arithmetic coding has been around for a long time. Historically it was avoided because of patents, many (all?) of which have now expired. Apparently ANS isn't going to be patented.

Question not about ANS, but patenting: Wouldn't it make more sense for Apple (or anybody) to actually patent it, and keep those patents, but make it open via licensing ? If there's patentable material and $developer passes on filing for it, doesn't that leave it open for poaching by $third_party ?

Offtopic, but I wonder what do you intend to gain by writing "$word" instead of "a word".

Re: How are zlib, gzip and Zip related? (2013)

#136

Post by greglindahl »

digi_owl wrote: post #128
greglindahl wrote: post #124

Earlier quoted context omitted.

The Internet Archive has both curated and non-curated collections. Right now the Wayback Machine doesn't have any curation, but that doesn't mean it's going to stay that way. However, in this situation, the collaboration between Wikipedia and the Wayback may be what you had in mind. We're working with Wikipedia to make sure all external links from Wikipedia articles are backed up in the Wayback Machine, and there's a…

Not quite. How easily would it be to find the linked to stackoverflow answer on the archive if ever stackoverflow were to vanish from the net one day? There was also a wikipedia article linked on HN recently about a certain mainframe terminal, and a spreadsheet program that make use of a special capability of that terminal. Said article was at risk of being deleted from wikipedia because they deemed it "original rese…

Ah, now you want to talk about discovery! It so happens that I'm building a search engine for the Wayback Machine. But it's true that discovery for it is never going to be that great until the search engines that people commonly use index the Wayback, which is probably never.

Re: How are zlib, gzip and Zip related? (2013)

#137

Post by digi_owl »

greglindahl wrote: post #136
digi_owl wrote: post #128

Earlier quoted context omitted.

Not quite. How easily would it be to find the linked to stackoverflow answer on the archive if ever stackoverflow were to vanish from the net one day? There was also a wikipedia article linked on HN recently about a certain mainframe terminal, and a spreadsheet program that make use of a special capability of that terminal. Said article was at risk of being deleted from wikipedia because they deemed it "original rese…

Ah, now you want to talk about discovery! It so happens that I'm building a search engine for the Wayback Machine. But it's true that discovery for it is never going to be that great until the search engines that people commonly use index the Wayback, which is probably never.

I dunno why you seem to treat those as two separate issues.

The way i see it, one feeds into the other. Wikipedia and other wikis have a repuration for being time/attention sinks, this because you can follow one article to another to another.

Search don't do that. It may or may not barf up what you are looking for if fed the right terms, not much beyond that.

Maybe what i have in mind is something akin to wikiquote but for topics rather than persons. So that this posting by Adler can be filed under zip, gzip, zlib and whatsnot, and people can find it to go alongside the "encyclopedic" description of either of the technologies.

Re: How are zlib, gzip and Zip related? (2013)

#138

Post by eln1 »

mayoff wrote: post #64
lpage wrote: post #55

In other compression news, Apple open sourced their implementation of lzfse yesterday: https://github.com/lzfse/lzfse . It's based on a relatively new type of coding - asymmetric numeral systems. Huffman coding is only optimal if you consider one bit as the smallest unit of information. ANS (and more broadly, arithmetic coding) allows for fractional bits and gets closer to the Shannon limit. It's also simpler to impl…

Strange that Apple didn't publish it on https://github.com/apple (which holds all of their open Swift repos). Also, to clarify, ANS is relatively new (2009) but arithmetic coding has been around for a long time. Historically it was avoided because of patents, many (all?) of which have now expired. Apparently ANS isn't going to be patented.

There is an attempt to patent something ANS-related: http://cbloomrants.blogspot.com/2015/05/05-21-15-software-pa...

Re: How are zlib, gzip and Zip related? (2013)

#139

Post by greggman »

spc476 wrote: post #67
joosters wrote: post #46

Earlier quoted context omitted.

Don't forget 'overwrite old header' Why? The new one will become the 'real' one since it will be at the end of the modified file. So it doesn't really matter if you delete the old one. If you're really trying to squeeze file sizes down, you could reference the old 'header' from the new one, so that you do not have to list the entire archive's contents again.

Having written code to extract files from a ZIP file, it's because the header is variable sized, anywhere from 22 to 65,557 bytes in size (22 bytes fixed, up to 65,535 bytes for a comment). There are two ways to scan for the header, one is to seek just 22 bytes shy of the end of the file and start checking backwards (since the majority of ZIPs I've encountered do not have the comment) or, seek 65,557 bytes from the e…

then you wrote a bad extractor. Scanning forward is against the format. Zipping up a zip file is a perfectly valid thing to do. If the inner zip is stored uncompressed you'll have 2 headers at the end. If you scan forward you'll fail.

Re: How are zlib, gzip and Zip related? (2013)

#140

Post by hatchoo »

dalke wrote: post #105
hatchoo wrote: post #100

Earlier quoted context omitted.

Because it more likely that beginning programmers would jump straight and look for the "accepted answer".

What mechanism would you suggest otherwise? For example, suppose I ask a question, and within 10 minutes get an answer which is good enough for me, then I accept it and move on. Hours later, someone gives a much better answer. What is my obligation to track the topic after I already know a correct answer? What should be the mechanism to override my acceptance? What is more achievable: putting that mechanism in place,…

I'm no UX expert but maybe highlight the accepted answer and a different colored highlight for the top voted answer.
Post reply on HN