Improving the Speed of LZ77 Compression by Hashing and Suffix Sorting
Summary :
Two new algorithms for improving the speed of the LZ77 compression are proposed. One is based on a new hashing algorithm named two-level hashing that enables fast longest match searching from a sliding dictionary, and the other uses suffix sorting. The former is suitable for small dictionaries and it significantly improves the speed of gzip, which uses a naive hashing algorithm. The latter is suitable for large dictionaries which improve compression ratio for large files. We also experiment on the compression ratio and the speed of block sorting compression, which uses suffix sorting in its compression algorithm. The results show that the LZ77 using the two-level hash is suitable for small dictionaries, the LZ77 using suffix sorting is good for large dictionaries when fast decompression speed and efficient use of memory are necessary, and block sorting is good for large dictionaries.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.12 pp.2689-2698
- Publication Date
- 2000/12/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Information Theory
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kunihiko SADAKANE, Hiroshi IMAI, "Improving the Speed of LZ77 Compression by Hashing and Suffix Sorting" in IEICE TRANSACTIONS on Fundamentals,
vol. E83-A, no. 12, pp. 2689-2698, December 2000, doi: .
Abstract: Two new algorithms for improving the speed of the LZ77 compression are proposed. One is based on a new hashing algorithm named two-level hashing that enables fast longest match searching from a sliding dictionary, and the other uses suffix sorting. The former is suitable for small dictionaries and it significantly improves the speed of gzip, which uses a naive hashing algorithm. The latter is suitable for large dictionaries which improve compression ratio for large files. We also experiment on the compression ratio and the speed of block sorting compression, which uses suffix sorting in its compression algorithm. The results show that the LZ77 using the two-level hash is suitable for small dictionaries, the LZ77 using suffix sorting is good for large dictionaries when fast decompression speed and efficient use of memory are necessary, and block sorting is good for large dictionaries.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_12_2689/_p
Copy
@ARTICLE{e83-a_12_2689,
author={Kunihiko SADAKANE, Hiroshi IMAI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Improving the Speed of LZ77 Compression by Hashing and Suffix Sorting},
year={2000},
volume={E83-A},
number={12},
pages={2689-2698},
abstract={Two new algorithms for improving the speed of the LZ77 compression are proposed. One is based on a new hashing algorithm named two-level hashing that enables fast longest match searching from a sliding dictionary, and the other uses suffix sorting. The former is suitable for small dictionaries and it significantly improves the speed of gzip, which uses a naive hashing algorithm. The latter is suitable for large dictionaries which improve compression ratio for large files. We also experiment on the compression ratio and the speed of block sorting compression, which uses suffix sorting in its compression algorithm. The results show that the LZ77 using the two-level hash is suitable for small dictionaries, the LZ77 using suffix sorting is good for large dictionaries when fast decompression speed and efficient use of memory are necessary, and block sorting is good for large dictionaries.},
keywords={},
doi={},
ISSN={},
month={December},}
Copy
TY - JOUR
TI - Improving the Speed of LZ77 Compression by Hashing and Suffix Sorting
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2689
EP - 2698
AU - Kunihiko SADAKANE
AU - Hiroshi IMAI
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2000
AB - Two new algorithms for improving the speed of the LZ77 compression are proposed. One is based on a new hashing algorithm named two-level hashing that enables fast longest match searching from a sliding dictionary, and the other uses suffix sorting. The former is suitable for small dictionaries and it significantly improves the speed of gzip, which uses a naive hashing algorithm. The latter is suitable for large dictionaries which improve compression ratio for large files. We also experiment on the compression ratio and the speed of block sorting compression, which uses suffix sorting in its compression algorithm. The results show that the LZ77 using the two-level hash is suitable for small dictionaries, the LZ77 using suffix sorting is good for large dictionaries when fast decompression speed and efficient use of memory are necessary, and block sorting is good for large dictionaries.
ER -
English
