Academic Journals Database
Disseminating quality controlled scientific knowledge

Linear-Time Text Compression by Longest-First Substitution

Author(s): Ryosuke Nakamura | Shunsuke Inenaga | Hideo Bannai | Takashi Funamoto | Masayuki Takeda | Ayumi Shinohara

Journal: Algorithms
ISSN 1999-4893

Volume: 2;
Issue: 4;
Start page: 1429;
Date: 2009;
Original page

Keywords: grammar-based text compression | suffix trees | linear-time algorithms

We consider grammar-based text compression with 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 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.

Tango Rapperswil
Tango Rapperswil

     Affiliate Program