Name
Abstract | ||
|---|---|---|
We present a new text indexing structure based on the run length encoding RLE of a text string $$T$$ which, given the RLE of a query pattern $$P$$, reports all the $$occ$$ occurrences of $$P$$ in $$T$$ in $$Om + occ + \\log n$$ time, where $$n$$ and $$m$$ are the sizes of the RLEs of $$T$$ and $$P$$, respectively. The data structure requires $$n 2\\log N + \\log n + \\log \\sigma + On$$ bits of space, where $$N$$ is the length of the uncompressed text string $$T$$ and $$\\sigma $$ is the alphabet size. Moreover, using $$n 3\\log N + \\log n + \\log \\sigma + 2 \\sigma \\log \\frac{N}{\\sigma } + On \\log \\log n$$ bits of total space, our data structure can be enhanced to answer the beginning position of the lexicographically $$i$$th smallest suffix of $$T$$ for a given rank $$i$$ in $$O\\log ^2 n$$ time. All these data structures can be constructed in $$On \\log n$$ time using $$On \\log N$$ bits of extra space. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-319-18173-8_29 | CIAC |
Field | DocType | Volume |
Data structure,Binary logarithm,Discrete mathematics,Combinatorics,Suffix,Search engine indexing,Run-length encoding,Lexicographical order,Sigma,Mathematics,Alphabet | Conference | 9079 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
8 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuya Tamakoshi | 1 | 6 | 0.79 |
| Keisuke Goto | 2 | 98 | 13.93 |
| Shunsuke Inenaga | 3 | 595 | 79.02 |
| Hideo Bannai | 4 | 620 | 79.87 |
| Masayuki Takeda | 5 | 902 | 79.24 |