A Rolling Hash Algorithm and the Implementation to LZ4 Data Compression
| Autor: | Hao Jiang, Sian-Jheng Lin |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
LZ77
rolling hash General Computer Science Computer science 020208 electrical & electronic engineering Hash function General Engineering 020206 networking & telecommunications 02 engineering and technology Dictionary coder Rolling hash SIMD 0202 electrical engineering electronic engineering information engineering LZ4 General Materials Science Multiplication lcsh:Electrical engineering. Electronics. Nuclear engineering Carry-less multiplication lcsh:TK1-9971 Throughput (business) Encoder Algorithm Data compression |
| Zdroj: | IEEE Access, Vol 8, Pp 35529-35534 (2020) |
| ISSN: | 2169-3536 |
| DOI: | 10.1109/access.2020.2974489 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|