A Rolling Hash Algorithm and the Implementation to LZ4 Data Compression

Abstract

LZ77 is a dictionary compression algorithm by replacing the repeating sequence with the addresses of the previous referenced data in the stream. To find out these repetition, the LZ77 encoder maintains a hashing table, which have to frequently calculate hash values during the encoding process. In this paper, we present a class of rolling hash functions, that can calculate multiple hash values via a carry-less multiplication instruction. Then the proposed hash function is implemented in LZ4, which is a derivative of LZ77. The simulation shows that the encoding throughput of LZ4 has 15.7% improvement in average, and the compression ratio is ±1% in most cases.

Keywords

• Carry-less multiplication
• LZ4
• LZ77
• rolling hash
• SIMD