Linear-time text compression by longest-first substitution (Q1662518)

Summary: We consider grammar-based text compression with \textit{longest first substitution} (LFS), where non-overlapping occurrences of a longest repeating factor of the input text are replaced by a new non-terminal symbol. We present the first linear-time algorithm for LFS. Our algorithm employs a new data structure called \textit{sparse lazy suffix trees}. We also deal with a more sophisticated version of LFS, called LFS2, that allows better compression. The first linear-time algorithm for LFS2 is also presented.