How is it possible to GZIP a stream before the entire contents are known?

Question

Two things you can do in Java:

1. Send a gzipped JSON body in response to an HTTP request
2. Send a StreamingOutput response to an HTTP request, where you begin sending a response before you know the entirety of the response (e.g. if reading entries from a database)

According to my testing, you can do both at the same time - i.e. gzip a stream of data before you know the entirety of the data.

How is it possible to gzip an incomplete stream? My limited understanding of compression is that it replaces, for example, the most common word with a single byte instead. But figuring out which word is "most common" requires knowing the entire data set. Right?

Answer 1

Your understanding concerns static compression, where the whole dataset is available when you begin compression. In a very simplified way, yes it replaces common sequences with smaller tokens to achieve compression. There are many cases where this won't even result in efficient compression (if done in a naive way), such as skewed data distribution (think "AAABBBCCC" vs. "AAAAAAABC").

More interesting is dynamic compression, which doesn't require before-hand knowledge of the full dataset. For the common CS homework algorithm, see Adaptive Huffman Coding (compared to regular Huffman Coding ) which builds the coding table as it processes the data. In addition to enabling compression of a stream, it also allows the coding table to encode data efficiently in different parts of the stream, regardless of previous data (think "AAABBBCCC").

The dynamic building of the coding table however does establish a dependency on the previous data. To correctly decode the last byte, you need to decode the first and all the following bytes.

In an unreliable environment such as the network, you don't want to resend the whole dataset if a single byte is corrupt (which would break the decoding), so there are lots of other things involved, such as chunking where you divide the payload into parts and compress them independently. A wrong checksum of the chunk would mean only that chunk is resent.