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