[paddyoloughlin]

Gzip uses DEFLATE, which uses Huffman coding.

Huffman coding works by replacing common symbols with shorter codes and uncommon symbols with longer codes.

The codes used are therefore variable-length.

The codes are created in such a way that no code is the prefix of any other code.

That way, the decoder is able to know when it has reached the end of a code without the need for extra information other than the Huffman tree, which tells the decoder which codes belong to which symbols.

The Huffman tree can be pre-agreed or, more commonly, included with the compressed data.