A simple algorithm for computing the Lempel-Ziv factorization

QR Code

A simple algorithm for computing the Lempel-Ziv factorization

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

Bibliographic Details
Main Authors:	Crochemore, M., Ilie, L., Smyth, William
Other Authors:	James A. Storer
Format:	Conference Paper
Published:	IEEE Computer Society 2008
Online Access:	http://hdl.handle.net/20.500.11937/5907

Similar Items

Lempel-Ziv factorization using less time & space
by: Chen, G., et al.
Published: (2008)

Watermark Compression in Medical Image Watermarking Using Lempel-Ziv-Welch (LZW) Lossless Compression Technique
by: Badshah, Gran, et al.
Published: (2016)

Fast two-stage Lempel-Ziv lossless numeric telemetry data compression using a neural network predictor
by: Logeswaran,, R
Published: (2004)

A simple fast hybrid pattern-matching algorithm
by: Smyth, William Fennell, et al.
Published: (2007)

Fast, Practical Algorithms for Computing All the Repeats in a String
by: Puglisi, Simon, et al.
Published: (2010)

Simple and Efficient Computer Algorithm to Solve Radial Distribution Networks
by: RANJAN, RAKESH, et al.
Published: (2003)

Improved Distributed Wyner-Ziv Video Coding Based On Reed Solomon Error Correction Scheme And Frame Estimation For Wireless Transmission
by: Chiam, Kin Honn
Published: (2015)

Computing regularities in strings
by: Smyth, William, et al.
Published: (2009)

Fast optimal algorithms for computing all the repeats in a string
by: Puglisi, Simon, et al.
Published: (2008)

Faster algorithms for computing maximal multirepeats in multiple sequences
by: Iliopoulos, Costas, et al.
Published: (2009)

A taxonomy of suffix array construction algorithms
by: Puglisi, Simon, et al.
Published: (2007)

Enhancement of a simple user authentication scheme for grid computing
by: Ramamoorthy, Viknesh
Published: (2008)

Clonal selection algorithm for the cryptanalysis of a simple substitution cipher
by: Ahmad, Badrisham, et al.
Published: (2006)

Efficient algorithms for two extensions of LPF table: the power of suffix arrays
by: Crochemore, M., et al.
Published: (2010)

A Simple-to-Use Matlab-based Computer Program for Prediction of Formation Water Properties
by: Bahadori, Alireza, et al.
Published: (2011)

A simple spatio-temporal algorithm for disease surveillance using routinely collected data
by: Watkins, Rochelle, et al.
Published: (2006)

Optimum tolerance synthesis of simple assemblies with nominal dimension selection using genetic algorithm
by: Kumar, D., et al.
Published: (2015)

Weighted simple and semi-simple splicing systems
by: Gan, Yee Siang, et al.
Published: (2014)

A simple approach for branch current computation in load flow analysis of radial distribution systems
by: Prasad, K., et al.
Published: (2007)

An adaptive hybrid pattern-matching algorithm on indeterminate strings
by: Smyth, Bill, et al.
Published: (2009)

Is it optimal to combine forecast with a simple average?
by: Chan, Felix, et al.
Published: (2015)

Simple advice for a simple ankle sprain?: the not so benign ankle injury
by: Palmer-Green, D.S., et al.
Published: (2016)

Study of output factors of electron beam based on the simple model
by: Sohaimi, Norhanna
Published: (2004)

The generative capacity of weighted simple and semi-simple splicing systems
by: Fong, Wan Heng, et al.
Published: (2016)

The generative capacity of weighted simple and semi-simple splicing systems
by: Fong, Wan Heng, et al.
Published: (2015)

Computational power of probabilistic simple one-sided sticker languages / Mathuri Selvarajoo ...[et al.]
by: Selvarajoo, Mathuri, et al.
Published: (2016)

A simulation software for DNA computing algorithms implementation
by: Muhammad, M.S., et al.
Published: (2010)

Simple Synthetic Receptors for Aspirin
by: Nguyen, Thanh Vinh, et al.
Published: (2014)

Transparency: issues are not that simple
by: Pearce, Warren, et al.
Published: (2016)

Transparency: issues are not that simple
by: Pearce, Warren, et al.
Published: (2016)

Science made simple
by: Rajaendram, Rebecca
Published: (2021)

A New Relation of Second Order Limit Language in Simple and Semi-Simple Splicing System
by: Muhammad Azrin, Ahmad, et al.
Published: (2014)

Incompressible flow simulation using S.I.M.P.L.E method on parallel computer
by: Manshoor, Bukhari
Published: (2005)

A simple effective duty cycle controller for high power factor boost rectifier
by: Athab, Hussain S., et al.
Published: (2007)

Just a Few Simple Questions
by: Hunn, Deborah
Published: (2010)

Development of a simple exoskeleton (hardware)
by: Mohd Yashim, Wong Paul Tze
Published: (2013)

Algorithms for computations of Loday algebras’ invariants
by: Said Husain, Sharifah Kartini, et al.
Published: (2017)

Algorithms for computations of invariants of Loday algebras
by: Rakhimov, Isamiddin Sattarovich
Published: (2009)

Application of a simple mono window land surface temperature algorithm from landsat ETM+ over al Qassim, Saudi Arabia
by: Lim, H.S, et al.
Published: (2012)

The integration of computational chemistry algorithms into a multimedia environment
by: Hyde, Richard T.
Published: (1996)