Linear-Time text compression by longest-first substitution

Ryosuke Nakamura; Shunsuke Inenaga; Hideo Bannai; Takashi Funamoto; Masayuki Takeda; Ayumi Shinohara

doi:10.3390/a2041429

Linear-Time text compression by longest-first substitution

Ryosuke Nakamura, Shunsuke Inenaga, Hideo Bannai, Takashi Funamoto, Masayuki Takeda, Ayumi Shinohara

INF - System Information Sciences

Kyushu University

Research output: Contribution to journal › Article › peer-review

16 Citations (Scopus)

Abstract

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.

Original language	English
Pages (from-to)	1429-1448
Number of pages	20
Journal	Algorithms
Volume	2
Issue number	4
DOIs	https://doi.org/10.3390/a2041429
Publication status	Published - 2009 Dec

Keywords

Grammar-based text compression
Linear-time algorithms
Suffix trees

Access to Document

10.3390/a2041429

Cite this

@article{fde266061f5e4dacba383cf1e99d1ebd,

title = "Linear-Time text compression by longest-first substitution",

abstract = "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.",

keywords = "Grammar-based text compression, Linear-time algorithms, Suffix trees",

author = "Ryosuke Nakamura and Shunsuke Inenaga and Hideo Bannai and Takashi Funamoto and Masayuki Takeda and Ayumi Shinohara",

year = "2009",

month = dec,

doi = "10.3390/a2041429",

language = "English",

volume = "2",

pages = "1429--1448",

journal = "Algorithms",

issn = "1999-4893",

publisher = "MDPI AG",

number = "4",

}

TY - JOUR

T1 - Linear-Time text compression by longest-first substitution

AU - Nakamura, Ryosuke

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

AU - Funamoto, Takashi

AU - Takeda, Masayuki

AU - Shinohara, Ayumi

PY - 2009/12

Y1 - 2009/12

N2 - 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.

AB - 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.

KW - Grammar-based text compression

KW - Linear-time algorithms

KW - Suffix trees

UR - http://www.scopus.com/inward/record.url?scp=77953038533&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77953038533&partnerID=8YFLogxK

U2 - 10.3390/a2041429

DO - 10.3390/a2041429

M3 - Article

AN - SCOPUS:77953038533

SN - 1999-4893

VL - 2

SP - 1429

EP - 1448

JO - Algorithms

JF - Algorithms

IS - 4

ER -

Linear-Time text compression by longest-first substitution

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this