Gzip uses DEFLATE, which uses Huffman coding.<p>Huffman coding works by replacing common symbols with shorter codes and uncommon symbols with longer codes.<p>The codes used are therefore variable-length.<p>The codes are created in such a way that no code is the prefix of any other code.<p>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.<p>The Huffman tree can be pre-agreed or, more commonly, included with the compressed data.