Linear-time off-line text compression by longest-first substitution

Shunsuke Inenaga; Takashi Funamoto; Masayuki Takeda; Ayumi Shinohara

doi:10.1007/978-3-540-39984-1_11

Linear-time off-line text compression by longest-first substitution

Shunsuke Inenaga, Takashi Funamoto, Masayuki Takeda, Ayumi Shinohara

Mathematical Informatics

Research output: Chapter in Book/Report/Conference proceeding › Chapter

9 Citations (Scopus)

Abstract

Given a text, grammar-based compression is to construct a grammar that generates the text. There are many kinds of text compression techniques of this type. Each compression scheme is categorized as being either off-line or on-line, according to how a text is processed. One representative tactics for off-line compression is to substitute the longest repeated factors of a text with a production rule. In this paper, we present an algorithm that compresses a text basing on this longest-first principle, in linear time. The algorithm employs a suitable index structure for a text, and involves technically efficient operations on the structure.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Mario A. Nascimento, Edleno S. de Moura, Arlindo L. Oliveira
Publisher	Springer Verlag
Pages	137-152
Number of pages	16
ISBN (Print)	3540201777, 9783540201779
DOIs	https://doi.org/10.1007/978-3-540-39984-1_11
Publication status	Published - 2003

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2857
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-39984-1_11

Cite this

Inenaga, S., Funamoto, T., Takeda, M., & Shinohara, A. (2003). Linear-time off-line text compression by longest-first substitution. In M. A. Nascimento, E. S. de Moura, & A. L. Oliveira (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 137-152). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2857). Springer Verlag. https://doi.org/10.1007/978-3-540-39984-1_11

Linear-time off-line text compression by longest-first substitution. / Inenaga, Shunsuke; Funamoto, Takashi; Takeda, Masayuki et al.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Mario A. Nascimento; Edleno S. de Moura; Arlindo L. Oliveira. Springer Verlag, 2003. p. 137-152 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2857).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Inenaga, S, Funamoto, T, Takeda, M & Shinohara, A 2003, Linear-time off-line text compression by longest-first substitution. in MA Nascimento, ES de Moura & AL Oliveira (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2857, Springer Verlag, pp. 137-152. https://doi.org/10.1007/978-3-540-39984-1_11

Inenaga S, Funamoto T, Takeda M, Shinohara A. Linear-time off-line text compression by longest-first substitution. In Nascimento MA, de Moura ES, Oliveira AL, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2003. p. 137-152. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-39984-1_11

Inenaga, Shunsuke ; Funamoto, Takashi ; Takeda, Masayuki et al. / Linear-time off-line text compression by longest-first substitution. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Mario A. Nascimento ; Edleno S. de Moura ; Arlindo L. Oliveira. Springer Verlag, 2003. pp. 137-152 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{d44852bb146745d0ab7151f0899eff9e,

title = "Linear-time off-line text compression by longest-first substitution",

abstract = "Given a text, grammar-based compression is to construct a grammar that generates the text. There are many kinds of text compression techniques of this type. Each compression scheme is categorized as being either off-line or on-line, according to how a text is processed. One representative tactics for off-line compression is to substitute the longest repeated factors of a text with a production rule. In this paper, we present an algorithm that compresses a text basing on this longest-first principle, in linear time. The algorithm employs a suitable index structure for a text, and involves technically efficient operations on the structure.",

author = "Shunsuke Inenaga and Takashi Funamoto and Masayuki Takeda and Ayumi Shinohara",

year = "2003",

doi = "10.1007/978-3-540-39984-1_11",

language = "English",

isbn = "3540201777",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "137--152",

editor = "Nascimento, {Mario A.} and {de Moura}, {Edleno S.} and Oliveira, {Arlindo L.}",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}

TY - CHAP

T1 - Linear-time off-line text compression by longest-first substitution

AU - Inenaga, Shunsuke

AU - Funamoto, Takashi

AU - Takeda, Masayuki

AU - Shinohara, Ayumi

PY - 2003

Y1 - 2003

N2 - Given a text, grammar-based compression is to construct a grammar that generates the text. There are many kinds of text compression techniques of this type. Each compression scheme is categorized as being either off-line or on-line, according to how a text is processed. One representative tactics for off-line compression is to substitute the longest repeated factors of a text with a production rule. In this paper, we present an algorithm that compresses a text basing on this longest-first principle, in linear time. The algorithm employs a suitable index structure for a text, and involves technically efficient operations on the structure.

AB - Given a text, grammar-based compression is to construct a grammar that generates the text. There are many kinds of text compression techniques of this type. Each compression scheme is categorized as being either off-line or on-line, according to how a text is processed. One representative tactics for off-line compression is to substitute the longest repeated factors of a text with a production rule. In this paper, we present an algorithm that compresses a text basing on this longest-first principle, in linear time. The algorithm employs a suitable index structure for a text, and involves technically efficient operations on the structure.

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

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

U2 - 10.1007/978-3-540-39984-1_11

DO - 10.1007/978-3-540-39984-1_11

M3 - Chapter

AN - SCOPUS:0142218944

SN - 3540201777

SN - 9783540201779

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 137

EP - 152

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Nascimento, Mario A.

A2 - de Moura, Edleno S.

A2 - Oliveira, Arlindo L.

PB - Springer Verlag

ER -

Linear-time off-line text compression by longest-first substitution

Abstract

Publication series

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this