Simpler and Faster Lempel Ziv Factorization
Authors:
- Keisuke GotoKGKeisuke Goto
- Hideo BannaiHBHideo Bannai
- 1 March 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10680314,p. 133-142
Abstract
We present a new, simple, and efficient approach for computing the Lempel-Ziv (LZ77) factorization of a string in linear time, based on suffix arrays. Computational experiments on various data sets show that our approach constantly outperforms the fastest previous algorithm LZ OG (Ohlebusch and Gog 2011), and can be up to 2 to 3 times faster in the processing after obtaining the suffix array, while requiring the same or a little more space.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Lempel-Ziv Factorization: Simple, Fast, Practical2013
- A comparison of index-based lempel-Ziv LZ77 factorization algorithmsACM Computing Surveys, 2012
- Computing Longest Previous Factor in linear time and applicationsInformation Processing Letters, 2008
- A Simple Algorithm for Computing the Lempel Ziv FactorizationData Compression Conference (DCC 2008), 2008
- Linear-time computation of local periodsTheoretical Computer Science, 2004
- Finding maximal repetitions in a word in linear time2003
- On-line construction of suffix treesAlgorithmica, 1995
- Suffix Arrays: A New Method for On-Line String SearchesSIAM Journal on Computing, 1993
- Linear searching for a square in a wordLecture Notes in Computer Science, 1984
- A universal algorithm for sequential data compressionIEEE Transactions on Information Theory, 1977