Name
Abstract | ||
|---|---|---|
The compressed pattern matching problem is to find all occurrences of a given pattern in a compressed text. In this paper an efficient grammar-based compression algorithm is presented for the compressed pattern matching. The algorithm achieves the worst-case approximation ratio O(g*logg*logn) for the optimum grammar size g* with an input text of length n. This upper bound improves the complexity of the compressed pattern matching problem to $O(g_*\log g_*\log m + \frac{n}{m} + m^2 + r)$ time and O(g*logg*logm + m2) space for any pattern shorter than m and the number r of pattern occurrences. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11940128_49 | ISAAC |
Keywords | Field | DocType |
worst-case approximation ratio,input text,log g,efficient grammar-based compression algorithm,improving time,number r,length n,optimum grammar size g,pattern occurrence,space complexity,log m,pattern matching,upper bound,compression algorithm | Compressed pattern matching,String searching algorithm,Discrete mathematics,Combinatorics,Upper and lower bounds,Spacetime,Data compression,Time complexity,Pattern matching,Mathematics | Conference |
Volume | ISSN | ISBN |
4288 | 0302-9743 | 3-540-49694-7 |
Citations | PageRank | References |
3 | 0.40 | 23 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shirou Maruyama | 1 | 66 | 4.65 |
| Hiromitsu Miyagawa | 2 | 3 | 0.40 |
| Hiroshi Sakamoto | 3 | 47 | 6.63 |