Improving a lightweight LZ77 computation algorithm for running faster

Wei Jun LIU, Ge NONG, Wai Hong CHAN, Yi WU

Research output: Contribution to journalArticles

1 Citation (Scopus)

Abstract

Computing the Lempel–Ziv factorization (LZ77) of a string is a key step in many applications. However, at the same time, it constitutes a bottleneck of the entire computation. The investigation of time and space efficient computation of the LZ77 has become an important topic. In this paper, we present a lightweight linear-time algorithm called LZone for computing the LZ77, which is designed by improvements on the existing linear-time space efficient LZ77 algorithm BGone for speed acceleration. For an input string T[1..n] over a constant alphabet size of O(1), LZone requires only n words of workspace in addition to the input string and the output factorization, ⌈logn⌉ bits per word. This is the same space requirement for the algorithm BGone. LZone has two versions, LZoneT and LZoneSA, corresponding to BGoneT and BGoneSA, respectively. Our experimental results show that for computing the LZ77 from an input string T, LZoneT and LZoneSA run at around 26% and 57%, respectively, faster than their counterparts in BGone. Moreover, for computing the LZ77 from the suffix array of T, the speed of LZoneSA is on average twice that of BGoneSA. Copyright © 2015 John Wiley & Sons, Ltd.
Original languageEnglish
Pages (from-to)1201-1217
JournalSoftware: Practice and Experience
Volume46
Issue number9
Early online dateNov 2015
DOIs
Publication statusPublished - Sep 2016

Citation

Liu, W. J., Nong, G., Chan, W. h., & Wu, Y. (2016). Improving a lightweight LZ77 computation algorithm for running faster. Software: Practice and Experience, 46(9), 1201-1217.

Keywords

  • Lempel–Ziv factorization
  • Algorithm
  • Linear time
  • Lightweight
  • Data compression
  • Suffix array

Fingerprint Dive into the research topics of 'Improving a lightweight LZ77 computation algorithm for running faster'. Together they form a unique fingerprint.