Não é uma reconstrução, mas duas boas alternativas para o zlib são quicklz e fastlz. Ambos são muito rápidos em relação ao gzip -1, mas não atingem uma taxa de compactação tão boa. Para minha aplicação, o tamanho estava subindo 10-15%, mas a velocidade de compressão era 6x, portanto, uma troca muito boa.
É claro que nem é compatível com zlib, então pode não funcionar para você.