Name
Abstract | ||
|---|---|---|
A space-efficient linear-time approximation algorithm for the grammar-based compression problem, which requests for a given string to find a smallest context-free grammar deriving the string, is presented. The algorithm consumes only O (g(*) log g(*)) space and achieves the worstcase approximation ratio O(log g(*) log n), with the size n of an input and the optimum grammar size g(*). Experimental results for typical benchmarks demonstrate that our algorithm is practical and efficient. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/978-3-540-30213-1_33 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
context free grammar,linear time | Discrete mathematics,Approximation algorithm,Binary logarithm,Context-free grammar,Commentz-Walter algorithm,Algorithm,Rabin–Karp algorithm,Linear grammar,Time complexity,String (computer science),Mathematics | Conference |
Volume | ISSN | Citations |
3246 | 0302-9743 | 7 |
PageRank | References | Authors |
0.48 | 20 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hiroshi Sakamoto | 1 | 47 | 6.63 |
| Takuya Kida | 2 | 271 | 23.56 |
| Shinichi Shimozono | 3 | 111 | 15.65 |