The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Le calcul de la factorisation Lempel-Ziv (LZ77) d'une chaîne est l'un des problèmes les plus importants en informatique. De nos jours, il est largement utilisé dans de nombreuses applications telles que la compression de données, l'indexation de texte et la découverte de modèles, et est déjà devenu le cœur de nombreux compresseurs de fichiers comme gzip et 7zip. Dans cet article, nous montrons un algorithme de temps linéaire appelé Xone pour calculer le LZ77, qui a le même besoin d'espace que le meilleur besoin d'espace précédent pour la factorisation du temps linéaire LZ77 appelé BGone. Xone améliore considérablement l'efficacité de BGone. Les expériences montrent que les deux versions de Xone : XoneT et XoneSA sont respectivement environ 27 % et 31 % plus rapides que BGoneT et BGoneSA.
Weijun LIU
Gannan Normal University
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.
Copier
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
Copier
@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},}
Copier
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 -