Since the documentation says thats the module doesn't support backward seeks, it seems that you have provided the answer.

Assuming that you can only seek forward, its an interesting problem how to search in an efficient manner. For starters, its probably a good idea to check if Compress::Zlib does in fact really seek, or if it just providing an abstraction that pretends to seek, while it decompresses everything underneath the hood. In that case, you're most likely to be better off doing linear search.