3 ms·
Here's an information-theory question: would there be a way to estimate the size of the decompressed output, just given the raw zip data and no size metadata, w
by derefr 12y ago
Here's an information-theory question: would there be a way to estimate the size of the decompressed output, just given the raw zip data and no size metadata, without attempting to extract it (i.e. without spending time or space proportional to the compression factor)?
- nawitus 12y agoWell, yes. The linked page shows you how to calculate it.
- euank 12y agoYour answer is wrong. He says "Just given the raw zipped data and no size metadata". The page calculates it using exactly that size metadata he excluded. The question, as I see it, is if that size metadata (the 4.3 gigs at the bottom) can be determined from the zip file without unzipping a rather lot of data. It would be interesting if someone who knew the exact details of the zip format could comment.
- igul222 12y agoI don't know whether it's possible with ZIP, but there are definitely compression schemes for which this can be done in time proportional to the size of the compressed file.
- DanBC 12y agoLong answer: http://mattmahoney.net/dc/dce.html http://mattmahoney.net/dc/dce.html
- lobster_johnson 12y agoIt's trivial if you know the zip file contains just a single file. A zip file starts with a "local file header" (see [1]) that contains the compressed and uncompressed size metadata. So you can decompress the first n bytes of the first file (where n = enough to get a complete header), look at the header, seek past it, then decompress the header of the next file, and so on, recursively. Unless you meant how to do this without reading the size information from the headers at all, in which case I don't think it would be possible without actually decompressing. There wouldn't be any need to spend "space proportional to the compression factor", though; you would decompress recursively with a pipelined function, but it would just count, not emit, any data. For a 42 KB zipfile, the time required would be near zero. [1] http://www.pkware.com/documents/casestudies/APPNOTE.TXT http://www.pkware.com/documents/casestudies/APPNOTE.TXT
- caspianm 12y agoSo long as it used the usual deflate algorithm, and you don't need to deal with recursive compression as in the article, yes. The size counter program would be structured similarly to the decompression algorithm, but there are some points where the compressed file says "repeat this many bytes from this location" where a decompressor would have to copy that many bytes, where the counter would only have to add the number.