A simple algorithm for computing the lempel ziv factorization

M. Crochemore; L. Ilie; W.F. Smyth

doi:10.1109/DCC.2008.36

Back

A simple algorithm for computing the lempel ziv factorization

Conference paper

Open access

A simple algorithm for computing the lempel ziv factorization

M. Crochemore, L. Ilie and W.F. Smyth

Data Compression Conference (dcc 2008)

Data Compression Conference (DCC 2008) (Snowbird, Utah, USA, 25/03/2008–27/03/2008)

2008

DOI: https://doi.org/10.1109/DCC.2008.36

Files and links (2)

pdf

lempelzivfactor.pdfDownload View

Published (Version of Record) Open Access

url

Link to Published Version *Subscription may be requiredView

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.

Details

Title: A simple algorithm for computing the lempel ziv factorization
Authors/Creators: M. Crochemore (Author/Creator) - King's College London
L. Ilie (Author/Creator) - Western University
W.F. Smyth (Author/Creator) - Department of Computing and Software
Publication Details: Data Compression Conference (dcc 2008)
Conference: Data Compression Conference (DCC 2008) (Snowbird, Utah, USA, 25/03/2008–27/03/2008)
Identifiers: 991005543101907891
Murdoch Affiliation: Murdoch University
Language: English
Resource Type: Conference paper

Metrics

166 File views/ downloads

123 Record Views