Name
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. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1007/978-3-540-39984-1_11 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
linear time,first principle | Compression (physics),Off line,Text compression,Computer science,Tree (data structure),Algorithm,Grammar,Time complexity,Data compression,String (computer science) | Conference |
Volume | ISSN | Citations |
2857 | 0302-9743 | 12 |
PageRank | References | Authors |
0.71 | 17 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shunsuke Inenaga | 1 | 595 | 79.02 |
| Takashi Funamoto | 2 | 19 | 1.33 |
| Masayuki Takeda | 3 | 902 | 79.24 |
| Ayumi Shinohara | 4 | 936 | 88.28 |