Name
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.3390/a2041429 | ALGORITHMS |
Keywords | Field | DocType |
grammar-based text compression, suffix trees, linear-time algorithms | Data structure,Text compression,Suffix,Computer science,Computational mathematics,Algorithm,Grammar,Artificial intelligence,Time complexity,Numerical analysis,Machine learning | Journal |
Volume | Issue | ISSN |
2 | 4 | 1999-4893 |
Citations | PageRank | References |
7 | 0.62 | 17 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ryosuke Nakamura | 1 | 68 | 21.87 |
| Shunsuke Inenaga | 2 | 595 | 79.02 |
| Hideo Bannai | 3 | 620 | 79.87 |
| Takashi Funamoto | 4 | 19 | 1.33 |
| Masayuki Takeda | 5 | 902 | 79.24 |
| Ayumi Shinohara | 6 | 936 | 88.28 |