Take a look at dictzip. It is compatible with gzip and allows coarse random access.
An excerpt from its man page:
dictzip compresses files using the gzip(1) algorithm (LZ77) in a manner which
is completely compatible with the gzip file format. An extension to the gzip
file format (Extra Field, described in 2.3.1.1 of RFC 1952) allows extra data
to be stored in the header of a compressed file. Programs like gzip and zcat
will ignore this extra data. However, [dictzcat –start] will make use
of this data to perform pseudo-random access on the file.
I have the package dictzip in Ubuntu. Or its source code is in a dictd-*.tar.gz. Its license is GPL. You are free to study it.
Update:
I improved dictzip to have no file size limit.
My implementation is under MIT license.