Title :
A Simple Algorithm for Computing the Lempel Ziv Factorization
Author :
Crochemore, Maxime ; Ilie, Lucian ; Smyth, W.F.
Author_Institution :
King´´s Coll. London, London
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.
Keywords :
computational complexity; data compression; Lempel-Ziv factorization; computational complexity; space-efficient simple algorithm; Automata; Computer science; Data compression; Dictionaries; Ecosystems; Educational institutions; Entropy; Software algorithms; Space technology; Tree data structures; Lempel--Ziv factorization; algorithms design; longest common prefix; longest previous factor; repetitions; runs; strings; suffix array;
Conference_Titel :
Data Compression Conference, 2008. DCC 2008
Conference_Location :
Snowbird, UT
Print_ISBN :
978-0-7695-3121-2
DOI :
10.1109/DCC.2008.36
