Improving a lightweight LZ77 computation algorithm for running faster. (11th November 2015)

• Record Type: Journal Article
• Authors: Liu, Wei Jun; Nong, Ge; Chan, Wai hong; Wu, Yi
• Is Part Of: Software, practice & experience. Volume 46:Number 9(2016)
• Page Start: 1201
• Page End: 1217
• Publication Date: 2015-11-11
• Subjects: Lempel–Ziv factorization -- algorithm -- linear time -- lightweight -- data compression -- suffix array; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2377
• Languages: English
• ISSNs: 0038-0644

Abstract

Summary: 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, ⌈log n ⌉ 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.