Regarding reducing run time, zlib/gzip already use a O(n) algorithm (Rabin-Karp rolling hash search), despite being "slow" in comparison with other "pure-hashin

Regarding reducing run time, zlib/gzip already use a O(n) algorithm (Rabin-Karp rolling hash search), despite being "slow" in comparison with other "pure-hashing" LZ77 implementations (e.g. LZO, LZ4, LZF). I don't have access to that paper, but "compressing indexes" is likely to be slow, no matter how is implemented: fastest LZ77 using hashing relies on doing few operations per input byte. So no matter if the hash table space could be reduced or not, the speed would not be likely to be faster (anyway, you can trade hash table size vs compression ratio, even without that new technique).