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

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.

Item 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