Catalog Home Page

A simple algorithm for computing the lempel ziv factorization

Crochemore, M., Ilie, L. and Smyth, W.F. (2008) A simple algorithm for computing the lempel ziv factorization. In: Data Compression Conference (DCC 2008), 25 - 27 March 2008, Snowbird, Utah, USA

[img]
Preview
PDF - Published Version
Download (185kB)
Link to Published Version: http://dx.doi.org/10.1109/DCC.2008.36
*Subscription may be required

Abstract

We give a space-efficient simple algorithm for computing the Lempel-Ziv factorization of a string. For a string of length n over an integer alphabet, it runs in O(n) time independently of alphabet size and uses o(n) additional space.

Publication Type: Conference Paper
URI: http://researchrepository.murdoch.edu.au/id/eprint/28018
Item Control Page Item Control Page

Downloads

Downloads per month over past year