Lempel-Ziv factorization using less time & space
dc.contributor.author | Chen, G. | |
dc.contributor.author | Puglisi, Simon | |
dc.contributor.author | Smyth, B. | |
dc.date.accessioned | 2017-01-30T15:19:26Z | |
dc.date.available | 2017-01-30T15:19:26Z | |
dc.date.created | 2009-03-05T00:54:16Z | |
dc.date.issued | 2008 | |
dc.identifier.citation | Chen, Gang and Puglisi, Simon and Smyth, Bill. 2008. Lempel-Ziv factorization using less time & space. Mathematics in Computer Science 1 (4): pp. 605-623. | |
dc.identifier.uri | http://hdl.handle.net/20.500.11937/45235 | |
dc.identifier.doi | 10.1007/s11786-007-0024-4 | |
dc.description.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. | |
dc.publisher | Birkhauser | |
dc.subject | LZ factorization | |
dc.subject | suffix tree | |
dc.subject | suffix array | |
dc.subject | Lempel-Ziv factorization | |
dc.title | Lempel-Ziv factorization using less time & space | |
dc.type | Journal Article | |
dcterms.source.volume | 1 | |
dcterms.source.number | 4 | |
dcterms.source.startPage | 605 | |
dcterms.source.endPage | 623 | |
dcterms.source.issn | 16618270 | |
dcterms.source.title | Mathematics in Computer Science | |
curtin.department | Centre for Extended Enterprises and Business Intelligence | |
curtin.accessStatus | Fulltext not available | |
curtin.faculty | Curtin Business School | |
curtin.faculty | The Centre for Extended Enterprises and Business Intelligence (CEEBI) |