A simple algorithm for computing the Lempel-Ziv factorization

Maxime Crochemore (1) , Lucian Ilie (2) , William F. Smyth (3)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 Department of Computer Science
3 McMaster University - Department of Computing and Software

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.

Domaines: Algorithme et structure de données [cs.DS]

Maxime Crochemore, Lucian Ilie, William F. Smyth. A simple algorithm for computing the Lempel-Ziv factorization. 18th Data Compression Conference (DCC'08), 2008, United States. pp.482-488. ⟨hal-00620138⟩