Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

Lempel–Ziv factorization using less time & space

Chen, G., Puglisi, S.J. and Smyth, W.F. (2008) Lempel–Ziv factorization using less time & space. Mathematics in Computer Science, 1 (4). pp. 605-623.

Link to Published Version: http://dx.doi.org/10.1007/s11786-007-0024-4
*Subscription may be required

Abstract

For 30 years the Lempel–Ziv factorization LZ x of a string x = x[1..n] has been a fundamental data structure of string processing, especially valuable for string compression and for computing all the repetitions (runs) in x. Traditionally the standard method for computing LZ x was based on Θ(n)-time (or, depending on the measure used, O(n log n)-time) processing of the suffix tree ST x of x. Recently Abouelhoda et al. proposed an efficient Lempel–Ziv factorization algorithm based on an “enhanced” suffix array – that is, a suffix array SA x together with supporting data structures, principally an “interval tree”. In this paper we introduce a collection of fast space-efficient algorithms for LZ factorization, also based on suffix arrays, that in theory as well as in many practical circumstances are superior to those previously proposed; one family out of this collection achieves true Θ(n)-time alphabet-independent processing in the worst case by avoiding tree structures altogether.

Item Type: Journal Article
Publisher: SP Birkhäuser Verlag Basel
URI: http://researchrepository.murdoch.edu.au/id/eprint/27956
Item Control Page Item Control Page