Lempel-ziv factorization using less time and space

Chen, G, Puglisi, S and Smyth, W 2008, 'Lempel-ziv factorization using less time and space', Mathematics in Computer Science, vol. 1, no. 4, pp. 605-623.


Document type: Journal Article
Collection: Journal Articles

Title Lempel-ziv factorization using less time and space
Author(s) Chen, G
Puglisi, S
Smyth, W
Year 2008
Journal name Mathematics in Computer Science
Volume number 1
Issue number 4
Start page 605
End page 623
Total pages 19
Publisher Birkhauser Verlag
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 T(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 T(n)-time alphabet-independent processing in the worst case by avoiding tree structures altogether.
Subject Numerical and Computational Mathematics not elsewhere classified
Keyword(s) Lempel-Ziv
factorization
suffix array
suffix tree
LZ factorization
DOI - identifier 10.1007/s11786-007-0024-4
Copyright notice © 2008 Springer-Verlag.
ISSN 1661-8270
Versions
Version Filter Type
Citation counts: Scopus Citation Count Cited 31 times in Scopus Article | Citations
Altmetric details:
Access Statistics: 65 Abstract Views  -  Detailed Statistics
Created: Mon, 06 Dec 2010, 11:15:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us