IEICE TRANSACTIONS on Information
Lempel-Ziv Factorization in Linear-Time O(1)-Workspace for Constant Alphabets
Summary :
Computing the Lempel-Ziv Factorization (LZ77) of a string is one of the most important problems in computer science. Nowadays, it has been widely used in many applications such as data compression, text indexing and pattern discovery, and already become the heart of many file compressors like gzip and 7zip. In this paper, we show a linear time algorithm called Xone for computing the LZ77, which has the same space requirement with the previous best space requirement for linear time LZ77 factorization called BGone. Xone greatly improves the efficiency of BGone. Experiments show that the two versions of Xone: XoneT and XoneSA are about 27% and 31% faster than BGoneT and BGoneSA, respectively.
- Publication
- IEICE TRANSACTIONS on Information Vol.E104-D No.12 pp.2145-2153
- Publication Date
- 2021/12/01
- Publicized
- 2021/08/30
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2021EDP7037
- Type of Manuscript
- PAPER
- Category
- Fundamentals of Information Systems
Authors
Weijun LIU
Gannan Normal University
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
Weijun LIU, "Lempel-Ziv Factorization in Linear-Time O(1)-Workspace for Constant Alphabets" in IEICE TRANSACTIONS on Information,
vol. E104-D, no. 12, pp. 2145-2153, December 2021, doi: 10.1587/transinf.2021EDP7037.
Abstract: Computing the Lempel-Ziv Factorization (LZ77) of a string is one of the most important problems in computer science. Nowadays, it has been widely used in many applications such as data compression, text indexing and pattern discovery, and already become the heart of many file compressors like gzip and 7zip. In this paper, we show a linear time algorithm called Xone for computing the LZ77, which has the same space requirement with the previous best space requirement for linear time LZ77 factorization called BGone. Xone greatly improves the efficiency of BGone. Experiments show that the two versions of Xone: XoneT and XoneSA are about 27% and 31% faster than BGoneT and BGoneSA, respectively.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2021EDP7037/_p
Copy
@ARTICLE{e104-d_12_2145,
author={Weijun LIU, },
journal={IEICE TRANSACTIONS on Information},
title={Lempel-Ziv Factorization in Linear-Time O(1)-Workspace for Constant Alphabets},
year={2021},
volume={E104-D},
number={12},
pages={2145-2153},
abstract={Computing the Lempel-Ziv Factorization (LZ77) of a string is one of the most important problems in computer science. Nowadays, it has been widely used in many applications such as data compression, text indexing and pattern discovery, and already become the heart of many file compressors like gzip and 7zip. In this paper, we show a linear time algorithm called Xone for computing the LZ77, which has the same space requirement with the previous best space requirement for linear time LZ77 factorization called BGone. Xone greatly improves the efficiency of BGone. Experiments show that the two versions of Xone: XoneT and XoneSA are about 27% and 31% faster than BGoneT and BGoneSA, respectively.},
keywords={},
doi={10.1587/transinf.2021EDP7037},
ISSN={1745-1361},
month={December},}
Copy
TY - JOUR
TI - Lempel-Ziv Factorization in Linear-Time O(1)-Workspace for Constant Alphabets
T2 - IEICE TRANSACTIONS on Information
SP - 2145
EP - 2153
AU - Weijun LIU
PY - 2021
DO - 10.1587/transinf.2021EDP7037
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E104-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2021
AB - Computing the Lempel-Ziv Factorization (LZ77) of a string is one of the most important problems in computer science. Nowadays, it has been widely used in many applications such as data compression, text indexing and pattern discovery, and already become the heart of many file compressors like gzip and 7zip. In this paper, we show a linear time algorithm called Xone for computing the LZ77, which has the same space requirement with the previous best space requirement for linear time LZ77 factorization called BGone. Xone greatly improves the efficiency of BGone. Experiments show that the two versions of Xone: XoneT and XoneSA are about 27% and 31% faster than BGoneT and BGoneSA, respectively.
ER -
English
