Reversed Lempel–Ziv Factorization with Suffix Trees

Abstract

We present linear-time algorithms computing the reversed Lempel–Ziv factorization [Kolpakov and Kucherov, TCS’09] within the space bounds of two different suffix tree representations. We can adapt these algorithms to compute the longest previous non-overlapping reverse factor table [Crochemore et al., JDA’12] within the same space but pay a multiplicative logarithmic time penalty.

Keywords

• longest previous non-overlapping reverse factor table
• application of suffix trees
• reversed Lempel–Ziv factorization
• lossless compression