Fast Lempel-Ziv factorisation and consequences

Maxime Crochemore
King's College London and Universite Paris-Est

Abstract: The talk presents a space-efficient simple 
algorithm for computing the Lempel-Ziv factorisation of 
a string. For a string of length n over an integer alphabet,
the algorithm runs in O(n) time independently of
alphabet size and uses O(sqrt(n)) space in addition
to the Suffix Array of the string.

The factorisation is used primarily in text compression
but also in several most efficient algorithms on strings,
which includes: detecting squares, locating repetitions
and runs, computing gapped palindromes, and sequence
alignment. The linear-time Lempel-Ziv factorisation
yields algorithms faster than those based on balanced
divide-and-conquer methods for all of these problems.